Review: A Pencil-and-Paper Algorithm for Solving Sudoku Puzzles
Summary
J. F. Crook develops a systematic pencil-and-paper algorithm for solving Sudoku, including difficult puzzles that cannot be completed by immediately obvious placements. The paper begins with the standard 9 x 9 board and treats each empty cell as a set of possible digits, called its markup. Rather than presenting a loose collection of puzzle tricks, Crook organizes logical elimination around one mathematical idea: the preemptive set.
A preemptive set consists of m candidate digits restricted to exactly m cells within a row, column, or box. Because those digits must occupy those cells in some order, they cannot appear elsewhere in the same range. Crook formalizes this observation as the Occupancy Theorem. Familiar Sudoku patterns such as naked pairs, triples, hidden pairs, and hidden triples can all be interpreted through this framework. The result is a unified explanation of why candidate eliminations are valid rather than a list of unrelated solving rules.
The proposed procedure has four main stages. First, the solver enters every forced number that follows directly from the clues. Second, all remaining cells are marked with their possible candidates. Third, the solver repeatedly identifies preemptive sets in rows, columns, and boxes and removes impossible candidates. This process continues until the puzzle is solved or no further logical reduction is available. If the puzzle stalls, the solver selects a cell with a small candidate set, makes a provisional choice, and continues the same elimination process. A contradiction causes the solver to backtrack and try another branch. In computational terms, the paper combines constraint propagation with a search tree, but presents both in a form that can be followed by hand.
Two worked examples illustrate the method. One puzzle is completed entirely through preemptive-set reasoning. A more difficult puzzle requires a provisional choice and the construction of search paths. Crook recommends branching on a preemptive pair when possible, or otherwise choosing a cell with the fewest candidates. This is closely related to the minimum-remaining-values heuristic used in modern constraint-satisfaction solvers.
The paper also interprets Sudoku as a graph-coloring problem. Each cell is a vertex, digits are colors, and cells sharing a row, column, or box must receive different colors. This perspective connects puzzle completion and uniqueness to chromatic-polynomial ideas.
The paper is important because it bridges human logical reasoning and general algorithmic search. Its terminology is not identical to that used by every modern Sudoku solver, and its procedure may still require guessing for hard instances. Nevertheless, the preemptive-set framework provides a clear mathematical foundation for candidate-based solving and explains how logical propagation can reduce the amount of backtracking required.
Sitan Chen
If you have the same hobbies, you can contact me.
