Create a gist now

Instantly share code, notes, and snippets.

What would you like to do?
A solver for the dominopeg wood puzzle
#!/usr/bin/env ruby
# Solves [dominopeg puzzle](http://www.puzzlemist.com/dominopeg.html)
BasePieces = [
{id: "0", spots: [0, 1]},
{id: "1", spots: [0, 2]},
{id: "2", spots: [0, 7]},
{id: "3", spots: [0, 8]},
{id: "4", spots: [0, 9]},
{id: "5", spots: [1, 8]},
{id: "6", spots: [0, 1, 2]},
{id: "7", spots: [0, 1, 7]},
{id: "8", spots: [0, 1, 8]},
{id: "9", spots: [0, 1, 9]},
{id: "A", spots: [0, 2, 7]},
{id: "B", spots: [0, 2, 8]},
]
Flips = [false, true]
Orientations = [0, 90, 180, 270]
FlipMap = {0=>7, 1=>8, 2=>9, 7=>0, 8=>1, 9=>2}
OrientationMaps = {
0 => {0=>0, 1=>1, 2=>2, 7=>7, 8=>8, 9=>9},
90 => {0=>1, 1=>8, 2=>15, 7=>0, 8=>7, 9=>14},
180 => {0=>9, 1=>8, 2=>7, 7=>2, 8=>1, 9=>0},
270 => {0=>14, 1=>7, 2=>0, 7=>15, 8=>8, 9=>1},
}
class Piece
PIECE_WIDTH = 2
PIECE_HEIGHT = 1
CIRCLE_WIDTH = 3
CIRCLE_HEIGHT = 2
attr_accessor :base_piece, :flip, :orientation
def initialize(base_piece, flip, orientation)
@base_piece = base_piece
@flip = flip
@orientation = orientation
end
def horizontal?
orientation == 0 || orientation == 180
end
def piece_width
horizontal? ? PIECE_WIDTH : PIECE_HEIGHT
end
def piece_height
horizontal? ? PIECE_HEIGHT : PIECE_WIDTH
end
def circle_width
horizontal? ? CIRCLE_WIDTH : CIRCLE_HEIGHT
end
def circle_height
horizontal? ? CIRCLE_HEIGHT : CIRCLE_WIDTH
end
def piece_positions
horizontal? ? [0, 1] : [0, 6]
end
def transpose
return @transpose if @transpose
spots = base_piece[:spots]
spots = spots.map { |spot| FlipMap[spot] } if flip
@transpose = spots.map { |spot| OrientationMaps[orientation][spot] }.sort
end
def to_s
base_width_transpose = _base_transpose
piece_array = (0...circle_height).map do |y|
(0...circle_width).map do |x|
spot = y * circle_width + x
base_width_transpose.include?(spot) ? base_piece[:id] : "U"
end
end
piece_row = Array.new(circle_width, " ").join("+")
piece_array.map { |row| row.join(" ") }.join("\n#{piece_row}\n") + "\n\n"
end
def _base_transpose
transpose.map do |spot|
spot % Board::WIDTH + spot / Board::WIDTH * circle_width
end
end
end
class Board
WIDTH = 7
HEIGHT = 5
PIECE_WIDTH = 6
PIECE_HEIGHT = 4
attr_accessor :board, :piece_board
def self.from_existing_board(board)
new_board = Board.new
new_board.board = board.board.dup
new_board.piece_board = board.piece_board.dup
new_board
end
def initialize(constraints=nil)
@board = Array.new(WIDTH*HEIGHT)
@piece_board = Array.new(PIECE_WIDTH*PIECE_HEIGHT)
constraints.each { |constraint| board[constraint] = "O" } if constraints
end
def accepts?(piece)
first_piece_spot = _first_empty_piece_spot
piece_positions = _piece_positions(first_piece_spot, piece)
if piece_positions[0] % PIECE_WIDTH + piece.piece_width > PIECE_WIDTH
return false
end
piece_positions.each do |piece_position|
return false if piece_position >= PIECE_WIDTH * PIECE_HEIGHT
return false unless piece_board[piece_position].nil?
end
first_circle_spot = _piece_spot_to_circle_spot(first_piece_spot)
_circle_positions(first_circle_spot, piece).each do |spot|
return false unless board[spot].nil?
end
true
end
def apply(piece)
first_piece_spot = _first_empty_piece_spot
_piece_positions(first_piece_spot, piece).each do |piece_position|
piece_board[piece_position] = piece.base_piece[:id]
end
first_circle_spot = _piece_spot_to_circle_spot(first_piece_spot)
_circle_positions(first_circle_spot, piece).each do |spot|
board[spot] = piece.base_piece[:id]
end
@first_empty_piece_spot = nil
end
def _first_empty_piece_spot
@first_empty_piece_spot ||= piece_board.index { |spot| !spot }
end
def _piece_spot_to_circle_spot(piece_spot)
piece_spot + piece_spot / PIECE_WIDTH
end
def _piece_positions(first_piece_spot, piece)
piece.piece_positions.map do |piece_spot|
first_piece_spot + piece_spot
end
end
def _circle_positions(first_circle_spot, piece)
piece.transpose.map do |spot|
first_circle_spot + spot
end
end
def to_s
circle_arrays = (0...HEIGHT).map do |y|
(0...WIDTH).map do |x|
spot = y * WIDTH + x
board[spot] || " "
end
end
piece_arrays = (0..PIECE_HEIGHT).map do |y|
(0...PIECE_WIDTH).map do |x|
spot = y * PIECE_WIDTH + x
piece_board[spot] || " "
end
end
full_array = circle_arrays.zip(piece_arrays).flatten(1).compact
string = ""
full_array.each_with_index do |row, index|
if index.even?
string << "#{row.join(" ")}"
else
string << " #{row.join(" ")} "
end
string << "\n"
end
string << "\n\n"
end
end
module Solver
def self.solve(board, pieces)
if pieces.any?
pieces.each do |piece|
if board.accepts?(piece)
new_pieces = remove(pieces, piece)
new_board = Board.from_existing_board(board)
new_board.apply(piece)
solution = solve(new_board, new_pieces)
return solution if solution
end
end
else
return board
end
nil
end
def self.remove(pieces, piece_to_remove)
pieces.reject do |piece|
piece.base_piece[:id] == piece_to_remove.base_piece[:id]
end
end
end
def main
pieces = _init_pieces
board = Board.new([0, 7, 14, 21, 28])
solution = Solver.solve(board, pieces)
puts solution
end
def _init_pieces
pieces = []
BasePieces.each do |base_piece|
Flips.each do |flip|
Orientations.each do |orientation|
pieces << Piece.new(base_piece, flip, orientation)
end
end
end
pieces.uniq { |piece| [piece.transpose, piece.horizontal?] }
end
main if __FILE__ == $PROGRAM_NAME
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment