The New Sudoku Players' Forum

[champagne]

Hi Champagne,

I hope you did not mis-understand my use of the term "deficiency". It's not meant to be a criticism of your work, which is truly awesome, it's just a technical term to describe the number by which a grid has less than the most common number of 1,218,998,108,160 morphs. The term has been used, for example, by Mathimagics on the forum here and on Wikipedia here. If your answer is that the "deficiency" is 0 then the number of Absolutely Different puzzles should be exactly 1,218,998,108,160 x 49,158, I think.

Leren

Hi leren,
I confess that I did not pay that much care of the term "deficiency", but I understood that you had in mind a risk of overlapping in morph expansion of the 49158 ED 17.

[Leren]

Hi Serg,

Thanks for the clarification, and thanks for the full decimal expansion of the final number - 59,923,509,000,929,280.

Leren

[eleven]

Coming late, i just missed the end of this most ambitious, technically brilliant and amazingly fast - though long lasting - search.
So congratulations to champagne, also blue for his preliminary work (and for finding the last 17's), and Mathemagics and mith for their contributions !!
An absolute forum highlight !

[coloin]

It is difficult to mix 2 strategies.......the scan of solution grids is an exhaustive, but very long process....

You are right of course - prolific small vicinity searches will never be exhaustive...

Approx How long is it projected that the e 765,774,855 etc full scan would take ?

The 666 cases include only a few valid patterns that I have seen, benefiting from symmetry reductions

Code: Select all

222  321   321   330   222   222   510                                               
222  213   222   303   240   141   132                                               
222  132   123   033   204   303   023       maybe there are some more valid pattterns


411  510     
141  132     
114  024        I guess I have found 90 % of these !!


510  600  600
141  033  042
015  033  024    these do not have valid puzzles [to be formally proved]

[champagne]

It is difficult to mix 2 strategies.......the scan of solution grids is an exhaustive, but very long process....

You are right of course - prolific small vicinity searches will never be exhaustive...

Approx How long is it projected that the e 765,774,855 etc full scan would take ?

The 666 cases include only a few valid patterns that I have seen, benefiting from symmetry reductions ... [to be formally proved]

Hi coloin,

Not easy to answer here.
Being very optimistic, we could hope to get at the end a code running the 18 search as fast as the 17 search with the V6 code.

Taking this as granted, applying blues ' process, we have to scan exactly 610 163 364 pairs band1+band2 to search the 666/666 pattern. This is already below your count. Then, the expected scan could be faster than the pass2 (A+B) of the 17 search as only one of the 2 pass is needed here.

Your "proven invalid patterns" have to lead to a significant reduction of the count to be of interest.

Anyway, the first point is to write and test the code to be in line with the optimistic assumption. I am slowly re shaping the 17 search (here I have a good basis to test the code) . The switch from one band 3 (the current 18 search for a given solution grid) to several bands 3 attached has to be done carefully to keep the code efficient. The extension from the 17 to the 18 search will not be a big problem.

[dobrichev]

We have 49158 ED sudokus, not one more.

Well done Gerard, you did it! Congratulations to Blue and all the other contributors.

[shortcipher]

As a newbie, I'm not quite sure what is meant by an ED Sudoku.

Are you really saying that it is proven that there are no more 17-clue Sudoku puzzles than the known list of 49158?

[champagne]

As a newbie, I'm not quite sure what is meant by an ED Sudoku.

Are you really saying that it is proven that there are no more 17-clue Sudoku puzzles than the known list of 49158?

ED is a short for Essentially Different, meaning that this excludes all morphs of a given grid.
And then, yes, it is proven that there are no more 17-clue ED Sudoku puzzles than the known list of 49158.

The process applied is a full scan of all ED solution grids as for the proof that no 16 clues exists.

[shortcipher]

This result does not seem to be well-known outside this forum. Wikipedia's Mathematics of Sudoku just says "Many Sudokus have been found with 17 clues, although finding them is not a trivial task."
It's a pity no-one has volunteered to help champagne write this up for publication.

[sultan vinegar 2]

Wow, this has to go down as one of the all-time great results!

A couple of follow-up questions:

1) Do any of the 49158 share the same (isomorphic) completed grid, i.e. does any one complete grid have more than one way to make a 17-clue puzzle?

2) I don't suppose we know (or could run) stats on the numbers of those 49158 that are solvable by various techniques e.g. singles (including locked candidates), pairs (including X-Wing) etc. and if any aren't solvable by known techniques?

[Hajime]

The SER rated list of the 49158 17 clue puzzles is here
In a cross table summarized is looks like:

Code: Select all

SER   count
1.2   117
1.5   17116
1.7   2848
2.0   9524
2.3   505
2.5   208
2.6   9696
2.8   613
3.0   393
3.2   37
3.4   569
3.6   21
3.8   3
4.0   16
4.2   1117
4.4   40
4.5   330
4.6   151
4.7   7
4.8   1
5.0   2
5.2   4
5.6   579
5.7   37
5.8   1
6.2   4
6.5   20
6.6   2738
6.7   555
6.8   64
6.9   18
7.0   14
7.1   1024
7.2   478
7.3   79
7.4   2
7.6   48
7.7   37
7.8   42
7.9   6
8.2   6
8.3   56
8.4   9
8.5   13
8.8   2
8.9   5
9.0   2
9.1   1
Total   49158


