Sudoku Grids That Require Many Clues
arXiv:2607.057286.5
Predicted impact top 47% in DM · last 90 daysOriginality Synthesis-oriented
AI Analysis
Provides theoretical lower bounds on clue requirements for sudoku puzzles, relevant to complexity theory and puzzle design.
The paper proves that most filled-in sudoku grids require almost all cells to be filled as clues, and constructs specific 9×9 and 16×16 grids needing 18 and 80 clues respectively.
Motivated by worst-case algorithmic time bounds for solving sudoku, we prove that a majority of filled-in $n^2\times n^2$ sudoku grids require all but a logarithmic fraction of cells to be filled by clues. For $9\times 9$ and $16\times 16$ sudoku, we construct grids that require $18$ clues and $80$ clues.