Why good logic puzzles have exactly one solution
Every logic puzzle on Pebblewit has exactly one solution, and you can reach it by reasoning alone. That sounds like a technicality, but it is what makes a logic puzzle a logic puzzle, and keeping the promise takes more work than you might expect. Here is why it matters, how a computer checks it, how difficulty is measured, and why our arrow puzzles follow a different rule.
One answer means every step has a reason
When a puzzle has exactly one solution, every correct move is forced by the clues. That is a guarantee to the solver. If you are stuck, the puzzle is not asking you to gamble; there is a deduction you have not found yet. It also means every step has a reason you can put into words, which is what makes a hint that explains itself possible.
Puzzle makers take this seriously. In Sudoku, a puzzle with a single solution is called a proper puzzle. Andrew Stuart of the solving site SudokuWiki puts the other case bluntly: "A Sudoku with more than one solution is not a valid puzzle."
What goes wrong with two solutions
A small example shows the problem. On a 4 by 4 board there are only two ways to place four crowns with one in every row and every column and no two touching, and each is the mirror image of the other. Split the board into four 2 by 2 regions and both arrangements still fit, because each region gets exactly one crown.
A solver on the four-squares board soon reaches a point where nothing is forced. The rules allow both answers, so the only way to finish is to pick one, and nothing in the clues says which. Now move a single cell from one region to its neighbour, as on the right. The mirrored arrangement breaks, because one region would hold two crowns and another none. The board has one answer, and a solver can reach it step by step. That is puzzle design in miniature: shape the clues until exactly one answer survives.
How a computer proves there is only one
Checking a finished answer is easy. Proving that no other answer exists is harder, because you have to rule out every alternative. The standard tool is a backtracking search. Place something, a crown, a symbol or a step of a path, follow the consequences, and back up as soon as a rule breaks. Left to run, the search would list every solution.
For a uniqueness check you do not need the full list. You only need to know whether there is one solution or more than one, so the search can stop the moment it finds a second. That is how our checks work: count solutions, stop at two, and keep a board only if the count is exactly one. On the 4 by 4 example, the search finds both arrangements on the four-squares board and rejects it, then finds just one on the board beside it.
At a larger scale the same question can take enormous effort. In 2012 Gary McGuire, Bastian Tugemann and Gilles Civario announced an exhaustive computer search showing that there is no 16-clue Sudoku with a unique solution, so every proper Sudoku has at least 17 clues.
How difficulty is graded
A computer can prove uniqueness by brute force, but a person cannot, so uniqueness alone is not enough. A fair board must also be solvable by steps a human can see. In Crowns and Sun & Moon we check that with a second solver that works like a person. It knows a fixed list of techniques, ranked from simple to subtle, and always tries the simplest one that makes progress. A board's difficulty is the hardest technique it needs.
In Crowns, the simplest step is that a crown rules out its row, column, region and neighbours. Harder steps notice, for example, two regions confined to the same two rows. The hardest is a short what-if: assume a crown, follow simple steps for up to two more crowns, and rule the cell out if some row, column or region empties. The labels run from Gentle to Fiendish. Sun & Moon works the same way, from signs, pairs and sandwiches up to counting × pairs and, on the hardest boards, a short what-if, with labels from Gentle to Expert.
A Crowns or Sun & Moon board that the human-style solver cannot finish is never used, even if the brute-force search proves it has one answer. The hints in both games come from the same solver, which is why a hint can always give the reason for its move.
Pebble Path is graded differently. Its difficulty comes from how much searching the solver needs to prove that a board has one answer, and from how few numbers and walls the board gives you, with labels from Gentle to Expert. Its hints show the next stones of the answer rather than a reason.
How our boards are made
- Crowns places crowns that follow the rules, grows color regions around them, and then proves the result: exactly one solution, and finishable with the human techniques.
- Sun & Moon starts from a complete, valid grid. The generator reads a spread of = and × signs off the answer, then takes away givens and signs one at a time, keeping a removal only if exactly one solution remains and the human-style solver can still finish the board.
- Pebble Path starts from a random line that winds through every stone. The generator places numbers along it, and while another line still fits, it adds a number or a wall that rules that line out, until exactly one answer is left. Numbers and walls that do no work are then taken away, and when a board comes out harder than wanted, a few numbers are added along its longest stretches.
Arrow boards are a different kind of puzzle
Arrows Away does not have one solution, and it does not need one. An arrow can leave when every cell on the straight line from its head to the edge is empty, and sending an arrow away only ever frees space. So any free arrow may go at any time, and there are usually many orders that clear the board. Picture two arrows at opposite edges, each pointing straight off the board: either can go first, and neither order is wrong.
The promise here is a different one: no board can trap you. We build each board in the order it will be cleared, and every arrow is placed with a clear line out through space that earlier arrows will vacate. A wrong tap on a blocked arrow costs a heart, but it can never leave you in a dead end. Difficulty is measured in waves, the rounds in which every currently free arrow leaves: level 3 clears in 2 waves, level 380 takes 17.
When uniqueness becomes a clue
Some expert solvers use the promise itself as a clue. In Sudoku, the unique rectangle technique spots a pattern that would allow two solutions and rules it out, because published puzzles are known to have one. It is clever, but it only works if the setter kept the promise, and it leans on that promise rather than on the rules themselves. None of the techniques our solvers and hints use relies on it: every step they show follows from the rules of the game.
If you enjoy the history behind all this, read how the eight queens puzzle became a textbook example of backtracking, or try the habits in how to get better at logic puzzles.