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.
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.
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,
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!