The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A198297 Minimum number of clues needed to uniquely solve an n^2 X n^2 sudoku. 1
 0, 0, 4, 17 (list; graph; refs; listen; history; text; internal format)
 OFFSET 0,3 COMMENTS McGuire, Tugemann, & Civario find a(3) = 17. 15 <= a(4) <= 55. The upper bound is shown by the example below. - David Radcliffe, Dec 29 2019 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 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. EXAMPLE 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. CROSSREFS Cf. A107739. Sequence in context: A300315 A296628 A123234 * A116573 A195881 A264217 Adjacent sequences:  A198294 A198295 A198296 * A198298 A198299 A198300 KEYWORD nonn,hard,bref AUTHOR Charles R Greathouse IV, Jan 26 2012 STATUS approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified May 26 18:08 EDT 2020. Contains 334630 sequences. (Running on oeis4.)