A198297 Minimum number of clues needed to uniquely solve an n^2 X n^2 sudoku.

0, 0, 4, 17

Offset: 0

Author

Charles R Greathouse IV, Jan 26 2012

Keywords

• nonn
• hard
• bref

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

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.

Crossrefs

Cf. A107739, A372224.