Once I found on this forum the list of Sukaku/Sudoku Explainer with the methods:
http://forum.enjoysudoku.com/revision-of-se-ratings-and-resolution-rules-t36376-30.html?hilit=revision#p292744
You have to match the rating with the method yourself...

[JPF]

Do any of the 49158 share the same (isomorphic) completed grid, i.e. does any one complete grid have more than one way to make a 17-clue puzzle?

Yes, there are 2167 ed grids that have more than one puzzle with 17 clues.
The grid that has the most has 29 17s, is well-known, is called the strangely familiar grid and was found by Gordon Royle here

Code: Select all

SF  : 123456789456789123798231564234675918815943276967812435379164852582397641641528397
Minlex form


Here are the 29 puzzles:

Code: Select all

123456789456789123798231564234675918815943276967812435379164852582397641641528397
..3...7......8.1.....2..............81..4...........35.7....8....23.7......5...9.
..3.5........8.1.....2..............81..4...........35.7....8....23.7......5...9.
..3...7......8.1.....2..............81..4...........35.7....8....239.......5....7
..3...7......8.1.....2..............81..4...6.......35.7....8....23.7......5.....
..3..........8.1.....2.........7.9..81..4...........35.7....8....23........5....7
..3..........8.1.....2.........7....81..4...........35.7....8....23..6.....5....7
..3..........8.1.....2.........7....81..4...6.......35.7....8....23........5....7
..3.....9....8.1.....2.........7....81..4...........35.7....8....23........5....7
..3..........8.1.....2...6.....7....81..4...........35.7....8....23........5....7
..3..........8.1.....2.........7....81..4...........35.7....8....23........5...97
..3..........8.1.....2.........7....81..4.....6.....35.7....8....23........5....7
..3..........8.1...9.2.........7....81..4...........35.7....8....23........5....7
..3..........8.1.....2.........7....81..4...........35.7....8...823........5...9.
..3..........8.1.....2.........7....81..4...6.......35.7....8...823........5.....
..3........6.8.1.....2.........7....81..4...........35.7....8....23........5....7
..3..........8.1.....2.........7....81..4...........35.79...8....23........5....7
..3..........8.1.....2.........7....81..4....9......35.7....8....23........5....7
..3..........8.1.....2.........7....81..4...........35.7....8....23.....6..5....7
..3..........8.1.....2.........7....81.94...........35.7....8....23........5....7
..3..........8.1.....2........67....81..4...........35.7....8....23........5....7
..3..........8.1.....2.........7....81..4...........35.7....8....239.......5....7
..3..........8.1.....2.........7....81..4...........35.7..6.8....23........5....7
..3..........8.1.....2.........7....81..4...6.......35.7....8....23.7......5.....
..3..........8.1.....2.........7....81..4...6.......35.7....8....23........5.8...
..3..........8.1.....2.........7....81..4...........35.7....8....23........5.8.9.
..3..........8.1.....2.........7....81..4...........35.7....8....23.7......5...9.
..3..........8.1.....2..........5...81..4...........35.7....8....23.7......5...9.
..3..........891.....2.........7....81..4...........35.7....8....23........5....7
..3..6.......8.1.....2.........7....81..4...........35.7....8....23........5....7



Next is a grid with 20 puzzles, followed by one with 14 puzzles, one with 12 and so on.

Code: Select all

  N1        N2        N3                                                                              Example           
                                                                                                                       
  29         1        29    123456789456789123798231564234675918815943276967812435379164852582397641641528397           
  20         1        20    123456789456789123789132564264918357875324691931675248392861475547293816618547932           
  14         1        14    123456789457189263689237451275613948348975612961842537534798126712364895896521374           
  12         1        12    123456789456789123798132546215648937864973215937215468342567891581394672679821354           
  11         1        11    123456789456789123798231564237615948864973215915824637342567891581392476679148352           
   9         1         9    123456789456789123798132546237915468864273915915648237342567891581394672679821354           
   8         4        32    123456789457189326689237451261374895378591642594628137742865913836912574915743268           
   7         6        42    123456789456789132789231546247193658368574291591862374635928417812347965974615823           
   6        21       126    123456789456789123798213564247598631539167842861324975385641297672935418914872356           
   5        17        85    123456789456789123789123465238567941514932678697841352375618294861294537942375816           
   4        83       332    123456789456789132789132546245378961637591824891624357312945678568217493974863215           
   3       252       756    123456789457189236689372451248693517536741892971528643364817925795234168812965374           
   2      1778      3556    123456789456789123798213654261935847384172596579648231632597418845361972917824365           
   1     44134     44134    123456789457189236689372145245963871731528964968714523374295618516847392892631457           
         46301     49158                                                                                               
 

N1 is the number of 17s in the grid
N2 is the number of grids having N1 17s
N3 is the number of 17s in total : N3 = N1 x N2
an example in minlex form of a grid having N1 17s is given

JPF