I recently stumbled upon a game that is not uncommon here in Germany. It is called Scramble Squares (in German “Legespiel”). The specific type of tile-based game, this post will be about, has quadratic cards with pictures on them. These pictures must be arranged to a square in such a way that the pictures on each card fit together with the pictures of the cards around it. I will show how complex this problem is and also present an algorithm to solve it.

I stumbled upon the Scramble Squares puzzle “Pippi Langstrumpf Absolut knifflig!” by accident. My 4 year old son liked it, because it had pictures of Pippi Longstocking on it and it looked like something he could play on his own – quietly. The goal of the game is to arrange all nine cards in a square in such a way that the pictures of Pippi Longstocking, her monkey and her horse fit together on the edges.

After I had been watching my son for a while, I realised that the name of the game “Absolut knifflig!” (roughly translated: “Absolutely tricky!”) was well deserved. He sometimes managed to arrange 8 cards correctly, but then he always hit a dead end. My son thought that somebody was playing a trick on him and got a bit angry. Still he continued playing – grumbling from time to time.

The Analysis

On the back of the box it said: “There is more than one solution.” Great, now I had to know! How many solutions were there? How could one find all solutions using software? What would be a good algorithm to do that? Would simply trying all ways in which the 9 cards could be positioned and rotated be a sensible option? That would be…

(9 · 4) · (8 · 4) · (7 · 4) · (6 · 4) · (5 · 4) · (4 · 4) · (3 · 4) · (2 · 4) · (1 · 4) = 9! · 4⁹ = 95,126,814,720

which is almost 100 billion possibilities. This is around the number of neurons in the human brain. Still, given enough time and a modern PC, it would be doable. But there is a far more efficient way using the principal of Ariadne’s thread or backtracking.

“According to Greek mythology, Ariadne’s thread was a present from Ariadne, daughter of King Minos, to Theseus. Using this thread, he found his way through the labyrinth to the Minotaur.” – tanslated from Wikipedia

So apparently Theseus found his way through the labyrinth, because he had a very long thread, which he kept unwinding while walking. Because he did that, he could always find his way back after every dead end (thus “Backtracking”). Of course, he also could see where he had not been before. Whereever there was no thread lying on the ground.

Theseus was able to search through the labyrinth systematically using his thread. Our Scramble Squares puzzle also represents a labyrinth. Although our search space is a bit more abstract. The starting point would be the empty playing field. From there we have to decide, which card we want to start with and how to rotate it. Thus, for this first step there are 36 (=9·4) possibilities. This would be equivalient to having 36 different possible paths at the first branch-off in a labyrinth.

No matter what we decide, for the second card, which we will put to the right of the first card (we always work from left to right, top to bottom) there are again several possibilities. But there are not as many possibilities as in the first step. Of course there are only 8 cards left, which would result in 32 (=8·4) possibilities (see calculation above), but there are even fewer possibilities, because the first and the second card have to fit together. Because of that, searching systematically with backtracking will result in trying far fewer possibilities to find all solutions than the above mentioned 100 billion.

The Algorithm

First we need an algorithm for the following subproblem: After n steps (n is between 0 and 8 in this case) calculate all possibilities for the (n+1)th step.

Starting with the empty or a partially filled playing field and given the remaining cards this algorithm has to find all possibilities to add one more card in a way that the result still fits together:

To find all solutions of our Scramble Squares puzzle, we start with the empty playing field. Then we look for all possibilities for the first card (as mentioned above for the first card there are 36), after that for the second, for the third and so. We do this by calling the method findAllSolutions recursively (see line 11 below) until we have gathered all possibilities where we were able to fill the whole playing field with all 9 cards (see line 7 and 8 below). These possibilities are the solutions.

But where is the thread here? Ariadne’s Thread is hidden in our recursive method-calls (basically in the call stack). Everytime we make a recursive method call, we unwind a bit of the thread and everytime we return solutions – no matter if the list is empty or not – we do some backtracking along the thread.

The Solutions

The algorithm presented here, implemented in java and running on a standard PC, will find all 148 solutions within a few milliseconds by systematically trying 220,760 possibilities instead of the above mentioned 95,126,814,720.

But, in fact, only a quarter (37) of these 148 solutions are of any interest, because the others can be formed by rotating the whole playing field by 90°, 180° and 270°. One could say: The 148 solutions can be divided into 37 equivalence classes with 4 members each. But enough with the math lingo! The following shows all 37 original solutions:

Some other Scramble Squares puzzles have duplicate cards in them, which further reduces the number of original solution. There is a separate article on the topic called “Solving Knifflidiffels“.

Playing With Arbitrary Degree of Difficulty

Because we know all solutions for the Scramble Squares puzzle “Absolut knifflig!”, we can now play the game with arbitrary degree of difficulty. To do that you arrange a few of the cards (e.g. 6 out of 9) to form a partial solution. The player now has to add the rest of the cards (3 in our example) correctly. As soon as this becomes too easy, you only give 5 cards and so on.

One more tip: This blog post can be viewed quite nicely on a smartphone and used as a cheat sheet.

The Software

The Java program “Legespiel-Solver” is free software and published under the permissive MIT-licence. The complete Eclipse-Project can be downloaded at Github. In order to display all results using the generated HTML files, you will need the nine pictures of the cards (see the second figure of this post) . These pictures are not part of the software package, as they are the intellectual property of the Oetinger Publishing Group.

Other Similar Games

There are many Scramble Squares puzzles on the market, which present almost the same problem for players to solve: see List of Scramble Squares Puzzles with Solutions

You are interested in the solutions for a very specific Scramble Squares puzzle? Using the Scramble Squares Solver Online you can use a simple user-interface to input the data of your game and display all solutions.

Please leave a comment if you have any questions about the software or if you have solved another Scramble Squares puzzle with it. Or even better: Submit your game using the Scramble Squares Solver Online.