kleemans.ch

Around three years ago, I got my wife a present: a pentomino jigsaw puzzle. It looks like this:

It consists of 20 parts, which are made out of 5 regular jigsaw pieces. The smaller pieces can have two different kinds of orientation, and the board allows one type at a certain place.

The problem is that it is really difficult to solve. We tried for a long time but unfortunately to no avail. So, what now?

Brute force to the rescue

My first idea was, why not just write a small Python script that brute forces all the possibilities?

First I had to encode the puzzle parts and board into code:

Every piece can be described by a an id and and a list of small parts, consisting of coordinates and an orientation ("-" or "|").

For example, the piece 0 would be represented like this (orientation, y, x):

Parts: 
0 = ('-', 0, 0), ('|', 1, 0), ('-', 2, 0), ('|', 2, 1), ('|', 3, 0)
1 = ...

As a first naïve attempt, I wrote a simple brute force with one recursive method place_piece():

• Pick a next puzzle piece
• Place it anywhere on the board
• Repeat until solved or no piece can be placed, in that case go back and pick the next piece

The problem with this approach, as I soon found out, was that it was taking ages without any result.

Improvement #1: Pruning impossible paths

The obvious first step was to prune paths from an unsolvable board state. For example, with a simple flood fill we can find enclosures that are smaller than 5 pieces, and know immediately that we have an unsolvable board state:

Improvement #2: Introducing hashing

What I also noticed was that I was checking the same board situation multiple times, as different orders of placing pieces would lead to the same situation, like here:

Remembering the Memoization problems from last year's Advent of Code, I added a check at the start of the place_piece() method to see if we've already (unsuccesfully) covered the current board state. If yes, we can return and go and try the next piece.

Improvement #3: Put next piece adjacent to placed pieces

One observation which turned out to be crucial was that when solving the puzzle by hand, I would always start and try to put the next piece onto the already placed pieces.

Until now, the algorithm just put the next piece anywhere on the board:

This is quite different to what you would do intuitively. So it's possible to cut the amount of possibilities by a huge part by only allowing placement next to an already placed piece on the board (except for the first piece).

Improvement #4: Adding a heuristic for compactness

As soon as I implemented the adjacent placement, I noticed another feature of trying to solve the puzzle by hand: I would also try to be as "compact" as possible, at least by intuition.

For example, these two board situations use the exact same pieces (and are also all connected):

But intuitively, the first is much more compact, so I tried to come up with a heuristic to order the placement possibilities.

Score for compactness:

• Loop over all placed pieces
• For every small part of a piece, check all 4 possible neighbor cells
• If the neighbor cell is empty (or outside the board), increase the count by one

This would lead to lower scores if small parts were placed besides each other. By sorting the placement possibilities by the lowest score first, the script would pick those first.

After implementing this (and turning of the), the script soon came up with a 19 piece solution:

We're getting closer!

Improvement #5: Improving the pruning

I noticed another small possible improvement, to only allow a single, connected piece of free space. Until now, the algorithm was also continuing on situations like this:

As I was convinced that it would be possible to only ever have a single, connected free space (which was getting smaller with every piece), I added this restriction to the is_solvable()-check.

Improvement #6: Only consider the top possibilities

As the script was still running for a long time without any progress above the 19 pieces solution, I became a bit discouraged, and thought of ways to reduce the search space (which still seemed too big to search for). So, why not just try to topmost 3, 4, 5 best possibilities and try my luck?

With only considering the top 5 possibilities at every level, I got lucky, and after a few hours, the script finally spit out a correct solution:

Quite the journey, and a fun one too. You can find the final script here:

Happy puzzling!