11

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?

Kevin
  • 2,770
  • 4
  • 22
  • 39
  • What is a unique solution? Please give an example. – martijnn2008 May 16 '14 at 17:14
  • @martijnn2008 A unique sudoku puzzle refers to one which has one and only one solution. I'll edit it to include the proper terms. –  May 16 '14 at 17:29
  • @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. – martijnn2008 May 16 '14 at 17:30
  • @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. – Kevin May 16 '14 at 17:31
  • @Kevin The term you're looking for is "proper sudoku," which I've edited in for you. –  May 16 '14 at 17:31
  • Slight terminology note: I'd think the term minimal should be synonymous with proper, specifically meaning that no clue can be deleted without resulting in a puzzle with more than one solution. If you want to know how many boards have a 17-clue solution, at least in the mathematics literature it would be more accurate to use minimum than minimal. – Logan M May 17 '14 at 05:15

2 Answers2

5

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.

Kevin
  • 1,273
  • 2
  • 11
  • 22
kaine
  • 9,102
  • 27
  • 71
2

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.

JPF
  • 226
  • 2
  • 2
  • 1
    There might not be the full number of equivalent puzzles, because some of those operations might give the same puzzle. – JiK Aug 14 '18 at 19:00
  • 1
    @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. – JPF Aug 14 '18 at 20:21
  • 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. – bryc Jun 04 '21 at 04:32