Skip to content

Instantly share code, notes, and snippets.

Embed
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
You can’t perform that action at this time.
You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session.