# Backtracking in The Nursery – How to Solve a “Legespiel”

I recently stumbled upon a type of game that is not uncommon here in Germany. It is called a “Legespiel”, which can be translated into english as “tile-based game”. The very 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 Legespiel “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.

Here is one of my son’s almost solutions. Note the card in the lower right corner. – All pictures of the cards: © Verlag Friedrich Oetinger, Hamburg.

# 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! · 49 = 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

Niccolo Bambini: Ariadne and Theseus (enhanced using waifu2x based on the version on 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 “Legespiel” 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 Legespiel, 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:

All pictures of the cards: © Verlag Friedrich Oetinger, Hamburg.

Some other Legespiele 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 “Legespiel” “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 Legespiele on the (German) market, which present almost the same problem for players to solve:

You are interested in the solutions for a very specific Legespiel? The Legespiel-Solver can be adapted to solve any game of this type. Please refer to the file “Readme.txt” for details.

Please leave a comment if you have any questions about the software or if you have solved another Legespiel with it. Also, I would be very interested to know if these types of games are played outside the German-speaking area and what they are called there.

### Related Posts

This entry was posted in Algorithms, Legespiel-Solver, Open Source on November 30, 2014.