16
$\begingroup$

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

Imagine there is a sudoku problem that has $n$ 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 $n$ possible with an example?

$\endgroup$
  • $\begingroup$ I'd guess that would be a hard problem. $\endgroup$ – Neil W Jan 17 '17 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 Jan 18 '17 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 Jan 18 '17 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 Jan 19 '17 at 4:40
4
$\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

$\endgroup$
  • $\begingroup$ interesting :) accepted this an answer then! $\endgroup$ – Oray Aug 12 '18 at 17:42
  • $\begingroup$ I see that both 40 clue puzzles us only 8 different clues. $\endgroup$ – Steve B Aug 13 '18 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 Aug 13 '18 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.

$\endgroup$
  • $\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 Jan 18 '17 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 Jan 18 '17 at 19:15
  • $\begingroup$ @Oray I'm glad there's something that exists. That's really all I wanted to see. :) $\endgroup$ – Ian MacDonald Jan 18 '17 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 Jan 18 '17 at 20:08
  • $\begingroup$ @JaapScherphuis very good job! It is valid answer! $\endgroup$ – Oray Jan 18 '17 at 20:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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