scan solution grids for 17 clues as of blue

Programs which generate, solve, and analyze Sudoku puzzles

Re: scan solution grids for 17 clues as of blue

Postby champagne » Sat Aug 13, 2022 6:50 am

Leren wrote: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.
champagne
2017 Supporter
 
Posts: 7336
Joined: 02 August 2007
Location: France Brittany

Re: scan solution grids for 17 clues as of blue

Postby Leren » Sat Aug 13, 2022 7:26 am

Hi Serg,

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

Leren
Leren
 
Posts: 5020
Joined: 03 June 2012

Re: scan solution grids for 17 clues as of blue

Postby eleven » Wed Aug 24, 2022 7:02 pm

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 !
eleven
 
Posts: 3082
Joined: 10 February 2008

Re: scan solution grids for 17 clues as of blue

Postby coloin » Fri Aug 26, 2022 11:49 am

champagne wrote: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]
coloin
 
Posts: 2365
Joined: 05 May 2005
Location: Devon

Re: scan solution grids for 17 clues as of blue

Postby champagne » Fri Aug 26, 2022 2:20 pm

coloin wrote:
champagne wrote: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.
champagne
2017 Supporter
 
Posts: 7336
Joined: 02 August 2007
Location: France Brittany

Re: scan solution grids for 17 clues as of blue

Postby dobrichev » Mon Aug 29, 2022 9:33 pm

champagne wrote:We have 49158 ED sudokus, not one more.

Well done Gerard, you did it! Congratulations to Blue and all the other contributors.
dobrichev
2016 Supporter
 
Posts: 1845
Joined: 24 May 2010

Re: scan solution grids for 17 clues as of blue

Postby shortcipher » Sun Sep 18, 2022 1:46 am

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?
shortcipher
 
Posts: 2
Joined: 18 September 2022

Re: scan solution grids for 17 clues as of blue

Postby champagne » Sun Sep 18, 2022 6:03 am

shortcipher wrote: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.
champagne
2017 Supporter
 
Posts: 7336
Joined: 02 August 2007
Location: France Brittany

Re: scan solution grids for 17 clues as of blue

Postby shortcipher » Mon Sep 19, 2022 12:46 am

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.
shortcipher
 
Posts: 2
Joined: 18 September 2022

Re: scan solution grids for 17 clues as of blue

Postby sultan vinegar 2 » Tue Dec 05, 2023 8:31 am

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?
sultan vinegar 2
 
Posts: 12
Joined: 23 February 2018

Re: scan solution grids for 17 clues as of blue

Postby Hajime » Fri Dec 08, 2023 5:05 pm

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...
User avatar
Hajime
 
Posts: 1348
Joined: 20 April 2018
Location: Fryslân

Re: scan solution grids for 17 clues as of blue

Postby JPF » Fri Dec 08, 2023 11:53 pm

sultan vinegar 2 wrote: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
JPF
2017 Supporter
 
Posts: 6123
Joined: 06 December 2005
Location: Paris, France

Previous

Return to Software