Episode 15 — Puzzle Design & Mathematics
When a sudoku has two solutions, it is broken. When a lateral thinking puzzle has twenty, it is brilliant. The difference between a flaw and a feature depends on what the puzzle is actually trying to do.
The Core Question
Every puzzle designer makes a foundational choice before setting a single clue or constraint: how many solutions should the finished puzzle have? For some puzzle types, the answer is so obvious it feels like a law of nature. A sudoku grid has exactly one valid completion — that is not a stylistic preference but a definitional requirement. A classic two-move chess problem (White to play and mate in 2) must have exactly one first move that forces mate regardless of Black's response; any alternative first move that also mates constitutes what problemists call a "cook," a fatal defect that disqualifies the composition from any respectable tournament.
But then consider the other end of the spectrum. A murder mystery dinner party puzzle is expected to have exactly one solution — the murderer, the weapon, the room — that players converge on through clue analysis. Yet the "black story" genre of lateral thinking puzzles, in which players ask yes/no questions to reconstruct a strange scenario, may have dozens of equally valid reconstructions, all logically consistent with the minimal information provided. The designer's intention is precisely that ambiguity. The puzzle does not fail for having multiple solutions; it succeeds because of them.
Between these poles lies most of the interesting territory in puzzle design. This episode maps that territory: what uniqueness means in constraint-satisfaction puzzles, why it matters so much for some genres and so little for others, how designers test for it, and what happens when a puzzle that should have one solution turns out to have two.
The Solution Spectrum
Puzzles distribute across a spectrum defined by how many solutions their designers intend — and what happens when that number deviates from the intention.
The distribution is not random. Puzzles that score and rank solvers — competitions, timed challenges, published crosswords — almost universally demand unique solutions, because fairness requires a single correct answer. Puzzles that focus on process rather than outcome — collaborative storytelling, group brainstorming, educational lateral thinking exercises — often thrive on multiplicity. The puzzle form and the intended use case are deeply intertwined.
Constraint Satisfaction
Sudoku is the most widely-played uniqueness-dependent puzzle in the world, with approximately 100 million daily solvers across all platforms. Understanding how uniqueness is achieved (and destroyed) in sudoku illuminates the design principles that apply across all constraint-satisfaction puzzles.
A minimal 17-clue sudoku — the proven minimum for guaranteed unique solutions
The McGuire proof required approximately 7.1 million CPU hours distributed across a computing cluster and took almost a year to complete. It is one of the most computationally intensive results in recreational mathematics. The underlying method — showing that no 16-clue configuration admits a unique solution by checking all possible 16-clue configurations — is a tour de force of algorithmic search with a result of genuine mathematical elegance: there is a sharp threshold at 17.
Chess Composition
In chess problem composition, a "cook" is an unintended solution — a first move other than the intended key that also achieves the stipulated goal (mate in N, stalemate, selfmate, etc.). A cooked problem is considered unsound and is disqualified from publication and competition. The term has been in use since the 1840s and remains the most feared word in any chess composer's vocabulary.
What makes cooks so insidious is that they are often beautiful. A cook is not a bad move — it is frequently an elegant alternative that the composer simply failed to anticipate. The problem's soundness depends not on the quality of the intended solution but on the absence of any equally valid alternative. This creates an interesting asymmetry: a composer can spend months crafting a perfect intended solution, only to have the whole composition invalidated by a simple, overlooked first move that also mates.
One key move achieves the goal. The depth of the solution rewards careful study. The puzzle is sound.
An alternative first move also achieves mate. The intended solution loses its meaning. The problem is unsound.
Modern chess composers use computer verification software — primarily Popeye and Gustav — that exhaustively checks for cooks before submission. But even with software assistance, cooks occasionally reach publication. The most famous historical case is the Brentano Cook Affair of the 1870s, when Wilhelm Brentano, a prolific German chess problemist, had dozens of compositions found cooked in a single edition of a problem collection, an embarrassment that effectively ended his publishing career.
"Finding a cook in your own problem before it is published is a relief. Finding a cook in someone else's published problem is a service to the community. Finding a cook in your own published problem is the worst day of a composer's year."
— Tim Krabbe, chess journalist and problem composerGenre Comparison
Different puzzle genres have very different relationships with solution uniqueness. The table below maps the landscape.
| Puzzle Type | Solution Expectation | Failure Mode | Test Method |
|---|---|---|---|
| Sudoku | Exactly 1 | Multiple solutions: "broken" puzzle | Backtracking solver, count = 1 |
| Crossword (US style) | Exactly 1 | Rogue answer at crossing: unchecked square | Grid-check software, all crossings |
| Chess Problem | Exactly 1 | Cook: unintended solution | Popeye/Gustav exhaustive search |
| Nonogram (Picross) | Exactly 1 | Ambiguous grid: two valid pictures | Constraint propagation solver |
| Logic Grid Puzzle | Exactly 1 | Undertermined: multiple valid assignments | SAT solver or manual verification |
| Lateral Thinking | Many Valid | Too constrained: only one reading possible | Playtest with multiple groups |
| Situation Puzzle | Many Valid | No coherent reading possible at all | Designer playtests for coherence |
| Find-All-Solutions Math | Set of N > 1 | Missed solutions or overcounting | Proof or exhaustive enumeration |
The genre-specific norms are not arbitrary. They derive from what each puzzle type is actually trying to deliver. A crossword that has two valid answers at a crossing leaves one solver feeling vindicated and another feeling cheated — both rightly. A lateral thinking puzzle that has only one valid reconstruction has failed to generate the exploratory conversation that is its entire point. Uniqueness is a design specification, not a universal virtue.
When Multiple Solutions Are the Feature
The cases where multiple solutions are not a bug but the entire purpose deserve closer examination, because they illuminate something important about what puzzles are actually for.
Edward de Bono's situation puzzles are designed to be explored collaboratively, with groups generating multiple coherent explanations through yes/no questioning. The multiplicity of valid readings is what makes the discussion rich.
Martin Gardner's columns regularly posed problems where the reveal was that a seemingly constrained scenario had far more solutions than expected. The surprise of abundance was the payoff.
Architecture and product design schools deliberately use open-ended "puzzle briefs" with multiple valid solutions to train students to evaluate and defend design decisions rather than discover a single correct answer.
Story seed puzzles ("Begin with a character who has lost something that never existed") are puzzles with infinite valid solutions. The multiplicity is the mechanism that forces creative divergence.
The common thread across all these intentionally multiple-solution cases is that the value lies not in the answer but in the process of generation, evaluation, and selection. The puzzle is not a quiz with a concealed answer; it is a constraint that activates a creative or analytical search process. In this context, uniqueness would destroy rather than enhance the experience.
Frequently Asked Questions
A well-formed sudoku puzzle is defined to have exactly one solution. Research by Felgenhauer and Jarvis established that there are 6,670,903,752,021,072,936,960 valid completed sudoku grids, but not all partial grids derived from these constitute valid puzzles. A partial grid has a unique solution only if each given clue is genuinely necessary — removing any single clue creates a puzzle with at least two solutions. The minimum number of clues required to guarantee a unique solution was proved to be 17 in 2012 by Gary McGuire and colleagues.
In puzzle design, a degenerate puzzle is one that has more solutions than its design intends. For single-solution puzzles like sudoku or logic puzzles, any number of solutions greater than one is degenerate. For chess problems, a sound problem has exactly one first move that achieves the stipulated goal; a "cook" renders the problem degenerate. Degenerate puzzles are problematic because they undermine the solving experience: if the solver finds solution A, they cannot know whether solution B exists.
In crossword construction, a rogue solution occurs when a crossing pattern of letters admits two or more valid English words. For example, if both ORATE and IRATE fit the crossing letters at a particular position, the puzzle has a rogue solution at that square. Skilled constructors and editors check for rogues systematically, and reputable puzzle outlets reject puzzles containing them. Rogue solutions are particularly insidious because solvers who arrive at the "wrong" correct answer have no way of knowing they have gone off-track.
Yes — several respected puzzle genres embrace ambiguity as a design feature. Open-ended lateral thinking puzzles (like Edward de Bono's situation puzzles) explicitly have multiple valid explanations, with the solving process being a structured dialogue rather than a single-answer hunt. Some mathematical puzzles ask for "all solutions" rather than "the solution." Martin Gardner's recreational mathematics column frequently posed problems with surprisingly large or infinite solution sets as the reveal. And some educational puzzle designers deliberately create variants with constrained multiple-solution sets for classroom purposes.
The method depends on puzzle type. For constraint-satisfaction puzzles like sudoku or nonograms, designers typically use backtracking solvers that enumerate all solutions up to a fixed limit — if the count exceeds one, the puzzle fails the uniqueness test. For chess problems, dedicated proof-number search algorithms exhaustively verify that no cook exists. For crosswords, grid-checking software tests every crossing for alternative valid words. Some constructors use SAT solvers which can be adapted to puzzle-specific constraint languages and scale to much larger puzzle instances.
Further Reading
The original paper proving the 17-clue minimum. Available on arXiv. The methodology section is readable even without a deep background in computer science.
The 2006 paper that calculated the exact count of valid completed sudoku grids. A fascinating exercise in combinatorics and group theory.
Complete glossary of chess problem terminology, including an extended entry on cooks, duals, and other forms of unsoundness. Essential for anyone curious about chess composition.
When you encounter a crossword with a possible rogue solution, A2Z Word Finder's pattern-matching tools help you identify all valid words that fit a given letter pattern.
Related Episodes
Listener Q&A
It does happen, occasionally. Major outlets like the Times and the Guardian have published sudoku puzzles that turned out to be ambiguous — typically discovered by eagle-eyed solvers who found a second valid completion. The response varies: some publications issue corrections in the next edition and accept both completions as valid for that day's competition. Some quietly update their digital versions. And some — before the era of routine algorithmic checking — had no mechanism for correction at all. The move to algorithm-generated sudoku (which most major publishers now use exclusively) has made this much rarer, since generation software can be set to verify uniqueness before output. Hand-crafted puzzles from the early sudoku boom era were much more likely to have errors.
There is actually a rare variant of crossword construction called a "quantum crossword" or "Schrödinger crossword" that intentionally plays with this. In a Schrödinger square, a single cell admits two valid letters — both of which, in their respective crossing answers, are correct. The most famous example appeared in the 1996 US election day NYT crossword, where one clue was "Lead story in tomorrow's newspaper (with 'elected')" and the answer worked as either CLINTON or BOBDOLE depending on how you filled one ambiguous square. Will Shortz has occasionally published puzzles where a single cell is genuinely ambiguous by design, with the theme being that the ambiguity is the gimmick. It is extremely rare, requires enormous constructing skill, and is entirely different from the accidental rogue solutions that editors work to eliminate.
For constraint-satisfaction puzzle types — sudoku, nonograms, logic grids — algorithmic generation already outperforms human construction on the dimension of uniqueness verification. A computer can generate a million valid unique sudoku puzzles in the time it takes a human to make a cup of coffee, and each one is guaranteed unique. The harder question is whether algorithmic generation can match human construction on aesthetic quality — things like the elegance of the solution path, the surprise of the break-in, and the satisfaction of the endgame. For sudoku, the answer is mostly yes. For crosswords, where the interaction between grid design, theme selection, fill quality, and clue craft involves layers of judgment that are deeply culturally embedded, the answer is much less clear. Computers can verify uniqueness; they have a harder time caring about beauty.