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 » Mon Jul 22, 2019 7:21 pm

New milestone in this project.

Now , bands1 index 0 to 7 and 330 to 415 are closed.
all known 17 came, no new 17 appeared.
Band 8 is half covered,
band 189 is covered at 90%

This is more or less 6% of the total band 3 count.
I'll check carefully in the next days the index 189 status.

Next milestone (in one month??) should cover at minimum bands 1 index 8;9 31

As no fee core joined the project so far, the process remains too slow for my available power.

Meantime, I checked directly that no 17 with 2 clues in a band exists. (looking for 18 clues with a band having 2 clues)
Doing so, I have seen neglected puzzle properties (AFAIK) and a possible new design of the current search.

Implementing and testing such a design is to-day my priority in the limit of the time dedicated to the project. I could get a first feeling of the feasibility in 2 or 3 weeks.

I used the third post in this thread to give information on the new design. This post will be edited when something of interest shows up
champagne
2017 Supporter
 
Posts: 6969
Joined: 02 August 2007
Location: France Brittany

search of 17 with 665 distribution milestone

Postby champagne » Wed Aug 14, 2019 9:34 am

97 bands are now closed or nearly closed for one band(index 0_9 189 and >=330)

up to now, in each closed band
all known puzzles are here
no new 17 came up.

This is about 8% of the total number of solution grids to scan.

Results for the band index 189

Results for the band index 189 are interesting to decipher.
This band was scanned mainly because it has the highest number of expected 17 with distribution 665
It is in the middle of the index. At this point, 88% of the bands 2 to scan are there and 97% of the solution grids to scan have been covered (if all previous bands 1 are closed)
The average number of bands 3 per band 2 is 3.11

The bad news for the future is that the worst cases scanned on my AMD phenom6 with 7 cores fully occupied required about 17 seconds per band 2 (nearly 6 seconds per solution grid)

I don't have benchmarks on the Intel i7 machines, but anyway, this is on the high side of my expectations.

Alternative process

The good news is that the alternative process shows a potential to divide by 2 or more this run time as far as I can see out of the first tests.

The fresh code produced it's first 17 recently. In this code, the band 2 is expanded in a way very close to the band 3 expansion in the current process. Some changes have been made also in the band 3 process to diminish the run time. Some of these accelerators have to be implemented in the second band as well.

In 2 or 3 weeks, all needed tests should have been done and I'll have a better idea of the true potential of this process.

In the new process, many pieces are common to the old one, However, I thought necessary to open a specific repository https://github.com/GPenet/sk_s17

Next steps

Waiting for the results of the alternative process, the scan goes ahead with bands index 10_12 ( more if necessary) and 31 (another band with many expected known 17).
Next milestone will come with the results of the alternative process. This could come this month.
champagne
2017 Supporter
 
Posts: 6969
Joined: 02 August 2007
Location: France Brittany

Re: scan solution grids for 17 clues as of blue

Postby champagne » Mon Sep 02, 2019 7:01 am

short milestone to comment on the alternative process.

The code has now passed the planned tests. The repository contains the current code, with still a lot of debugging code.
Although benchmarks are not so easy to run with all cores occupied in the 17 search, I can confirm that the run time is divided by about 2 (may be a little more) with the alternative process.

bands 1 index 9 10 11 12 31 are closed or nearly closed with the old process
bands 13 and 326-329 have been started with the alternative process.
champagne
2017 Supporter
 
Posts: 6969
Joined: 02 August 2007
Location: France Brittany

#49158 -- another 17, finally !

Postby blue » Fri Oct 11, 2019 3:46 am

This was found using code along the lines of what champagne has been describing in this thread.

Code: Select all
........1.....2..3.45.............1...6.....237..6.......1..4.....2.35...8....... #49158

It came up at about the 8% point in the "pass 2" phase -- the 665/665 search.
At the 15.65% mark, this was the only new one found.

The testing covered a (pseudo) random subset of the 983,959,110 ED bands 1&2 cases. [ 830,000,000 cases remain. ]
Based on that, I think the most likely number of (still) undiscovered 17's is 5.

Blue.
blue
 
Posts: 869
Joined: 11 March 2013

Re: scan solution grids for 17 clues as of blue

Postby dobrichev » Fri Oct 11, 2019 4:50 am

Blue, that is Impressive!!!!

You make me believe in Santa again.
dobrichev
2016 Supporter
 
Posts: 1733
Joined: 24 May 2010

Re: scan solution grids for 17 clues as of blue

Postby Mathimagics » Fri Oct 11, 2019 4:52 am

Congratulations blue !!! 8-)

That's a new ED grid, too (#46301):
Code: Select all
D:\UA9\Find19C\Admin>GridStatus.exe
 G: ........1.....2..3.45.............1...6.....237..6.......1..4.....2.35...8....... #49158

