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 » Fri Jul 27, 2018 2:50 pm

dobrichev wrote:aha, and instead of reporting when the new house is built, you preferred reporting when the ribbon cutting ceremony takes place ;)

Eh mladen, what do you want to prove here,

in a process lasting one year, spread over 21 cores and interrupted by power failures and windows out of control updates, each step must be carefully controlled before any release of information.
I store files generated by the process, and from time to time, I check. This is the most reliable process I found so far. :roll:
champagne
2017 Supporter
 
Posts: 6692
Joined: 02 August 2007
Location: France Brittany

Re: scan solution grids for 17 clues as of blue

Postby champagne » Fri Sep 28, 2018 7:42 am

New milestone

I hoped to close the phase 1 end of September, (17 clue puzzles with one band/stack having more than 6 clues)
Some more days will be needed

8 slices of 10 "band 1" are not yet closed, but not more than 15 " band 1" are not closed

so far same results, all known 17 come but no new appears
The final result should come in the next 2 weeks likely all 17 with this property are known
champagne
2017 Supporter
 
Posts: 6692
Joined: 02 August 2007
Location: France Brittany

Re: scan solution grids for 17 clues as of blue

Postby champagne » Thu Oct 11, 2018 1:12 pm

last milestone

12 "band1" are not yet covered
The final result is expected by the end of the next week.

uncovered band 1 are in the range 286 to 367

No new 17 with one band/stack having more than 6 clues appeared. This should be the final result
champagne
2017 Supporter
 
Posts: 6692
Joined: 02 August 2007
Location: France Brittany

Re: scan solution grids for 17 clues as of blue

Postby champagne » Sat Oct 20, 2018 5:53 am

Thanks to blue, this "one year project" is now closed. The final result is clear :

All 17 clues sudokus having one or more band/stack with >=7 clues are known.

By the way, this is another proof that no 16 clue exists, as explained blue (although a direct check would have been about 2.5 times faster)



As nobody came with free cycles; this has been established in about 13 months using my available power.

20 cores in average in three computers has been activated to run the verification.

intel 7700
intel 4770
amd 8320


The next step will be to check puzzles having no band/stack having >= 7 clues.

This should be done in 2 sub-phases to avoid the search of a 6+6 clues in bands 1+2.

The current code would require much more time than the covered case.
With my limited power, it would be too long, so, before starting the task, I intend to work once more on the code to try to cut in the run time.

In the best case, seen from to-day, the corresponding check could start in may 2019, when I am back from a winter long stay in the southern hemisphere.
champagne
2017 Supporter
 
Posts: 6692
Joined: 02 August 2007
Location: France Brittany

Re: scan solution grids for 17 clues as of blue

Postby coloin » Sun Oct 21, 2018 8:59 am

Well done !
To be clear you have checked for all 17-clue puzzles that have a band with 7 or more clues.
We now have to test for only puzzles which have at most 6 clues in any band.
This means that the clues in band count [in both directions] for all these is {6,6,5}{6,6,5}
coloin
 
Posts: 1738
Joined: 05 May 2005

Re: scan solution grids for 17 clues as of blue

Postby champagne » Sun Oct 21, 2018 9:52 am

coloin wrote:Well done !
To be clear you have checked for all 17-clue puzzles that have a band with 7 or more clues.
We now have to test for only puzzles which have at most 6 clues in any band.
This means that the clues in band count [in both directions] for all these is {6,6,5}{6,6,5}


Right, and the code to do this is ready, but as it is, it requires 2/3 times more run time (from memory) than the covered "phase 1", so it is worth to work a little more on it to try to be faster.
Among other possibilities of improvement

the control that 8 digits are there at the end (added in the current version of skmpp2)
findings done by "emerentius" in the brute force (to investigate)
The control that 4 digits are there in each pair of bands/stacks
...
champagne
2017 Supporter
 
Posts: 6692
Joined: 02 August 2007
Location: France Brittany

Re: scan solution grids for 17 clues as of blue

Postby dobrichev » Tue Oct 23, 2018 9:56 am

[withdrawn]
Last edited by dobrichev on Mon Oct 29, 2018 6:04 am, edited 1 time in total.
dobrichev
2016 Supporter
 
Posts: 1622
Joined: 24 May 2010

Re: scan solution grids for 17 clues as of blue

Postby champagne » Tue Oct 23, 2018 2:49 pm

Hi mladen,

dobrichev wrote:I still can't believe that all possible 17s in the vast of the search space have been found using only indirect methods.


I think that blue shared your view when he started the work on this topic, despite the fact that Gary McGuire wrote that likely most of them were there.
The chances to find a new 17 are bigger with the 6,6,5 distribution.


dobrichev wrote:Sadly no new 17s. Finding some would be a strong evidence for the correctness of the used methods.


knowing that some 17 with a band stack >= 7 clues have been often searched in both directions, about 45000 morphs have been searched and found.
Do you really think that finding no new 17 is weakening the results?

I can't give a probability to get the 45000 known and to miss another 17 puzzle, but it is surely much lower than to find no 16 clues and conclude that they don't exist.
champagne
2017 Supporter
 
Posts: 6692
Joined: 02 August 2007
Location: France Brittany

Re: scan solution grids for 17 clues as of blue

Postby dobrichev » Tue Oct 23, 2018 4:16 pm

[withdrawn]
Last edited by dobrichev on Mon Oct 29, 2018 6:04 am, edited 1 time in total.
dobrichev
2016 Supporter
 
Posts: 1622
Joined: 24 May 2010

Re: scan solution grids for 17 clues as of blue

Postby champagne » Tue Oct 23, 2018 8:14 pm

dobrichev wrote:To me a confirmation of non-existence of new puzzles is significant result too.

