Publications with Xinyu (Cindy) Zhang
Sudoku grids that require many clues.
D. Eppstein and
X. Zhang.
arXiv:2607.05728.
26th Japan Conference on Discrete and Computational Geometry, Graphs,
and Games, Tokyo, 2026, to appear.
We study the minimum number of clues needed in sudoku, for a solution matrix that maximizes this minimum number. We show that, for most \(n^2\times n^2\) sudoku puzzles, all but a logarithmic fraction of the squares must be clues, and we apply this to the worst-case complexity of solving these problems. We also show how to pack many independent Latin squares into a sudoku puzzle, and we use this construction to construct many \(9\times 9\) puzzles that require 18 clues and \(16\times 16\) puzzles that require 80 clues.