11
$\begingroup$

It is known that there are a minimum of 17 clues needed to create a proper sudoku puzzle.

For how many puzzles is 17 sufficient? From the history of the minimal proof, I gather that there are multiple puzzles for which 17 clues are enough for a unique solution. Is 17 enough to specify every proper sudoku puzzle? Just a class or a few classes of puzzles?

Improve this question
$\endgroup$
6
  • $\begingroup$ What is a unique solution? Please give an example. $\endgroup$
    – martijnn2008
    May 16, 2014 at 17:14
  • $\begingroup$ @martijnn2008 A unique sudoku puzzle refers to one which has one and only one solution. I'll edit it to include the proper terms. $\endgroup$
    – user20
    May 16, 2014 at 17:29
  • $\begingroup$ @Emracool I though so too, but Kevin is using the term 'unique solution' wrong. And Is 17 enough to uniquely specify every sudoku? still doesnt make sense, because you now say with 17 clues you can make every sudoku solution you want. $\endgroup$
    – martijnn2008
    May 16, 2014 at 17:30
  • $\begingroup$ @martijnn2008 perhaps I phrased it (/ was thinking about it) backwards. What I'm really after is does every valid sudoku board have a 17-clue starting board that uniquely specifies that puzzle. $\endgroup$
    – Kevin
    May 16, 2014 at 17:31
  • $\begingroup$ @Kevin The term you're looking for is "proper sudoku," which I've edited in for you. $\endgroup$
    – user20
    May 16, 2014 at 17:31

2 Answers 2

Reset to default
5
$\begingroup$

While not a perfect answer the, following is from the same paper that proved the non-existence of 16 clue sudoku. The paper can be read at http://arxiv.org/pdf/1201.0749v2.pdf

For several years now, whenever people send Gordon Royle (see the second item in Section 2.1) a list of 17-clue puzzles, there are usually not too many new puzzles. One correspondent sent 700 puzzles, and it turned out that only 33 were new. Assuming that both Royle and this correspondent had drawn their puzzles at random from the universe of all 17-clue puzzles, Ed Russell computed the maximum likelihood estimate for the size of the universe to be approximately 34,550 at a time at which Royle’s list contained around 33,000 puzzles [26]. In retrospect this is an underestimate; nevertheless we may infer that the 49,151 puzzles on the most recent version of Royle’s list must be almost all the 17-clue puzzles in existence.

Improve this answer
$\endgroup$
2
$\begingroup$

As of today, 49,157 17-clue non equivalent puzzles have been found.
Studies are in progress to list all of them.
Adding "non equivalent" is important : actually, for each puzzle one can relabel the digits, permute rows, columns, bands, stacks and rotate the board.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ There might not be the full number of equivalent puzzles, because some of those operations might give the same puzzle. $\endgroup$
    – JiK
    Aug 14, 2018 at 19:00
  • 1
    $\begingroup$ @JiK . Thanks! You are right, there are "automorphic " puzzles P, such that it exists a transformation f such that f(P) = P. I edited my answer accordingly. $\endgroup$
    – JPF
    Aug 14, 2018 at 20:21
  • $\begingroup$ Interestingly, 49,157 is a prime number. Even more interestingly, another was found in 2019, giving a total of 49,158, shattering some belief that 49,157 was all there was. In any case, an exhaustive search is well underway and it's possible a conclusion will be reached by 2023 if the computers keep calculating steadily. $\endgroup$
    – bryc
    Jun 4, 2021 at 4:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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