Last active
February 5, 2017 20:46
-
-
Save pblesi/04eae033d76132d4de6f98ec9581c1f8 to your computer and use it in GitHub Desktop.
A solver for the dominopeg wood puzzle
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#!/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