Sudoku Grids That Require Many Clues

David Eppstein, Xinyu, Zhang

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 cel…