How a Computer Makes a Puzzle With Exactly One Answer
Press "New puzzle" and a fresh board appears in an instant. Behind that button, a small program is setting itself homework and marking it.
Most of the puzzles on GridPencil have a button marked "New puzzle". Press it and you get a board nobody has ever seen before. There is no library of ready-made puzzles behind it. The puzzle is built in your browser, in a fraction of a second, at the moment you ask.
That raises a fair question. How does a program make a puzzle that is guaranteed to be solvable, and for some puzzles guaranteed to have only one answer? There are three main approaches, and all three are at work in the notebook.
Method one: start from the answer
The safest way to make a solvable puzzle is to begin with it already solved and then mess it up.
Pipe Twist works like this. The program first draws a complete network that connects all twenty-five squares to the centre. Then it spins every piece to a random angle. Whatever you are looking at, you know it can be put back, because it started out finished.
Untangle does the same. It begins with a drawing that has no crossing lines, then drags the dots onto a circle to tangle it. You do not have to find the original picture. Any layout without crossings counts, but the original proves that at least one exists.
Method two: make it, then test it
For some puzzles you cannot easily start from the answer, so the program makes a random board and then tries to solve it. If it fails, the board is thrown away and another is made. You only ever see the ones that pass.
Water Sort is tested this way. So is Ice Slide, with a twist: the program does not just check that the flag can be reached, it finds the shortest route. Boards that can be solved in fewer than five slides are rejected as too easy, and the best figure is shown beside the puzzle so you have something to aim for.
How does a program find a shortest route? By being thorough in the right order. It lists every square reachable in one slide, then every square reachable in two, and so on, never visiting the same square twice. The first time the flag turns up, the count at that moment is the answer. It is the same idea a map application uses, on a very small map.
Method three: remove clues until just before it breaks
Sudoku needs more care, because a sudoku has to have exactly one solution. Two would mean that somewhere you must guess.
The usual recipe goes like this. Fill a complete, valid grid. Then take digits away one at a time. After each removal, run a solver that counts solutions. If there is still exactly one, carry on. If there are now two, put that digit back and try removing a different one.
The counting solver is simple and stubborn. It finds an empty square, tries each digit that does not clash, and moves on to the next square. When it hits a dead end it backs up and tries the next option. Programmers call this backtracking, and it is exactly what you do by hand in Eight Queens when you shift the last queen along and carry on.
Sudoku Six and Binary Grid both leave you fourteen given squares on a six by six grid. That number is a choice. Leave more and the puzzle solves itself. Leave fewer and it becomes hard to guarantee a single answer.
Why uniqueness matters to you
It changes how you can think. In a puzzle with one solution, an argument such as "if this square were a 4, that row would have nowhere left for its 2" is solid. You can trust it. In a puzzle with two solutions the same reasoning can stall, because both are consistent with everything you can see.
So when a puzzle page here says "exactly one solution", it is a promise about your experience: you will never need to guess.
What a program cannot judge
A program can prove a puzzle is solvable. It is much worse at knowing whether the puzzle is any fun. Hand-made puzzles, of the kind good magazines print, often have a theme or a clever bottleneck that a random generator would never plan.
What generated puzzles offer in return is supply. You will not run out. And for short HTML5 games played in a spare few minutes, a fresh, fair board every time is worth a great deal.
Try spotting it
Next time you play, press "New puzzle" a few times before you start and watch what stays the same. The number of givens, the size of the board, the minimum number of slides. Those constants are the fingerprints of the method that made it.