How to generate Slither Link puzzles
A tasty treat for algorithm nerds
Slither link is one of my favorite pen and paper puzzles. It’s in the same genre as Sudoku, but I prefer it because it has a smoother difficulty curve as you solve it. You start with a grid of numbers like this:
The goal is to draw lines between the dots to form a single connected loop with no branches. Each numbered cell must have that many lines surrounding it.
I’ve wanted to write my own slither link game for a while, but generating a good slither link puzzle is tricky. The problem has been percolating in the back of my head, and every now and then I pull it out and look at the problem again.
Broadly speaking, the algorithm works like this:
- Generate the shape of the solution’s line.
- Count the number of lines around each cell, and set the cell to this number. These numbers form a valid slither link puzzle, but it is far too easy. We need to leave some cells blank to increase the difficulty.
- Remove numbers one-by-one, at random, making sure that there is only ever one valid solution to the puzzle (our original line). If removing a number means there is more than one solution, add it back and try a different number. Keep doing this until we’ve run out of numbers to remove, or stop early to make an easier puzzle.
Step 3 is relatively straightforward to implement, and step 2 is trivial. The part I’ve been stuck on is generating a good line for step 1. We want a line that wiggles its way around the grid, without intersecting itself, and that covers most of the grid. We don’t want large patches of empty space.
I recently figured out an efficient way of generating this line, during a bout of 2020-related insomnia.
There’s a variation of the puzzle where instead of forming a loop, you have an inlet on one side and an outlet on the other, and you have to form a single unbroken line joining them. The inlet and outlet are provided along with the numbers, as part of the puzzle. I’ll be focusing on that variant, because that’s what I want in my game, but this algorithm could easily be adapted to generate loop based puzzles.
So the problem is to generate a wiggly line that traces from one side of the grid to the other, doesn’t branch or intersect with itself, and covers most of the grid.
Prior attempts
I initially tried restating “generate a wiggly line” in a more formal and mathematical way: “From the set of all possible lines from one side of a grid to the other, randomly choose one line.
This should work pretty well, because there are many more wiggly lines than straight ones (analogously to entropy). If selecting in this way generates too many bad lines, we can always add a heuristic wiggliness check at the end, and choose a different line if it’s no good.
Unfortunately this got me nowhere. I have no idea how to select a random line from that gargantuan set.
Another approach I tried was divide and conquer. Maybe we could divide the grid into 4 quadrants, and recursively run our algorithm on them.
The hard part about this approach is the entry and exit points of each quadrant. The final wiggly line can enter and exit each quadrant multiple times, and those points all have to meet up with the other quadrants. So maybe we have to randomly choose points along the boundaries, and pass those to the recursive call as the entry and exit points.
The probability distribution of the total number of these points would need to be carefully chosen. Too many or too few crossings, and the boundaries of the quadrants would be visible in the final line. There’s probably a way of deriving this distribution mathematically, but it’s not obvious to me. We can’t just randomly choose X% of the boundary edges to draw lines in, because not all rows and columns have the same number of lines.
Moreover, we have to ensure that when all those entry and exit points are joined up, they form a single unbroken line. So we would have to pair up the entry and exit points of each quadrant somehow, in a way that is random, but logically satisfiable. Overall, the divide and conquer approach felt a bit too fiddly, and I wasn’t sure I could make it work.
The last approach I tried is probably the most obvious. Start with a straight line from one side to the other, then repeatedly deform it until it’s wiggly enough.
The problem with this approach is that we have to be careful to make sure we don’t introduce crossings when wiggling the line, and make sure that each deformation makes it more wiggly by some heuristic. Naively implementing each of these checks would take O(n) for an x by y grid with n=x*y cells. So the overall algorithm would take at least O(n²), assuming we need O(n) deformations on average to reach peak wiggliness.
A better approach
I was stuck on this deformation approach for a while, but I recently figured out a way of verifying that a particular deformation of the line will increase wiggliness, and won’t cause line crossings, in O(1) time.
The basic idea is simple. Instead of trying to generate a line from one side to the other, we think of it as a cell coloring problem. The goal is to divide the grid into two orthogonally contiguous regions of color, and the final line is the boundary of these regions. Our initial straight line state is translated into having the top half of the grid in one color, and the bottom half in the other color:
Once all the deformations are done, we should end up with something like this:
The final line is the boundary of these regions:
One important thing to note about this reformulation is that the constraint that the final line is a single continuous line with no branches or crossings is preserved. This constraint is exactly the same as the constraint that the two regions of color are orthogonally contiguous. As long as we don’t have patches of color floating by themselves, the boundary between the colors will form a single unbroken line from one side to the other.
Each deformation of the line is just a matter of flipping the color of one of the cells adjacent to the boundary. So the question is how do we make sure that flipping the color of a particular cell will increase the wiggliness of the boundary, without separating either of the colored regions?
The wiggliness check involves counting how many of the orthogonally adjacent cells have the same color as the cell we are considering flipping.
Let’s look at these cases starting from the left. If all of the surrounding cells are the same color as the cell, flipping its color would leave a disconnected patch of color. If 3 are the same color and one is different, flipping it increases wiggliness, so this would be a valid flip. If 2 adjacent cells are the same color, flipping it doesn’t change anything. If only 1 adjacent cell is the same color, flipping it would reduce wiggliness. And on the right, we should never see a case where all 4 adjacent cells are a different color to our candidate cell, because that would mean we already have a disconnected patch of color.
Actually the 2 adjacent cells case is a little more complicated. It may or may not change the wiggliness, depending on the color of the 4 diagonally adjacent cells.
The first case shouldn’t happen, and the last case would cause disconnected regions. Of the remaining cases, the only one that increases wiggliness is the case where 3 of the diagonal cells are a different color than the candidate cell. There are also cases where it’s not enough to just count the number of same and differently colored cells, but they’re all covered by the region connectivity check below.
These rules don’t quite work at the edges of the grid, so we have to modify the check a bit: the wiggliness increases if the number of same colored orthogonally adjacent cells is greater than the number of differently colored ones, or if they’re the same but the number of same colored diagonally adjacent cells is greater than the number of differently colored ones. That’s a mouthful, so to summarize in pseudocode:
same(O) > diff(O) or (same(O) == diff(O) and same(D) > diff(D))
Where O is the set of orthogonally adjacent cells, and D is the diagonally adjacent cells.
The connectivity check turns out to be pretty simple. Let’s look at some examples where flipping the candidate cell color would cause disconnected regions.
All these cases have one thing in common. As we walk around the 8 adjacent cells, we count the number of times the color flips. If the total is 4 or more, then flipping the candidate cell color will cause disconnected regions.
Again, the edges of the grid are a little more complicated. Let num(O) be the number of orthogonally adjacent cells, then the connectivity check is:
flips > 2 * num(O) − 4
So putting all this together, we start with a grid with the top half one color and the bottom half the other color. We repeatedly choose a random cell on the border between the colors, by maintaining an array of candidate coordinates and using pop-swap to remove a random element. If that cell meets the aforementioned conditions we flip its color and add its neighbors to the array. Repeat until the array is empty. Overall this algorithm is (roughly) O(n), where n is the number of cells in the grid.
Refining the results
This algorithm generates pretty good results, but there’s still a bit of a remnant of the initial conditions. It can be hard to see from just one example, but after looking at a lot of them, I noticed that there’s a lot of long vertical lines in these patterns. It’s a bit more obvious when you rotate it and compare it to the original.
My guess as to why this happens is that the initial state being divided in half horizontally means that all the valid deformations early in the process are vertical, and this biases the results.
The most straightforward fix is to randomize the initial conditions somehow. I tried initializing it to a sine wave pattern, and this eliminated a lot of the visible bias. But I wanted to truly randomize it, because the bias was still there, even if I couldn’t easily see it. I considered coming up with a variation on simplex noise, but making that obey the connectedness rule would be a pain.
If only we had an algorithm that generates wiggly regions obeying the connectedness rule. Oh… right.
We can run the algorithm on a smaller grid, then scale it up to get the initial conditions for the larger grid. Doing this recursively until we reach a minimum size (I’m stopping at 4 by 4) is still O(n), because the geometric series converges to a multiple of n.
The results look great, and 50 by 50 grids like this are generated essentially instantly. Definitely fast enough for use in my game.
There’s a small variation I’m still experimenting with. The second half of the wiggliness check generates extremely stable diagonal lines. Unlike most other structures, these can’t easily be messed with by further deformations, because this rule considers any deformation away from the diagonal as decreasing wiggliness. So these immutable diagonals can enclose small regions, leading to gaps in the puzzle. You can see some of these in the image above. They’re not necessarily a problem, because all the gaps are very small, but disabling that half of the check gets rid of them:
I don’t have a strong opinion about which is better. I’ll see how each of them feels to play.
Generating the numbers
The next step is to convert the grid into numbers, by simply counting how many orthogonally adjacent cells have a different color to a given cell.
Almost all the numbers at the edge of the puzzle are either 0 or 1, which is not how the puzzle is supposed to be. What’s going on?
Well since the outermost cells of the colored grid are all the same color in the top and bottom halves, the line this algorithm generates will never touch the edge of the grid other than at the entrance and exit. So we actually have to generate a grid 2 cells wider and taller than our desired size, and then discard the outline.
For this single line variant of slither link, we also need to keep track of the entrance and exit points, and present them to the player as part of the puzzle.
Then we choose cells at random (by iterating through a shuffled list of all the cell positions) remove their number, and see if the puzzle is still solvable. So the key to the second phase of the algorithm is writing a fast slither link solver.
The solver
A slither link solver is essentially the same as a sudoku solver, and this sort of thing is a common challenge when learning to code. In the worst case, this is an NP-complete problem. But these puzzles wouldn’t be much fun to solve if the only approach was the brute-force of trying every possible solution. A fun puzzle is one where applying logical rules will get us most (if not all) of the way to a solution, and the amount of brute-force needed will be minimal.
The approach I usually take for these sorts of puzzles, and related problems like scheduling workers on a roster with various constraints, is backtracking with some hand crafted rules to speed it up.
We can start by writing a solver that reasons about the puzzle similarly to a human, building in all the rules we can think of. For example, when there are two lines coming out of a vertex, we know the other two directions can’t be lines, so we can cross them out.
We can write many rules like this, and make quite a lot of progress. Eventually though, we’ll to run into a puzzle that cannot be solved by these hard coded rules alone. That’s where backtracking comes in.
The idea of backtracking is that when you get stuck, you choose an arbitrary empty line segment and try filling it in. Then you continue running your solver, and if it reports that there’s no solution, you undo all the changes you made and try putting a cross there instead.
Backtracking alone will solve the puzzle, but it’s essentially trying every combination of lines and crosses, so it will be impractically slow. Our hard coded logic rules are essentially just a way of speeding up that search.
In this case, we don’t really care about finding the solution (we know what the solution is), we care about answering the question “does this puzzle have exactly one solution?”. So we just have to keep a count of how many solutions we find, and we can stop the search early if we find more than one. The solution counting algorithm looks like this:
- Apply all the hard coded logical rules repeatedly until they stop making progress.
- Check if the puzzle is solved, is unfinished but still ok, or is violating the rules (eg too many lines around a number, or branches in the line).
- If the puzzle is solved or violating the rules, undo all the changes made by step 1, then return 1 if it’s solved, otherwise return 0.
- Otherwise, find the first edge that isn’t filled or crossed, and fill it. Also, let n = 0 (this variable counts the number of solutions).
- Recursively call this algorithm, and add its result to n.
- Undo the change from step 4.
- If n > 1, jump to step 9, since we don’t care about exactly how many solutions there are, just whether there’s more than 1.
- Try setting that same edge to a cross, then repeat steps 5–7 again.
- Undo all the changes made by the entire algorithm.
- Return n.
This algorithm is a bit fiddly to implement. Handling the undos efficiently requires maintaining a stack of all the modifications made to the puzzle. The logic rules need to push their changes to the stack, and return the total number of changes made, so we can pop and undo the correct amount.
Speeding it up
This algorithm works, but it’s a bit slow. The main issue is that recursive backtracking often needs to go very deep to find a solution. One way to fix this is to add more hard coded rules. I have a set of puzzles I use for benchmarking, and it’s a fun coding challenge to implement more rules and watch the total number of recursive backtracks decrease. But there’s a limit to what this approach can achieve.
The recursive depth is a pretty good measure of the difficulty of the puzzle. Since I’m not really interested in making maximally difficult puzzles for my game, there are a few techniques that can drastically speed up puzzle generation by making the puzzles easier.
One technique is to limit the maximum recursion depth. If the solver reaches this limit, we give up and assume there are multiple solutions to the puzzle. I have the maximum depth set to 10 at the moment, and it seems to generate moderately difficult puzzles. I’ll have to tune this parameter more through playtesting though.
Looking once again at the top layer of the algorithm, which removes numbers from the grid, we can apply a similar giving up approach here. Each time removing a number causes the puzzle to have multiple solutions, we increment a counter. When that counter reaches a limit, we give up and return the finished puzzle. This limit needs to be tuned based on the size of the puzzle. I currently have it set to x * y / 10.
There’s an even more powerful technique that can be applied during number removal. Typically, the first 20–40% of the removals will be successful. So for a grid with 100 cells, we could blindly remove 20 random cell numbers, and check if the puzzle still has only one solution. If it does, we try removing another 20 numbers, otherwise we add back 10. We can apply binary search to this problem.
Using our shuffled list of cell positions, we choose its midpoint, and iterate through all the positions up to that midpoint, clearing the corresponding cells. If the resulting puzzle has more than one solution, we set the upper bound of our search to the midpoint, otherwise we set the lower bound to this point. Rinse and repeat, until the bounds meet. To implement this efficiently, we should only clear and refill the cells that need to change each iteration, rather than fully resetting the grid each time. This binary search is well worth it. Removing the first 30% of a 30 by 30 grid naively would need to run the solver 270 times, but with a binary search we only need to run it 10 times.
Final results
Using the latest version of the algorithm, a 10 by 10 puzzle can be generated in about 10 to 30 seconds, a 20 by 20 in about 3 to 5 minutes, and a 30 by 30 in about 10 to 20 minutes. These are all good enough for my game, because while the player is solving one puzzle, I can generate the next one in the background. I’ll keep trying to make it faster though, because implementing more rules is a really fun exercise, and has a significant impact on the generation time. The faster the solver runs, the harder I can make the puzzles.
