|
%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
| 