Review: Exact Method for Generating Strategy-Solvable Sudoku Clues
Summary
Kohei Nishikawa and Takahisa Toda study a Sudoku-generation problem that ordinary generators do not fully address: given a fixed pattern of clue positions and a specified collection of human-style strategies, can digits be assigned to those positions so that the resulting puzzle is solvable using only those strategies? This requirement is stronger than merely producing a valid puzzle with a unique solution. It also allows the constructor to control the geometry of the clues and the logical techniques needed to finish the puzzle.
The authors first give a rigorous definition of strategy-solvability. A Sudoku grid is represented as a sequence of states containing placed digits and remaining candidates. A strategy produces a valid transition from one state to another by placing a digit or eliminating candidates, while previously established information cannot be reversed. A puzzle is strategy-solvable if repeated applications of the allowed rules lead from the initial clues to a completed grid without speculative backtracking. The paper demonstrates the framework using three common techniques: naked singles, hidden singles, and locked candidates.
The central contribution is an exact constraint-satisfaction formulation of the generation problem. Variables encode the initial clues, candidate sets, placed digits, and transitions between solving states. The constraints enforce Sudoku consistency as well as the permitted logical deductions. A complete CSP solver can therefore return a suitable set of clue values when one exists, or eventually prove that a chosen pattern of clue positions cannot produce a puzzle solvable by the selected strategies. This guarantee distinguishes the method from generate-and-test systems, which may search indefinitely without showing that no solution exists.
To reduce the size of the formulation, the authors eliminate unnecessary variables associated with fixed clue cells and introduce an incremental procedure that increases the permitted number of solving steps only when needed. The same model can be adapted to investigate the minimum number of clues required for strategy-solvable Sudoku. The framework is largely independent of the particular strategies: additional techniques can be supported by encoding their logical conditions.
Experiments compare the exact method with an existing generate-and-test generator across randomly chosen clue patterns. The CSP approach terminates within one minute for many instances and behaves relatively consistently across moderate clue counts. Its main weakness appears near sparse puzzles: as the number of clues approaches 20, computation becomes much harder and can exceed the 600-second limit. The competing generator can sometimes find sparse examples faster, but its performance deteriorates for dense clue patterns and it cannot certify impossibility. The authors also test 17-clue patterns derived from known minimum Sudokus to examine unsolvability decisions.
This work is significant because it separates three concepts that are often conflated: having a valid completion, having a unique solution, and being solvable through a prescribed logical process. Its formal model creates a foundation for generating puzzles with controlled human-solving behavior and for studying the limits of particular strategy sets. The principal limitation is computational scalability for very small clue counts, which the authors identify as future work.
Sitan Chen
If you have the same hobbies, you can contact me.
