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

 

Logo


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

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: 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.

License Agreements, Terms of Use, Privacy Policy. .

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