A198297 Minimum number of clues needed to uniquely solve an n^2 X n^2 sudoku.
0, 0, 4, 17
Offset: 0
Examples
Every 4 X 4 board with 3 filled squares either cannot be completed, or can be completed in two or more ways. But with 4 filled squares it is possible: +-----+-----+ | . 1 | 2 . | | . . | . . | +-----+-----+ | . . | 1 . | | . . | . 3 | +-----+-----+ Thus a(2) = 4. The following 16 X 16 puzzle with 55 clues has a unique solution: +------------+------------+------------+------------+ | . . . 9 | . . . . | . 3 . . | . . . 2 | | . . . . |15 . . 12 |16 . . . | . 10 . 8 | | . 4 . 5 | . . . . | . 9 . . | . . . . | | . . . . | . . . 10 | . . 13 . | . . . 15 | +------------+------------+------------+------------+ | . . 8 . | . . . . | . . . . | . . . 16 | | . . . . | . 5 . . | . . . . | . . . . | |10 . 15 . | . . . . | . . . . | . . . 12 | | . . . . | . 13 9 . | . 4 . . | . . 7 . | +------------+------------+------------+------------+ | . . . . |16 . . 14 | . . . . | . . . . | | . 5 . 4 | . . . . | . 7 . 11 | 1 13 9 . | | . . . 3 | . . . . | . 1 . . | 5 . 4 . | | . . . . |10 . . 15 | . . . . | . . . . | +------------+------------+------------+------------+ |15 . 16 . | . . . . | 8 . 10 . | . . . 14 | | . . . . | . 1 4 . | . . . . | 2 . 5 . | | 8 . . . | . . . . |12 . 16 . | . . . . | | . . . . | . 9 7 3 | . . . . | . . 1 . | +------------+------------+------------+------------+ Thus a(4) <= 55.
Links
- James Grime and Brady Haran, 17 and sudoku clues, Numberphile video (2012).
- Agnes M. Herzberg, and M. Ram Murty. Sudoku squares and chromatic polynomials, Notices of the AMS 54, no. 6 (2007): 708-717.
- Gary McGuire, Bastian Tugemann, and Gilles Civario, There is no 16-clue sudoku: solving the sudoku minimum number of clues problem via hitting set enumeration, arXiv:1201.0749 [cs.DS], 2012-2013.
- Gary McGuire, Bastian Tugemann, and Gilles Civario, There is no 16-clue Sudoku: solving the Sudoku minimum number of clues problem via hitting set enumeration, Experimental Mathematics 23.2 (2014): 190-217.
- The New Sudoku Players' Forum, Minimum givens on larger puzzles.
- Wikipedia, Mathematics of Sudoku.
Comments