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 » Sun Sep 13, 2020 10:00 am

Milestone September 13th

Mathimagics, continues to run the slice 130-140. Band 136 is closed, band 137 at half way
I am in trouble with a recent move to another place, but the workers are again in action, the main point to solve is a limited and temporary access to the net

Band 27 is closed and band 28 is on the way and should be covered in September
Bands >= 260 are closed
Comments on this V4 will come later in a separate post.


Today, 193 "bands 1" out of 416 are closed, with no new 17.
This is 46.3% of the bands 1, but only around 27% of the solution grids.
On the worst cases side, the runtime per band 2 goes down slowly, but remains high.

Bands closed are bands index 0-27 31 189 260-415 plus bands 130-136 searched by Mathimagics.
champagne
2017 Supporter
 
Posts: 7203
Joined: 02 August 2007
Location: France Brittany

first milestone 2021

Postby champagne » Sun Jan 03, 2021 9:13 am

Milestone January 3th 2021,

Nothing to report would say Mathimagics. For all bands closed, all expected 17 are there and no new appeared so far.

Nearly 4 months since the last milestone and 27 more bands 1 closed. Around 7 to 8 bands closed per month.
With still 195 bands 1 to process, the full scan with the current available power and the current process should be closed in 2023 at best.

I revised once more the code and one faster version is in the final validation test. The switch to this version is expected end of this month.
The improvement in in the first part of the process: the extraction of a potential valid pair of “valid band 1” + “valid band 2”.
A significant jump in performance requires now another improvement in the second part of the process. So far, I did not see what to do.

Bands 0 to 32 are now closed, band 33 is more than 50% covered
Bands 130 to 144 have been processed by Mathimagics.
Bands >245 (worst cases) are closed

The final validation test has been started on bands 240 241 and will be done on the band 34

I’ll prepare in January comments on the new version.
champagne
2017 Supporter
 
Posts: 7203
Joined: 02 August 2007
Location: France Brittany

milestone june 2021

Postby champagne » Wed Jun 02, 2021 4:45 am

Milestone June 2; 2021,

The process continues slowly, with usually around 20 cores active on my side and often 16 cores supplied by Mathimagics.
This is far away from the 820 cores used to prove that 17 clues is the smallest possible size.

We had 220 bands out of the 416 checked in January, the count is now 250. 30 bands in 5 months, still 166 bands to cover, with the current code and power available, the end of the search could be end of 2022.

So far, no new 17 appeared.

Working with Mathimagics on another issue, the check that no 18 exist in a given solution grid, we could see that our friend “blue” had activated in his code properties leading to a much better efficiency. Unhappily, we don’t have the code, so we have to guess what he did.

I have an idea of what is implemented in blue’s code and not in mine. I am preparing a V6 code (draft put in GitHub) to try to get the best of it.

So far, but I have still a lot of work to optimize the process, the positive effect is mainly when a small number of bands 3 is attached to a pair band 1 band 2. This explains why the gap was so big in Mathimagics’s issue.

I hope to have a V6 available in June,
champagne
2017 Supporter
 
Posts: 7203
Joined: 02 August 2007
Location: France Brittany

Re: milestone june 2021

Postby eleven » Wed Jun 02, 2021 9:16 pm

champagne wrote:The process continues slowly, with usually around 20 cores active on my side and often 16 cores supplied by Mathimagics.
This is far away from the 820 cores used to prove that 17 clues is the smallest possible size.

Does that mean, that you would have finished your search in some months (less than the 16 clue proof needed) with the same computer power ?
eleven
 
Posts: 2616
Joined: 10 February 2008

Re: milestone june 2021

Postby champagne » Thu Jun 03, 2021 3:48 am

eleven wrote:
champagne wrote:The process continues slowly, with usually around 20 cores active on my side and often 16 cores supplied by Mathimagics.
This is far away from the 820 cores used to prove that 17 clues is the smallest possible size.

Does that mean, that you would have finished your search in some months (less than the 16 clue proof needed) with the same computer power ?


This is a fact that "blue" noticed several years ago.

Blue had an estimate of a ratio 1:300 for the run time of his code applied to the 16 clues search.

Meantime, the code has been improved and I would not be surprised to be here over a ratio 1:1000.

But this version of the code is specific to the distribution 665. The basis to apply the code to the 16 clues search is the version (now closed for long) looking for 17 clues with a band having more than 6 clues.

One interesting point in this work is that our friend Mathimagics is looking for a code telling if a given solution grid can produce a 18 clues. Blue's code has not been published, but he sent a DLL doing the job in windows 10 to Mathimagics.

It is trying to produce something similar with my code that I discovered the high efficiency of blue's code.
A far as I can see, catching the goodies of blues search, telling whether a solution grid can produce a 18 will end in a run time in the order of magnitude of the runtime of the "no 16 clues" proof.
champagne
2017 Supporter
 