CF: 123456789456789132789231546264318957578694213931572468345827691617943825892165374
CP: ...4..7..4...89...........6.6.....5..78....1......2.........6....7...8.....1.5...

    Band  24, record  45515774 (cat index # 885450784)
    Current status: 19C puzzle recorded
    .....67...5.........9....4.26...8.......9..1..3...2.....5...6.1..794..........3..
User avatar
Mathimagics
2017 Supporter
 
Posts: 1292
Joined: 27 May 2015
Location: Canberra

Re: scan solution grids for 17 clues as of blue

Postby dobrichev » Fri Oct 11, 2019 7:22 am

I am confirming that blue's
Code: Select all
........1.....2..3.45.............1...6.....237..6.......1..4.....2.35...8....... #49158

is new, and that it is lone on its {-3,+3} island.
dobrichev
2016 Supporter
 
Posts: 1733
Joined: 24 May 2010

Re: scan solution grids for 17 clues as of blue

Postby tarek » Fri Oct 11, 2019 7:57 am

Congratulations,

My mistake the other week wasn’t a mistake after all. I could see the future :lol:

Clairvoyant Tarek
User avatar
tarek
 
Posts: 3075
Joined: 05 January 2006

Re: scan solution grids for 17 clues as of blue

Postby blue » Fri Oct 11, 2019 8:30 am

Clairvoyant Tarek

I'm a believer :lol:

dobrichev wrote:I am confirming that ...
and that it is lone on its {-3,+3} island.

Thank you.
blue
 
Posts: 869
Joined: 11 March 2013

Re: #49158 -- another 17, finally !

Postby champagne » Fri Oct 11, 2019 9:08 am

blue wrote:This was found using code along the lines of what champagne has been describing in this thread.

Code: Select all
........1.....2..3.45.............1...6.....237..6.......1..4.....2.35...8....... #49158


Blue.

Hi Blue,

Good to see that finally the first new 17 came from the inventor of the breakthrough in the search. Congratulations.

On my side, the slow "full scan" of the ED solution grids is going on with the limited power that I can use. Except for bands index 13 and 14, I am mainly working with the second version of code on the High index. A new milestone should come within 2 weeks.

After a short work on the 18/19 extraction from a solution grid, I came with fresh Ideas to try to speed up the code.
I am testing the new draft with hopes to get a new (third) version within a week.
champagne
2017 Supporter
 
Posts: 6969
Joined: 02 August 2007
Location: France Brittany

Re: scan solution grids for 17 clues as of blue

Postby GouinJP » Fri Oct 11, 2019 2:30 pm

Hi
Today I found this one.
Is it a new one #49159?

000000001000002030004005006000000003010070000870000000000000800000810070520000000
Last edited by GouinJP on Fri Oct 11, 2019 2:58 pm, edited 1 time in total.
GouinJP
 
Posts: 294
Joined: 06 April 2013
Location: Montreal

Re: #49158 -- another 17, finally !

Postby Serg » Fri Oct 11, 2019 2:54 pm

Hi, Blue!
blue wrote:This was found using code along the lines of what champagne has been describing in this thread.

Code: Select all
........1.....2..3.45.............1...6.....237..6.......1..4.....2.35...8....... #49158

Very impressive finding! Congratulations!

Serg
Serg
2018 Supporter
 
Posts: 652
Joined: 01 June 2010
Location: Russia

Re: scan solution grids for 17 clues as of blue

Postby champagne » Fri Oct 11, 2019 3:10 pm

GouinJP wrote:Hi
Today I found this one.
Is it a new one #49159?

000000001000002030004005006000000003010070000870000000000000800000810070520000000

seems to be a morph of the last puzzle of blue
champagne
2017 Supporter
 
Posts: 6969
Joined: 02 August 2007
Location: France Brittany

Re: scan solution grids for 17 clues as of blue

Postby Mathimagics » Fri Oct 11, 2019 3:56 pm

champagne wrote:seems to be a morph of the last puzzle of blue


Indeed, it is the very same one ...

Code: Select all
> gridstatus
 G: 000000001000002030004005006000000003010070000870000000000000800000810070520000000

CF: 123456789456789132789231546264318957578694213931572468345827691617943825892165374
CP: ...4..7..4...89...........6.6.....5..78....1......2.........6....7...8.....1.5...


CF is the puzzle solution when canonicalised, CP is the corresponding puzzle.
User avatar
Mathimagics
2017 Supporter
 
Posts: 1292
Joined: 27 May 2015
Location: Canberra

Re: scan solution grids for 17 clues as of blue

Postby coloin » Sun Oct 13, 2019 10:06 pm

Yes, very well done blue.....
dobrichev wrote:I am confirming that blue's puzzle is new, and that it is lone on its {-3,+3} island.

even a {-4+4} on the 49157 wouldnt have found it !
there are only 8 puzzles from the 49157 which share 12 common clues [and no puzzle sharing 13 clues]
Code: Select all
........1.....2..3.45.............1...6.....237..6.......1..4.....2.35...8....... # 49158
                                                                                 
..............2.3..45............91.........237..6.......1........2.34...86...5..
........1.....2..3.4.5........8..41...6......37.......1....6......2.35...8.......
........1.....2..3.45..........4....3.....1.2.7..6........9.46......35...8.......
........1.....2..3.45..........9..1.2.6......3.............64..7..2.35.........9.
.......21.........94.............91...6......372.6.......1..4.....2.3....8....5..
..2...6.1....8.....4..............1...6...9.237..6.......1........2.3....8....7..
.7......1.....2..3.45.........74......6......3...6.....9....4.....2.35.......1...
.9......1.....2..3.45..........8.5....6......37..6.....8....4.....2.3........1...
                                                                                 
similarity  8      395                                                           
similarity  9    37523                                                           
similarity 10    10793                                                           
similarity 11      438                                                           
similarity 12        8                                                           
similarity 17        1 

of note maybe for any 2 puzzles its difficult to not share at least 8 clues ?

at any rate #49158 is so remote a puzzle that we never found it !
coloin
 
Posts: 1813
Joined: 05 May 2005

PreviousNext

Return to Software