The New Sudoku Players' Forum

[blue]

Game over

We have 49158 ED sudokus, not one more.

This has been a very long task done with a limited power.

The scan to extract all 17s having one band/stack with more than 6 clues started in the end of the summer 2017 and was finished in October 2018.

The scan for the distribution 566 656 (no stack over 6 clues) started after, with ” more or less” 20 cores of an I7 (processors available at this moment).

Mathimagics came in June 2020 to double the throughput and processed bands index 90 to 119 and 130 to 199. This was a difficult area and it has been a key contribution to the project.
Mith arrived later and took over the slice 120-129. Thanks to him as well.

Congratulations to all … especially to champagne

Too bad my estimate of 4-5 more remaining 17's, didn't pan out
I wish there had been at least one more, after #49158

Cheers,
Blue.

[m_b_metcalf]

The proof that there is no 16-clue puzzle was published in a journal. Are you contibutors to this new result thinking of doing the same?

Mike

[champagne]

Hi Mike,

No for several reasons :
This requires a good article commenting the process.
I wrote in the past several comments, but most of them are obsolete, and I don't have the English level to write an acceptable text for a publication, ( so far nobody proposed to work with me on such a boring task. )
I have no contact with any publishing support to receive such an article,
I am thinking, as I wrote earlier to close the task with a fresh code using the last findings done trying to break blue's DLL.

But you are right, this should be done.

My current project is to rewrite the code with fresh comments starting from the 18 clues extraction.
If anybody is interested, this could be a good opportunity to go in your direction.

My 18 clues code is not as good as blue's DLL, but much better than the code used to make the proof. I am very close to a beta test level with this code.
Switching form a one solution grid to the frame used by blue to make the scan is a big task that I am just starting in parallel with the test of the 18 clues code.

[coloin]

It’s impressive that “we” are even contemplating the 18C search !
Learning from the 17C search - it’s noteworthy that the division into two parts was successful .
The 665 search taking significantly more time than the 7xx and above.

Applying this to the 18C - maybe the 666 search is also problematically long - though the symmetry of the 18 clues may not require the vertical or horizontal band repetition ( factor 6 )

Whilst the 17search was ongoing I preferentially searched and found probably 2/3 of the 18C with box distribution 321222123 and 321213132 - and no new 17 was found .

It may well be that splitting that 666 search even more eg 222222222 would be worth doing.

Searching for 18s with maximum clues in diagonal boxes might also be a thought but increasing the search space by the similar factor of 6 might also be a stumbling block .

Given the precarious nature of our forum - the loss of the discussions in this thread would render any contribution to sudopedia for example much less meaningful.

[champagne]

It’s impressive that “we” are even contemplating the 18C search !
Learning from the 17C search - it’s noteworthy that the division into two parts was successful .
The 665 search taking significantly more time than the 7xx and above.

Hi coloin,

just a quick answer on a sample of 200 solution grids having 18s.
Using blue's DLL in enumeration mode (counting all 18), the process is covered below 10 seconds per solution grid this to compare to an average 3 seconds in the 16 clues proof.

Applying the scan "in the mood of the 17 clues search" (3 pass) we could be in a "per solution grid" similar to the average 16 clues.
And, as you write, the 666 case is very costly. Limiting the scan to 18s having at least one band with more than 6 clues, and finishing the task in vicinity mode, we should cover nearly all 18s and then, (relatively) very quickly

This is what I try to check

[Leren]

I've been "thinking" (IMHO )about this result and it seems to me that it is also another proof that no 16 clue puzzle exists. Is that right ?

Leren

[champagne]

I've been "thinking" (IMHO )about this result and it seems to me that it is also another proof that no 16 clue puzzle exists. Is that right ?

Leren

Right, but as wrote blue long ago, the first pass (no missing 17 with one band/stack with 7 or more clue) was enough to assess that no 16 exists.

A 16 clues must have at least one band and one stack with 6 clues.
Such a 16 clues would give non minimal 17s with at least one band stack with 7 or more clues.