Posts: 7203
Joined: 02 August 2007
Location: France Brittany

start of the V6

Postby champagne » Thu Jun 24, 2021 4:00 pm

The new code is now ready for use.
This is the V6 version of the 17 clue search with the distribution 656.

a new repository has been used to store it sk_s17V6

I don't have precise figures, but this code could be twice as fast as the V5 in average.

The main change is a better use in the final step of the UAs created when a 17 checked is not valid.
But at the end, this pushed to several important changes.

The UAs (stored in a table in the code) necessary to expand a valid stack are added.
The control of the bands 1+2 passing all filters is suppressed
The sockets 2 handler, now on the critical path has been improved.

Each band 3 has now a table of all uas
.specific to the band
.belonging to the stacks and having some clues in band 3
.having <=4 clues in band 3 and not socket 2 or 3 appearing at the start or on the final check.

The outer loop using small uas in bands 1+2 has the last status of the implementation,
To day 258 bands1 out of the 416 have been checked with no new 17


We should have within one month a better idea of the improvement in performances.
champagne
2017 Supporter
 
Posts: 7203
Joined: 02 August 2007
Location: France Brittany

Re: scan solution grids for 17 clues as of blue

Postby Mathimagics » Sun Jun 27, 2021 12:13 pm

I have completed band 158 using V6, in 72 hours. It found all expected 17C's.

V5 would have taken 8/9 days. So, that is great work, champagne! 8-)
User avatar
Mathimagics
2017 Supporter
 
Posts: 1804
Joined: 27 May 2015
Location: Canberra

Re: scan solution grids for 17 clues as of blue

Postby champagne » Mon Jun 28, 2021 5:23 am

Mathimagics wrote:I have completed band 158 using V6, in 72 hours. It found all expected 17C's.

V5 would have taken 8/9 days. So, that is great work, champagne! 8-)


This is in line with my fresh runs.
Thinking of things to do to update the 18 search for you, I see small new things to test with a possible significant effect. I'll do it on the 17 search with a possible V7 end of July. The focus is in a better way to handle sockets 2 digits in band 3, the main source of improvement in the run time.
champagne
2017 Supporter
 
Posts: 7203
Joined: 02 August 2007
Location: France Brittany

milestone

Postby champagne » Tue Aug 03, 2021 5:25 am

quick status of the 17 scan:

V6 is now the version in use and the results are in line with expectations.
Still no new 17.

Mathimagics's cores are occupied on another task for a while, but we have reached 274 bands 1 closed out of the 416.

the 142 bands 1 not yet checked are bands index 44 to 129 and 164 to 220

Attempts to improve V6 failed so far
champagne
2017 Supporter
 
Posts: 7203
Joined: 02 August 2007
Location: France Brittany

Re: milestone

Postby champagne » Sat Oct 02, 2021 8:36 am

Milestone 2 months later

During these 2 months, 30 bands have been closed

bands 44-47
bands 164-175 (Mathimagics)
bands 207-220

bands 48, 176, 201-206 are on the way

V6 remains the best code valid so far. Small improvements could come next month.

about 50% of the ED solution grids have been checked with no new 17.

All the worst cases have been processed, so we can hope to keep with the current available power, an average 15 " bands 1" per month.
With still 112 "bands 1" not closed, the end of the scan is expected in 2022, at best around June July


Note, the current scan is done with around 35 active cores, half of them supplied by Mathimagics.
champagne
2017 Supporter
 
Posts: 7203
Joined: 02 August 2007
Location: France Brittany

Re: scan solution grids for 17 clues as of blue

Postby mith » Wed Oct 06, 2021 9:22 pm

If you need more cores to throw at it, I'd be happy to lend some of mine.
mith
 
Posts: 577
Joined: 14 July 2020

Re: scan solution grids for 17 clues as of blue

Postby champagne » Thu Oct 07, 2021 5:50 am

mith wrote:If you need more cores to throw at it, I'd be happy to lend some of mine.

Any additional power is welcome here.
We can share more trough PM

Mathimagics run so far" bands "1 index 130 to 176 and should continue to reach "band 1" index 200

bands 48 to 130 are still not covered and can easily be shared.
champagne
2017 Supporter
 
Posts: 7203
Joined: 02 August 2007
Location: France Brittany

Re: scan solution grids for 17 clues as of blue

Postby champagne » Sat Oct 09, 2021 4:02 pm

mith wrote:If you need more cores to throw at it, I'd be happy to lend some of mine.

I posted a pm yesterday for you
champagne
2017 Supporter
 
Posts: 7203
Joined: 02 August 2007
Location: France Brittany

Previous

Return to Software