I have no reason to trust your algorithm and implementation but if you find new puzzle it is easy to be checked and confirmed.

Off-topic.
]3 years ago I spent a month or so in scanning the patterns with known 17s. Started from those with high number of puzzles to lower. After the initial code stabilization all known puzzles within the processed patterns were rediscovered. Several thousands of 17s, all double-checked.
This summer I ran the same code on another pattern and found that it doesn't work correctly. Fact


So I guess that you have doubts that no 16 clue exists.
It's always difficult to guarantee that the code is correct, but at least here, all known puzzles showed up
champagne
2017 Supporter
 
Posts: 6692
Joined: 02 August 2007
Location: France Brittany

Re: scan solution grids for 17 clues as of blue

Postby blue » Wed Oct 24, 2018 7:29 am

Hi champagne,

Nice work !

champagne wrote:
dobrichev wrote:I still can't believe that all possible 17s in the vast of the search space have been found using only indirect methods.

I think that blue shared your view when he started the work on this topic, despite the fact that Gary McGuire wrote that likely most of them were there.

In his "There is no 16-Clue Sudoku" paper, Gary wrote this:

(...); 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.

I hope that isn't what you were referring to.
I (still) doubt that even with 49,157 of them, we have all of them.

champagne wrote:The chances to find a new 17 are bigger with the 6,6,5 distribution.

I'm interested in why you say that.

For the known 17's, only ~25% of them have the double 6,6,5 distribution.
A naive person -- me, in particular -- might be tempted to conclude that any missing 17's, would be ~3 times more likely to be the other type ... with at least one band/stack, having 7+ clues.

Is it that you're confident that your code is correct, and you're sure that at this point, there is zero chance of finding any other type of new 17 ?
Did you have some other argument in mind ... say a year ago ?

Cheers,
Blue.
Last edited by blue on Wed Oct 24, 2018 7:45 am, edited 1 time in total.
blue
 
Posts: 701
Joined: 11 March 2013

Re: scan solution grids for 17 clues as of blue

Postby dobrichev » Wed Oct 24, 2018 7:37 am

[withdrawn]
Last edited by dobrichev on Mon Oct 29, 2018 6:05 am, edited 1 time in total.
dobrichev
2016 Supporter
 
Posts: 1622
Joined: 24 May 2010

Re: scan solution grids for 17 clues as of blue

Postby champagne » Wed Oct 24, 2018 10:26 am

Hi blue,


blue wrote:In his "There is no 16-Clue Sudoku" paper, Gary wrote this:

(...); 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.

I hope that isn't what you were referring to.
I (still) doubt that even with 49,157 of them, we have all of them.



I was referring to this. Frankly, between 49151 and 49157, I have no problem with the sentence
almost all the 17-clue puzzles
I knew that you expected new 17. They did not come in my phase 1 search.


blue wrote:
champagne wrote:The chances to find a new 17 are bigger with the 6,6,5 distribution.

I'm interested in why you say that.
For the known 17's, only ~25% of them have the double 6,6,5 distribution.
A naive person -- me, in particular -- might be tempted to conclude that any missing 17's, would be ~3 times more likely to be the other type ... with at least one band/stack, having 7+ clues.


What you say is correct. On the other side, we have more patterns to analyze with the 665 distribution (the reason why the process will be longer). This is the reason why my feeling would be in favor of a new 17 with this distribution. Another naive view. (a third naive view is that a new 17 did not come in the search done. The probability to have a code missing them remains low).


blue wrote:Is it that you're confident that your code is correct, and you're sure that at this point, there is zero chance of finding any other type of new 17 ?
Did you have some other argument in mind ... say a year ago ?


I fixed enough bugs in my life to stay cautious.

On the positive arguments, this code is derived from a process written by a reliable member of the forum :roll:
(and the code of the phase 1 is simpler than the code of the phase 2)

The second positive argument is that the known 17 of this kind appeared in any band 3 having >= 7 clues.
Having a process completely different of the process (vicinity search) used to find them before, the chances to get them and to miss a new one are very low

On the negative side, as wrote mladen, nobody had enough interest to check the code

So zero chance, no, but high confidence in the validity of the results, yes.
I checked carefully each step, so the risk of a possible error in files handling is also very low.

Cheers

champagne
champagne
2017 Supporter
 
Posts: 6692
Joined: 02 August 2007
Location: France Brittany

Re: scan solution grids for 17 clues as of blue

Postby coloin » Sat Nov 03, 2018 12:24 pm

blue wrote:For the known 17's, only ~25% of them have the double 6,6,5 distribution.


maybe there is mileage in just searching [for now] for 6,6,5 puzzles which have a box with exactly 3 clues [ and no box with 4].

i suspect that all box distribution 222222221s have been found
I also suspect that all 4xxxxxxxx have been found [ would imply 411 or 420 in a band with 6 clues]

just a thought
coloin
 
Posts: 1738
Joined: 05 May 2005

Re: scan solution grids for 17 clues as of blue

Postby champagne » Sat Nov 03, 2018 2:36 pm

coloin wrote:
blue wrote:For the known 17's, only ~25% of them have the double 6,6,5 distribution.


maybe there is mileage in just searching [for now] for 6,6,5 puzzles which have a box with exactly 3 clues [ and no box with 4].

i suspect that all box distribution 222222221s have been found
I also suspect that all 4xxxxxxxx have been found [ would imply 411 or 420 in a band with 6 clues]

just a thought

Phase 2 will not come in the top of my todo list this month, but this is easy to implement.

Can you tell more about "I suspect"
And when you say a box with exactly 3 clues I assume that it is "at least one box with exactly 3 clues"
champagne
2017 Supporter
 
Posts: 6692
Joined: 02 August 2007
Location: France Brittany

PreviousNext

Return to Software