17
$\begingroup$

As most of you know, there is no Sudoku problem that has less than 17 starting clues, with one unique solution.

Imagine that there is a sudoku problem that has đť‘› number of starting clues with one unique solution, where removing any clue in the sudoku will make the puzzle non-unique (more than one answer).

What is the maximum value of đť‘› possible? Provide an example.

Improve this question
$\endgroup$
4
  • $\begingroup$ I'd guess that would be a hard problem. $\endgroup$
    – Neil W
    Commented Jan 17, 2017 at 22:51
  • 2
    $\begingroup$ This sounds like it could be made into a game actually. Two players start with an empty 9x9 sudoku board. Player take turns filling in numbers into the board. If a number is placed whereby a unique (partial or full) solution can be filled in, the other player can automatically fill all of those numbers in. The player who completes the last digit on the board wins. I'd imagine it'd be very nontrivial and no exact strategy however...but the thought process may be similar to the question posed here $\endgroup$
    – skyeriding
    Commented Jan 18, 2017 at 1:13
  • $\begingroup$ @skyeriding: The game you propose will not necessarily lead to the kinds of arrangements that the question is asking for (even if only considering the state just before the first move that allows some empty cells to be deduced). Moves later in the game may make the numbers placed in earlier moves redundant (i.e. deducable from the other numbers even if the board as a whole is not yet solvable). $\endgroup$
    – Jaap Scherphuis
    Commented Jan 18, 2017 at 13:47
  • $\begingroup$ @Jaap-Scherphuis: alternatively, modify the rules then such that whoever makes a move that allows the next player to deduce at least one number from the current setup - loses. This can avoid the redundancy... $\endgroup$
    – skyeriding
    Commented Jan 19, 2017 at 4:40

2 Answers 2

Reset to default
6
$\begingroup$

As of today, the maximum value of n is 40. Two puzzles are known.

This first puzzle was discovered by Mladen Dobrichev in March 2014.

    ...|...|...
    .12|.34|567
    .34|5.6|182
    ---+---+---
    ..1|.58|2.6
    ..8|6..|..1
    .2.|..7|.5.
    ---+---+---
    ..3|7.5|.28
    .8.|.6.|7..
    2.7|.83|615

See his post here

Improve this answer
$\endgroup$
3
  • $\begingroup$ interesting :) accepted this an answer then! $\endgroup$
    – Oray
    Commented Aug 12, 2018 at 17:42
  • $\begingroup$ I see that both 40 clue puzzles us only 8 different clues. $\endgroup$
    – Steve B
    Commented Aug 13, 2018 at 4:35
  • $\begingroup$ @Steve True. M. Dobrivhev found also 2650 39-clues minimal puzzles. Out of them only 63 (i.e. 2%) have 9 different digits. $\endgroup$
    – JPF
    Commented Aug 13, 2018 at 10:02
6
$\begingroup$

To get the ball rolling, here is an example of a Sudoku with 28 clues, and if my Sudoku generating program is right, none of them are redundant.

    .1.|.6.|7.9
    3..|...|...
    .9.|...|...
    ---+---+---
    7..|..8|4..
    .4.|1..|...
    9..|.4.|137
    ---+---+---
    .7.|.86|9..
    6..|5..|2..
    .2.|4.7|.61

This is the unique solution.

    412|863|759
    387|954|612
    596|721|384
    ---+---+---
    761|398|425
    243|175|896
    958|642|137
    ---+---+---
    175|286|943
    634|519|278
    829|437|561

My sudoku generator produces these only on the highest difficulty setting, which means that when you solve it you will have to some of the more advanced deduction techniques. There are likely to be unreducible sudokus with more clues, but which are solvable using only simple techniques.

Edit:

I have now looked through the book "Tak1ng Sud0ku Ser10usly", by Jason Rosenhouse and Laura Taalman. It says that the largest known number of clues is 39:

   7.5|6..|8.4
   64.|...|.27
   128|47.|.56
   ---+---+---
   251|.6.|..8
   ...|...|...
   8..|.5.|26.
   ---+---+---
   .8.|.3.|.7.
   5.2|74.|.83
   3.7|5..|4.2

It is not known (at least at the time of writing that book, 2011) whether there is an irreducible sudoku with 40 clues.

Improve this answer
$\endgroup$
6
  • $\begingroup$ While it's obviously super cumbersome and wouldn't format very well in a post, it would be interesting to see the 28 alternate endings for each of the removals. $\endgroup$
    – Ian MacDonald
    Commented Jan 18, 2017 at 18:53
  • $\begingroup$ @IanMacDonald thonky.com/sudoku/… Yes this is valid answer. You can remove one number, and you will see multiple answer for each... $\endgroup$
    – Oray
    Commented Jan 18, 2017 at 19:15
  • $\begingroup$ @Oray I'm glad there's something that exists. That's really all I wanted to see. :) $\endgroup$
    – Ian MacDonald
    Commented Jan 18, 2017 at 19:43
  • $\begingroup$ @Oray: I have now added one with 39 clues, taken from a book. I have not verified it. $\endgroup$
    – Jaap Scherphuis
    Commented Jan 18, 2017 at 20:08
  • $\begingroup$ @JaapScherphuis very good job! It is valid answer! $\endgroup$
    – Oray
    Commented Jan 18, 2017 at 20:19

Not the answer you're looking for? Browse other questions tagged or ask your own question.