This post details a backtracking algorithm for solving scramble square puzzles. This is a deceptively simple looking puzzle, with only 9 pieces, but it can be very challenging to solve, with over 23.8 billion possible arrangements.
When I was a child, I used to spend many hours trying to solve a scramble square puzzle. An example is shown above. The puzzle consists of nine square pieces and four images spread across the squares. On each side on each square is half of one of the four images. For example the top half of an elephant. Some of the other pieces have the corresponding half, like the bottom half of the elephant. The aim to is arrange the pieces in a 3x3 grid such that all inner images are aligned - all halves are matched. This is actually very difficult, and I was not able solve it.
Much later, when I was in university, I returned to this puzzle. I wondered if there was a procedural method to solve it. Such methods exist for Rubik’s cubes. I was not able to find any, but I did find a depth first search backtracking algorithm for it described in this paper. This algorithm is rather painful to do by hand, but easy to implement with a computer. I wrote up the algorithm in Python, and within a second, I found the two solutions for my puzzle. So much for hours of frustration when I was younger!
The rest of this post will describe this algorithm in detail.
The search space for this puzzle is surprisingly large. There are $9!$ permutations for placing each puzzle piece, and each piece has 4 orientations, except for the middle piece (because rotating this piece just rotates the entire puzzle). This gives $4^8 9! \approx 23.8$ billion arrangements of the puzzle. Therefore, just trying every puzzle arrangement is too slow.
The backtracking algorithm is more efficient. In this algorithm, each piece is placed one at a time in the order shown above. Then either the piece fits, and we move onto the next position, or it does not and we try a new piece. If we run out of pieces, we backtrack to the last position where a piece was placed, and try a new piece. If we reach position k=8 and the last piece fits successfully, a solution is registered. Then we backtrack again to find other solutions.
This algorithm very effectively cuts down the search space. If a piece does not fit in the kth position, then all arrangements with the piece in that position are skipped. So if for example, a piece does not fit in position k=1, then all $4(4^7 7!)$ arrangements with the piece in this position are skipped. That’s 1.4% of the total search space.
The Serengeti puzzle I posted above has no solution1. So instead I’ll use a mock-up of a puzzle I had as a child. This is shown above. The goal here is to match triangles with blocks of the same colour. I’ve labelled each piece from 0 to 8. Each piece is encoded as an array using the following rules:
For example, piece 0 is encoded as
[-2, -3, +1, +4].
The rest of the pieces look like:
The state of the puzzle can be summarised in two variables:
order, a list of the order of placements of pieces, and
rot, the current rotation applied to each piece.
A rotation is encoded as a number from 0 to 3.
I created a simple class to store this state. I’ve also made a nice representation for the
I can now present the algorithm in full. I will go into the detail of the abstract functions afterwards:
I’ve written the algorithm as a recursive function, so that Python’s memory stack can keep track of different puzzle states for us.
This could also be done in
for loop, but then the backtracking has to be explicitly implemented.
Note: the constants are
calls variable is useful for analysing the results.
Now let’s elaborate the abstract functions2. The
fit_2pieces() function is simple.
Two pieces “fit” if the sum of the touching sides is 0. So it is written as:
Pieces are “rotated” 90° counter-clockwise by subtracting a value from the index. The indexing behaviour of Python conveniently wraps around with negative numbers,
so something like
piece1[0 - 1] is evaluated as
fit_position() function is not as straightforward. Each piece needs to fit with the previous piece, but the sides which are compared are different at each position.
Also, at positions 3, 5, 7 and 8, two sides on the piece need to be checked.
I found it was easiest to hardcode all this. This is what it looks like, after some refactoring:
This code retrieves the following solutions in 0.07 seconds:
These are the only two solutions for this puzzle.
In total, it calls
solve 588 times. The final
calls list looks like:
[1, 9, 43, 165, 70, 151, 68, 60, 19, 2].
So, 19 times the code placed 8 pieces, but only 2 of those times was it able to progress to a solution.
This is tough puzzle to give to someone. Certainly, as an engineer and as a programmer, I would approach this problem with an algorithmic way of mind. However, when I was younger, I was not thinking along those lines at all. I wonder though, if with guidance, it is worthwhile showing this to a young student. It would teach them the value of algorithms. They do not need to know how to code - it is possible to implement this algorithm by hand. Although it took me 1.5 hours, I was able to do this recently. Part of the reason it took so long was because I was trying to be clever and skip steps. But once I followed the simple rules with the physical stack in my hand, I got into a rhythm and it went quickly. In any case, it is definitely a worthwhile coding exercise in backtracking and recursion.
At first, I thought this was a mistake. However after failing to find solutions for several other puzzles on that website, I think this was deliberate. This is a crude form of copyright protection - it prevents you from copying the puzzles (from this website at least). ↩
The original paper does not describe the abstract functions at all. ↩