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

0, 0, 4, 17

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

Table of n, a(n) for n=0..3.

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: A355550 A296628 A123234 * A368392 A116573 A195881

Adjacent sequences: A198294 A198295 A198296 * A198298 A198299 A198300

Keyword

nonn,hard,bref

Author

Charles R Greathouse IV, Jan 26 2012

Status

approved