How we make Numberlink puzzles

Numberlink puzzles are one of the harder puzzles to make - most of our puzzles require around 1000-1250 lines (not including tests) of C++ code, where Numberlink requires just over 1600. The problem wasn't so much in making a Numberlink puzzle, it was more in making Numberlink puzzles that are enjoyable to play.

Numberlink solver

The first step when making a puzzle generator is to make a solver for that puzzle. Normally for our puzzles, we prefer to implement a solver that will solve a puzzle in the same way a human player would do. Numberlink is a little unusual in that regard, how does a human person solve a Numberlink puzzle? I'm not sure! Writing a solver gives us insights in to what makes a puzzle easy or hard - you get to see the different techniques required for each difficulty level.

When I solve Numberlink puzzles, there isn't a method that I could teach to somebody else that could be used. I 'just' look at the puzzle, try some possible paths, rework some paths, and eventually (depending on the size of the puzzle), I find the solution. After a few puzzles you start to get a feel for where the paths might go. This isn't a method! Without a method that you can explain and write down (if you had to), there is no basis for implementing an algorithm.

In short, our Numberlink solver uses a classic backtracking algorithm. I won't go in to the details, but the backtracking algorithm we implemented was heavily inspired by the method detailed over here at github. Our backtracking algorithm continues after it has found a solution - I want to know if there is more than one solution to a puzzle, as I want all of my puzzles to have a unique solution.

Numberlink generator

Implementing a generator for a puzzle is always the tricky part. Writing a puzzle generator is always a little more subjective compared to a solver. In this case I wanted to be able make Numberlink puzzles that had a good distribution of length of links, i.e. I wanted every puzzle to have a combination of short links and long links. Additionally, I didn't want any links that were only 2 cells in length.

This is the full list of steps we go through,

1. Start from a completely blank grid.
2. Insert a random link with up to 6 'turns'. Why 6? I found this gave the puzzles with the attributes I wanted.
3. Take two cells, and create a link between these cells. The first cell will be a 'dead-end', if there is one available. We will pick a second cell making sure it is always reachable from the first. This line won't have any unnecessary turns, it is always the shortest path.
4. We take any small isolated areas of the puzzle (3 cells or smaller) that aren't part of a link yet, and try to extend existing links in to these cells.
5. We repeat steps 3 and 4 until our grid is completely covered.
6. We will now try to merge any links together. It's quite common at this point to find that one link will end right next to where another link starts. In this situation, we will merge these two links together.
7. At this point, if we have any links with only 2 cells, we throw the puzzle away and start again.
8. It's quite likely that we will have merged multiple links together in step 6, so we will re-number all of the links to make sure we aren't missing any numbers.

We now have a candidate solution. We will run a few checks to make sure that it satisfies our criteria,

• No loops. It's not common to have loops at this point, but it is possible that step 6 will give us loops.
• We have the right number of links. We take the total number of cells in the grid, multiply this by 0.85 to give us our lower bound for the number of links, and multiply by 1.15 to give us our upper bound for the number of links. If we have too many links, or not enough links, then we throw the puzzle away and start again.
• Only one solution! This is where the solver comes in very useful.

If all of these checks pass, then we have our puzzle!

This is quite a convoluted process to make a Numberlink puzzle. Most of our puzzle generators are quite straightforward in comparison. We didn't sit down and design this 'algorithm', it evolved. That is, we used an initial implementation, and looked at the puzzles it would make for us. We looked at the properties of the puzzles we liked, and the properties we didn't like. We modified the process to remove the properties that we didn't like until we had something that could make Numberlink puzzles that we would like to play. The above was the result!