Automating Puzzle Solving With Python
Can’t quite figure out that puzzle? Have you tried brute forcing every possible combination?
I received this puzzle as a gift on Christmas, and I naively dumped all the pieces out of the board as soon as I opened it. A smarter person probably would’ve taken a photo of the original solution, just in case. I would regret this oversight deeply in the hours that followed, as I repeatedly tried and failed to put all the pieces back in their place. I came agonizingly close many times, placing 12 of the 13 pieces before realizing it would be impossible for the final piece to fit.
Soon after this I enlisted the help of friends and family, but even their combined efforts proved no match for the deceptively simple-looking puzzle. Finally, a friend found a configuration that worked, but the victory felt hollow. This puzzle had defeated many of us, wasting hours of everyone’s time. Fueled in equal parts by curiosity and frustration, I decided to build an algorithm to crush this puzzle completely. My intuition told me that the puzzle was difficult because there was probably only one unique solution. I couldn’t rule out the possibility of dozens or hundreds of solutions, but it seemed unlikely. With an algorithm, I’d be able to prove it one way or the other.
The Puzzle
It was only after I finished my algorithm and started research for this article that I found out the game I received is a version of something called a “pentomino puzzle.” Apparently, pentomino is the name for a shape made up of five equally-sized squares.
In a typical pentomino puzzle, the only pieces on the board are, well, pentominoes. Our puzzle is somewhat unique since it includes an additional 2x2 square piece. To follow the naming convention of the graphic above, I’ll refer to this piece from now on as the “O quadromino.”
The different pieces add varying degrees of complexity to the puzzle. For example, the O quadromino only has one orientation. No matter how we rotate or flip it, the actual profile of the shape remains the same. On the other end of the spectrum, the F pentomino has eight possible orientations.
To find every possible solution to the puzzle, we need to consider every possible flip and rotation for every piece. To represent these complex states, we’ll transition our board representation from the physical world to the digital.
The Board
I chose a list of lists as the data structure for both the board and the pieces. The board is initialized with values of 0 to symbolize empty squares. The pieces each have a value from 1–13, which makes it possible to discriminate between them when they’re placed on the board. I also wrote two functions to manipulate the orientation of the pieces: one to rotate the piece arrays 90 degrees clockwise and another to reflect a piece across its Y axis. Combined, they can create every possible position for a given piece.
board = [[0, 0, 0, 0, 0, 0, 0, 0] for _ in range(8)]
pieces = (
[[1, 1],
[1, 1]],
[[2, 0, 0],
[2, 0, 0],
[2, 2, 2]],
[[0, 3, 0],
[3, 3, 3],
[0, 3, 0]],
[[4, 4, 4, 4, 4]],
...
)
def rotate_piece(piece):
return [list(row[::-1]) for row in zip(*piece)]
def reflect_piece(piece):
return [row[::-1] for row in piece]Now we need a method to place pieces on the board without breaking any game rules. Before we place a piece down, we need to check two criteria:
- The piece won’t hang off the edge of the board.
- The piece won’t overlap with any pieces already on the board.
As long as both rules are met, it is legal to place the piece.
def add_piece(board, piece, start_row, start_col):
piece_width = len(piece[0])
piece_height = len(piece)
legal_move = True
# check if piece is hanging off the edge of the board
if (start_row + piece_height > len(board)) or
(start_col + piece_width > len(board[0])):
legal_move = False
return board, legal_move
changed_squares = []
for i, row in enumerate(piece):
for j, val in enumerate(row):
# only add filled spaces, never take away
if val:
# don't overwrite existing pieces on the board
if board[start_row + i][start_col + j]:
legal_move = False
return board, legal_move
else:
changed_squares.append((start_row + i, start_col + j, val))
new_board = [[val for val in row] for row in board]
for changed_row, changed_col, val in changed_squares:
new_board[changed_row][changed_col] = val
return new_board, legal_moveAt this point, we have a game board that behaves exactly as the board in real life does. Only now, instead of me having to test out a dozen combinations every minute, we can write software to churn out thousands of combinations per second. To make this a reality, we need an algorithm capable of generating all those possible board states.
The Algorithm
I decided to go with a tried-and-true approach called backtracking. The basic idea of this method is to make a choice, then undo it later if it turns out to be incorrect. For the pentomino puzzle, we want to place pieces down on the board until it becomes impossible to place any more pieces. When this happens, it’s because we’ve either run out of pieces and solved the puzzle or (much more likely) placed pieces in a configuration that doesn’t fit on the board. We must start undoing some previous choices when we hit this dead end.
First, we pull the most recently placed piece off the board. If it can fit in a way that hasn’t been tried yet, we put the piece back on the board in this new orientation and continue placing more pieces. If all orientations have been exhausted for the piece, we backtrack again and try the same thing with the next most recently-placed piece. Repeating this procedure will produce every possible board state in the pentomino puzzle.
def solve_board(board, pieces):
# piece_positions contains all possible orientations for a given piece
piece_positions = pieces[0]
for position in piece_positions:
# find every place a piece can fit into the board
legal_squares = get_legal_squares(board, position)
for row, col in legal_squares:
# place the piece, repeat with new board
new_board, _ = add_piece(board, position, row, col)
solve_board(new_board, pieces[1:])Well, that was pretty simple. Now we can sit back and let the algorithm go to town, right? Unfortunately, it won’t be that easy. There are billions of possible board configurations, and the overwhelming majority are not even close to solutions. If we visualize what the algorithm is doing right now, it’s easy to see that it’s wasting most of its time on impossible board configurations. For example, when the X pentomino is placed in the top left corner of the board, any work the algorithm does is useless until the X pentomino is moved since the top left square cannot be filled.
Optimizations
It turns out the solution to this issue is straight out of a Leetcode problem. In our case, we can think of the empty squares surrounded by pieces as “islands.” We want to prevent the algorithm from generating boards where a pentomino can’t fit into an island.
To count the size of each island, we’ll use a depth-first search. More recursion! This “island counter” algorithm scans through the board until it finds a square with a value of zero. It marks that square as visited, increments a counter variable, and recursively calls itself on all the square’s neighbors. The island has been fully explored when the algorithm runs out of zero-valued neighbor squares to check. The counter now contains the size of the island. If the island has less than four squares, the configuration is unsolvable, so we throw that board configuration away.
We have to allow islands of four squares because of the O quadromino, which is the only piece that could actually fit there. We can get around this restriction by always placing the O quadromino first. Since it’s always on the board, we’ll never have to worry about finding space for it. Now we can switch the algorithm to only allow islands if they’re multiples of five.
def legal_islands(board):
board = [[elem for elem in row] for row in board]
board_height = len(board)
board_width = len(board[0])
island_size = 0
# depth first search on island squares
def island_dfs(row, col):
# break if square is out of bounds or nonzero
if row < 0 or col < 0 or
row >= board_height or col >= board_width or
board[row][col] != 0:
return
island_cells += 1
board[row][col] = "#"
island_dfs(row - 1, col)
island_dfs(row + 1, col)
island_dfs(row, col - 1)
island_dfs(row, col + 1)
for row in range(board_height):
for col in range(board_width):
if board[row][col] == 0:
island_dfs(row, col)
# only allow islands if they're multiples of five
if len(island_cells) % 5 != 0:
return False
island_cells = []
return TrueThe additional computation may slow the overall algorithm down a little, but it more than compensates for this by eliminating a massive number of incorrect paths.
Solutions
I hit run on my solver and glued my eyes to the terminal output. Nothing happened for about 30 seconds, and then suddenly, it spat out three unique solutions simultaneously. Five minutes later, it was up to 34. My intuition was completely shattered. It became clear that the number of solutions was at least in the thousands, if not more. I felt like laughing as the computer found more and more solutions for a puzzle I couldn’t even solve once.
I had come this far and just needed to know exactly how many solutions were out there. Luckily, I had access to an unused server where nobody would mind if I cranked out puzzle simulations. Even with multiprocessing implemented, it took about a day to finish running. But at last, I had my answer! There are 129,168 solutions to the pentomino puzzle!
More Optimizations, Less Solutions
A day later, it hit me that there are definitely not 129,168 solutions to this puzzle. Many solved boards were just rotations or reflections of other solved boards, which means they aren’t truly unique. To remove the duplicates, we need to “normalize” each board to undo all those transformations.
My solution was to pick a standard orientation for the F pentomino and rotate/reflect every board until the F pentomino was in that standard orientation. This eliminates any differences between boards caused by rotation or reflection and allows us to compare them directly.
After removing all the duplicates in this way, I was left with 16,146 genuinely unique solutions. Notably, this is exactly 1/8 of the original amount of solutions. I had a hunch this would be the case, but it felt good to prove it.
This approach made me realize one final optimization for generating solutions. We can restrict ourselves to only generating boards where the F pentomino is in its standard orientation. This prevents us from generating duplicate boards and reduces the algorithm’s runtime to 1/8 of its previous best.
Final Thoughts
I’m sure there are plenty of additional optimizations for my code. For example, the island finder algorithm could be modified to not allow islands in the shape of pieces already on the board. I could even try to solve the puzzle the way Donald Knuth did it. It wouldn’t be the first time I’ve implemented one of his algorithms. For now, though, I’m satisfied with what I have.
If you’re interested in playing the pentomino puzzle or just messing with the code, my implementation is freely available on GitHub. Thanks for reading!
