The DominoPeg Puzzle
It is difficult to fit all the pieces into the puzzle, and it is even more difficult to find a solution to the puzzle given a specific arrangement of these five holes. This is what prompted me to write a solver.
 | |
|
The Solver
The entire solution can be found here.
I wrote the solver in Ruby for the same reason that I write so many of my solutions in Ruby: because it's fun! The solution is 249 lines long. It consists of a Piece class, a Board class, and a Solver module. We'll set up a domain to represent our puzzle and then employ a depth-first search algorithm to find a solution to the puzzle.
Setting the Problem Domain
We represent the puzzle board by setting up a grid. The puzzle actually contains two grids, one that represents the placement of the pieces, and one that represents the locations of the circles, leaving 5 circles empty when all puzzle pieces are placed in the puzzle. The board's piece dimensions are 6 x 4 and its circle dimensions are 7 x 5. Each puzzle piece has piece dimensions of 2 x 1 and circle dimensions of 3 x 2. When placing a puzzle piece on the board we keep track of both the piece positions that the puzzle piece takes up and the circle positions that the puzzle piece takes up.
 |
| The board is represented by a circle grid where each circle is represented by index 0 through 34 |
 | |
|
When the board is organized in this way, placing a piece on the board is a matter of marking what spots the piece takes up, and continuing to place pieces on the board until we find a solution.
We represent puzzle pieces based on the circles that they cover. We have canonical representations of each of the 12 puzzle pieces. In addition to these 12 canonical representations, we represent flipped puzzle pieces and rotated puzzle pieces as separate puzzle pieces that are variations of the same canonical puzzle piece. These transformations of puzzle pieces lead to 70 distinct puzzle pieces when orientation is taken into account. The reason there are 70 distinct pieces and not 96 (12 pieces X 4 rotations X 2 flips) is because some of the pieces contain symmetry and are duplicates of each other.
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
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]
Flips represent whether the piece is a flipped version of one of the canonical representations. Orientation represents whether the canonical pieces is rotated and by how many degrees it is rotated (0 representing no rotation of the canonical piece). A base piece's spots represent the circles that would be covered on the board if the piece were to be placed in the top left of the board.
In order to represent each piece we take the canonical representation and apply transformations to the piece positions and circles that it covers.
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
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
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},
}
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},
}
Solving Using Depth-First Search
The solver is a recursive algorithm employing depth-first search. For each of the puzzle pieces it has, it places the piece in the puzzle, and then tries to solve a new puzzle with the new set of puzzle pieces (the placed puzzle piece and canonical equivalent pieces are removed) and the new board (because the new board has additional constraints added to it by the piece that was just laid).
If there are no more puzzle pieces left then we know that we have placed all the puzzle pieces on the board and have found a solution. If we go through all our pieces and none of them can be placed on the board, then we know we've hit a dead end and this board cannot be solved with this set of puzzle pieces.
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
When determining if a board accepts a piece, we only need to look at the top left most uncovered piece position. If we cannot fit any of our pieces into that position, then the current board configuration is invalid and there is no need to try to further fit pieces into this configuration.
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
When verifying that a piece fits on a board, we first perform a check to see if the piece position goes off the edge of the board horizontally. Then we check both the piece positions and the circle positions to make sure that they both fit on the board.
When checking the piece positions, we verify that the piece does not go off the board vertically and that there are no other pieces that would be in the way of this piece before we place it.
Finally, we check all the circle positions that this piece would fill on the board and verify that no previous pieces are filling these circle positions. If all of these checks pass then this piece can validly be placed on this board.
Putting It All Together
Now that we have our domain and our solver, we can put them together to solve our puzzle.
def main
pieces = _init_pieces
board = Board.new([0, 7, 14, 21, 28])
solution = Solver.solve(board, pieces)
puts solution
end
main if __FILE__ == $PROGRAM_NAME
Main is the main jumping point into our program. We initialize all of our distinct pieces, set up a board passing in a list of constraints that represent the 5 circles we want to be blank at the end, invoke solve on our board and pieces, and then print the solution.
The Results
Because this is a depth-first search solution, solution times will vary depending on where the solution is located in your search space and how you choose to traverse that space. Solving three puzzles with different constraints produced the following results:
| Puzzle Constraints | Time to Solve | Total Pieces Placed |
|---|---|---|
| Board.new([0, 10, 20, 24, 28]) | 5m15.509s | 4,461,278 |
| Board.new([0, 7, 14, 21, 28]) | 2m49.996s | 2,397,106 |
| Board.new([25, 26, 27, 32, 33, 34]) (Unsolvable) | 24 hours+ | 1,220,171,512 |
The puzzle with unsolvable constraints gives you an idea of size of the search space of this problem. I stopped the solver after 24 hours. Though it is difficult to adequately determine the total number possible placements of pieces due to the complexity of the constraints, my rough calculations indicate that to try all possible combinations of laying pieces on the board would take years given this solver.
These results were derived on my laptop with a core i7 processor, running single-threaded (because this is Ruby).
A lot of improvements could be made to the performance of this algorithm. This approach is fairly naive and leaves out a lot of optimizations for the sake of readability. For example, a faster algorithm would take advantage of constraints as soon as possible, so it would be more optimal to find the provided constraints and place pieces around them, failing faster than trying possibilities that do not take advantage of these constraints.
Also, choosing a more performant language and one that can utilize native threads to parallelize the search for a solution would provide an additional speedup that we are not able to leverage with Ruby.
Thanks for reading! Have any thoughts on solving this puzzle or solving any other puzzles using artificial intelligence? Leave a comment below.