Finding the optimal solution for the numbers game

One of the games bored students play is the "Numbers Game," also known as "Take Tens" or in German, "Zahlenspiel." I once implemented it and wrote a solver to find the minimum number of steps required to solve the game. Here is the solution.

The Numbers Game is a game you normally play with sheets of paper. You write the numbers from 1 to 19 next to each other: 1 2 3 4 5 6 7 8 9. Afterwards, you write the numbers from 11 to 19 below, but so that you have nine columns and three rows:

You are allowed to strike through numbers that are next to each other if they are the same or add up to 10. Diagonals are not allowed, but the left/right neighbor of the outermost numbers are considered the right/left outermost of the column before/after. Thus, the 9 in the first row could be struck with the left 1 in the second row. After there are no possibilities left, one must write all remaining numbers below. This repeats until no numbers are left. To get a feeling, go to the implementation and play around a bit; I mark the possible matches: http://tn1ck.github.io/numbers-game/.

Three years ago, I wanted to learn React.js. The best way to learn a new library or framework is to build something with it. For me, this was the Numbers Game. Just head straight to http://tn1ck.github.io/numbers-game/, to play it.

The game itself is really hard to finish but also strangely addictive. When I started, I actually thought that by changing the used numbers range (in the original, it is 1 to 9), I could vary the difficulty, but 1 to 9 seems to be the sweet spot. 1 to 8 is really easy to solve, and 1 to 10 is super hard.

It’s frustrating to write a game that you haven’t solved yourself, and because I was curious about what the minimum number of steps would be, I wrote a backtracking solver.

I’m a fan of Clojure, so the solver is also written in it. The source code can be found here. It’s not perfect, but it’s straightforward and works. There is one magic number there; I put 74 there to filter out every solution that was bigger than that. Why? Because I knew that this was a valid solution and as I was using a depth first search, it could have run forever. My approach was to repeatedly run the depth first search and always decrease the upper bound until it wouldn’t find another solution with that upper bound. A breadth-first search would have also worked, but I already had the depth-first search implemented.

The code is old, and I just changed some things and commented here and there. I should rewrite it… but you know how it is, hard enough to find time to write this blog post. I will probably update the post then.

Anyway! Let’s look at the solution. What is the minimum number of steps needed? You need 34 steps at minimum to solve this game. Here are the steps, to be read as match: index1 & index2. So the first step would be to match the 1 on the left in the first row with the 1 on the left in the second row.

Here it is, a bit nicer as an image sequence:

previousnext

Step 1: 0 & 9

It feels kind of awesome to solve the game with these steps, as you normally take quite a long time to solve it.