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?

$\endgroup$
  • $\begingroup$ What is a unique solution? Please give an example. $\endgroup$ – martijnn2008 May 16 '14 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$ – Aza May 16 '14 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 '14 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 '14 at 17:31
  • $\begingroup$ @Kevin The term you're looking for is "proper sudoku," which I've edited in for you. $\endgroup$ – Aza May 16 '14 at 17:31
4
$\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.

$\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.

$\endgroup$
  • $\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 '18 at 19:00
  • $\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 '18 at 20:21

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.