Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).
%I #43 Jan 16 2020 05:52:16
%S 0,0,4,17
%N Minimum number of clues needed to uniquely solve an n^2 X n^2 sudoku.
%C McGuire, Tugemann, & Civario find a(3) = 17.
%C 15 <= a(4) <= 55. The upper bound is shown by the example below. - _David Radcliffe_, Dec 29 2019
%C For all n, a(n) >= n^2 - 1. The solution to a puzzle with fewer solutions cannot be unique, because we can generate another solution by swapping two numbers that are not given as clues. - _David Radcliffe_, Dec 29 2019
%H James Grime and Brady Haran, <a href="https://youtu.be/MlyTq-xVkQE">17 and sudoku clues</a>, Numberphile video (2012).
%H Agnes M. Herzberg, and M. Ram Murty. <a href="https://www.ams.org/notices/200706/tx070600708p.pdf">Sudoku squares and chromatic polynomials</a>, Notices of the AMS 54, no. 6 (2007): 708-717.
%H Gary McGuire, Bastian Tugemann, and Gilles Civario, <a href="http://arxiv.org/abs/1201.0749">There is no 16-clue sudoku: solving the sudoku minimum number of clues problem via hitting set enumeration</a>, arXiv:1201.0749 [cs.DS], 2012-2013.
%H Gary McGuire, Bastian Tugemann, and Gilles Civario, <a href="https://doi.org/10.1080/10586458.2013.870056">There is no 16-clue Sudoku: solving the Sudoku minimum number of clues problem via hitting set enumeration</a>, Experimental Mathematics 23.2 (2014): 190-217.
%H The New Sudoku Players' Forum, <a href="http://forum.enjoysudoku.com/minimum-givens-on-larger-puzzles-t4801.html">Minimum givens on larger puzzles</a>.
%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Mathematics_of_Sudoku">Mathematics of Sudoku</a>.
%e 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:
%e +-----+-----+
%e | . 1 | 2 . |
%e | . . | . . |
%e +-----+-----+
%e | . . | 1 . |
%e | . . | . 3 |
%e +-----+-----+
%e Thus a(2) = 4.
%e The following 16 X 16 puzzle with 55 clues has a unique solution:
%e +------------+------------+------------+------------+
%e | . . . 9 | . . . . | . 3 . . | . . . 2 |
%e | . . . . |15 . . 12 |16 . . . | . 10 . 8 |
%e | . 4 . 5 | . . . . | . 9 . . | . . . . |
%e | . . . . | . . . 10 | . . 13 . | . . . 15 |
%e +------------+------------+------------+------------+
%e | . . 8 . | . . . . | . . . . | . . . 16 |
%e | . . . . | . 5 . . | . . . . | . . . . |
%e |10 . 15 . | . . . . | . . . . | . . . 12 |
%e | . . . . | . 13 9 . | . 4 . . | . . 7 . |
%e +------------+------------+------------+------------+
%e | . . . . |16 . . 14 | . . . . | . . . . |
%e | . 5 . 4 | . . . . | . 7 . 11 | 1 13 9 . |
%e | . . . 3 | . . . . | . 1 . . | 5 . 4 . |
%e | . . . . |10 . . 15 | . . . . | . . . . |
%e +------------+------------+------------+------------+
%e |15 . 16 . | . . . . | 8 . 10 . | . . . 14 |
%e | . . . . | . 1 4 . | . . . . | 2 . 5 . |
%e | 8 . . . | . . . . |12 . 16 . | . . . . |
%e | . . . . | . 9 7 3 | . . . . | . . 1 . |
%e +------------+------------+------------+------------+
%e Thus a(4) <= 55.
%Y Cf. A107739.
%K nonn,hard,bref
%O 0,3
%A _Charles R Greathouse IV_, Jan 26 2012