The first pass (ended 4 years ago) did not produce any non minimal 17.

[coloin]

A 16 clue puzzle must have at least one band and one stack with 6 clues.

Quite a Eureka observation I remember …

Likewise every 18C must have at least 6 clues in at least one of the bands ( and indeed in at least one of the diagonal boxes]

If the 666 search is too problematic to even split into stages … here’s a thought
Searching for all 222222222 puzzles is definitely feasible on a -2+2 in one box (or 3+ level perhaps) and I would have to check again but I think there is “only” around 20 or so ED ways to have 2 clues in 3 diagonal boxes. ( will check this )

EDIT - there are slightly more than 20 ! - there are 64 - but in every 222222222 there will be 6 of these

Hidden Text: Show

Code: Select all

222000000 1.........2...................1.........2...................1.........2..........
222000000 1.........2...................3.........1...................1.........2..........
222000000 1.........2...................3.........1...................1.........4..........
222000000 1.........2...................3.........2...................1.........3..........
222000000 1.........2...................3.........2...................1.........4..........
222000000 1.........2...................3.........4...................1.........2..........
222000000 1.........2...................3.........4...................1.........5..........
222000000 1.........2...................3.........5...................4.........6..........
222000000 12............................12............................1.........2..........
222000000 12............................12............................1.........3..........
222000000 12............................12............................1........2...........
222000000 12............................12............................1........3...........
222000000 12............................12............................12...................
222000000 12............................12............................13...................
222000000 12............................2.........1...................1.........2..........
222000000 12............................2.........1...................1.........3..........
222000000 12............................2.........3...................1.........3..........
222000000 12............................2.........3...................1.........4..........
222000000 12............................2........1....................1.........2..........
222000000 12............................2........1....................1.........3..........
222000000 12............................2........3....................1.........3..........
222000000 12............................2........3....................1.........4..........
222000000 12............................23............................1.........3..........
222000000 12............................23............................1.........4..........
222000000 12............................23............................1........3...........
222000000 12............................23............................1........4...........
222000000 12............................23............................13...................
222000000 12............................3.........1...................1.........3..........
222000000 12............................3.........1...................1.........4..........
222000000 12............................3.........4...................1.........2..........
222000000 12............................3.........4...................1.........3..........
222000000 12............................3.........4...................1.........5..........
222000000 12............................3.........4...................1........2...........
222000000 12............................3.........4...................1........5...........
222000000 12............................3.........4...................12...................
222000000 12............................3.........4...................15...................
222000000 12............................3.........4...................3.........4..........
222000000 12............................3.........4...................3.........5..........
222000000 12............................3.........5...................4.........6..........
222000000 12............................3........1....................1.........2..........
222000000 12............................3........1....................1.........4..........
222000000 12............................3........4....................1.........2..........
222000000 12............................3........4....................1.........3..........
222000000 12............................3........4....................1.........5..........
222000000 12............................3........4....................12...................
222000000 12............................3........4....................15...................
222000000 12............................3........5....................4.........6..........
222000000 12............................31............................1.........2..........
222000000 12............................31............................1.........4..........
222000000 12............................31............................1........2...........
222000000 12............................31............................1........4...........
222000000 12............................31............................14...................
222000000 12............................34............................1.........2..........
222000000 12............................34............................1.........3..........
222000000 12............................34............................1.........5..........
222000000 12............................34............................1........2...........
222000000 12............................34............................1........3...........
222000000 12............................34............................1........5...........
222000000 12............................34............................12...................
222000000 12............................34............................13...................
222000000 12............................34............................15...................
222000000 12............................35............................4.........6..........
222000000 12............................35............................4........6...........
222000000 12............................35............................46...................

The range for maximum number of clues in at least one band is 6 to 11 (no 12plus6)
The range for maximum number of clues in at least one diagonal is 6-13 (almost certainly no 14plus4)

[Leren]

Another dumb question from me is what is the number of Absolutely Different 17 clue puzzles. ie do they all have the most common number of 1,218,998,108,160 morphs or is there a deficiency lurking in there.

Leren

[champagne]

If the 666 search is too problematic to even split into stages … here’s a thought
Searching for all 222222222 puzzles is definitely feasible on a -2+2 in one box (or 3+ level perhaps) and I would have to check again but I think there is “only” around 20 or so ED ways to have 2 clues in 3 diagonal boxes. ( will check this )

Hi coloin,
It is difficult to mix 2 strategies.
In the solution grid approach, one extract 18s using mainly unavoidable sets to reduce the scan. What you write is likely done in a different process. Adding constraints in the scan of solution grids does not help, it is an exhaustive, but very long process. (although the project of mathimagics to "flag" all solution grids having a 18 can be done with a short cut in the full scan)

The range for maximum number of clues in at least one band is 6 to 11 (no 12plus6)
The range for maximum number of clues in at least one diagonal is 6-13 (almost certainly no 14plus4)

In the 18 search, the most interesting is the minimum number of cues to have a valid 2 bands solution.
As you wrote, the minimum is 7 with only 4 cases. symmetry of your 6 to 11 for band 3,
In fact, most of the valid 2 bands will have 9-12 clues, with a sharp increase of the count when the number of clues grows.

[champagne]

Another dumb question from me is what is the number of Absolutely Different 17 clue puzzles. ie do they all have the most common number of 1,218,998,108,160 morphs or is there a deficiency lurking in there.

Leren

Take it reverse. If the morphs are not disjoints, a morph of the shared area would have 2 different canonical forms, just the opposite of the definition of a canonical form.
And I can't see any reason to have a non feasible morph for a given 17

[Leren]

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

[Serg]

Hi, Leren!

Another dumb question from me is what is the number of Absolutely Different 17 clue puzzles. ie do they all have the most common number of 1,218,998,108,160 morphs or is there a deficiency lurking in there.

There are 49158 essentially different (ED) 17-clue puzzles. None of them are automorphic (I checked it), so each ED 17-clue puzzle is representative of orbit - a set of 3,359,232 puzzles produced by applying 3,359,232 isomorphic transformations to the representative puzzle. Adding possible puzzles relabelling, we'll get 3,359,232 x 49,158 x 9! = 59,923,509,000,929,280 all different 17-clue puzzles.

Serg

[Edited. I corrected an error (as Leren pointed in his post) - my final result wasn't multiplied by 9!]

[Leren]

OK Serg, that's an answer, almost. You say you checked all the 49,158 grids and none is automorphic, none has an internal symmetry leading to a deficiency, which is thus zero for the whole set. But the Wikipedia article also says this (inter alia).

This is S3 ≀ S3 ≀ C2, a group of order 1,2962 × 2 = 3,359,232. Finally, the relabelling operations commute with the rearrangement operations, so the full sudoku (VPT) group is (S3 ≀ S3 ≀ C2) × S9 of order 1,218,998,108,160.

So my next stupid question is, have you left out the relabelling factor of 9!, so should the correct number be 165,133,126,656 or 165,133,126,656 x 9! ?

Leren

[Serg]

Hi, Leren!

OK Serg, that's an answer, almost. You say you checked all the grids and none is automorphic, none has an internal symmetry leading to a deficiency, which is thus zero for the whole set. But the Wikipedia article also says this (inter alia).

This is S3 ≀ S3 ≀ C2, a group of order 1,2962 × 2 = 3,359,232. Finally, the relabelling operations commute with the rearrangement operations, so the full sudoku (VPT) group is (S3 ≀ S3 ≀ C2) × S9 of order 1,218,998,108,160.

So my next stupid question is, have you left out the relabelling factor of 9!, so should the correct number be 165,133,126,656 or 165,133,126,656 x 9! ?

You and Wikipedia are right - I forgot multiply result by 9!. So, the right answer is "There are 165,133,126,656 x 9! = 59,923,509,000,929,280 all different 17-clue puzzles."

Serg