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 blue » Tue Oct 15, 2019 6:08 pm

Hi champagne,

champagne wrote:If we switch from a strict -3+3 to a strict -4+4, I have more difficulties with your "originally empty" adjustment.
This would match better in my feeling with a {-1+1 to -3+3} versus a {-1+1 to -4+4} comparison, but I learned for long to be wrong against your view :oops:

Think about this: "same shape, different clues", "almost the same shape, not almost the same clues" ...

For a strict {-n,+n}, really the only (*) thing you can ignore is placing the original clue value in a "+" cell that's also a "-" cell.
Taking that into account, would change the "5 candidates" number that I used, but only only a small amount.

The "5" in the (5^n) factor is isn't exact, anyway.
It's just a number has worked well in other calculations, when actual numbers have been compared.
With so few filled cells remaining, after "{-3}" or "{-4}", it might be too small.
Technically, it seems like it should increase slightly, as 'n' increases.

Cheers.

Added: (*) - "Only" isn't quite correct. If after the "-n" operation is performed, there are two empty rows, for example, then the "+n" cells could give a shape that would share cells with the original puzzle (in those rows) if the rows were swapped.
blue
 
Posts: 894
Joined: 11 March 2013

Re: scan solution grids for 17 clues as of blue

Postby blue » Tue Oct 15, 2019 7:03 pm

Hi Mathimagics,

Bottom line for me is:

  • is a hypothetical Find17C possible? One that effectively behaves as does Find18C, ie can return a definitive 0 or 1 according to whether or not a 17C puzzle exists on that grid (the actual puzzle would also be nice!)?

    From LCT pov, it doesn't matter whether the function works on individual grids or on batches (provided it answers the question for all ED grids in the batch, of course!), or whether it does 2 passs, etc

  • if yes, what might the average grid testing time be (roughly)?

Yes, it's possible. From my post above, the average testing time would be 440 ms/grid. (fixed ms/grid time)
With so few grids having a 17, it wouldn't matter if it found just one, or all 17's on a grid.
Also, FYI: the "divide and conquer" method, doesn't operate on batches of grids.

Then, with LCT-18, we can probably find most 18C grids in a few months (by our morphing process, if indeed the majority of 18C puzzles are in fact {-1,+1}-connected).

This would reduce the potential 17C grid pool, of course, to 0.9 billion. (blue mentions the quantity "983,959,110" - is that a sampling prediction? )

"983,959,110" is the number of ED ways to fill two bands.
It is pretty close to my (earlier) sampling prediction for "18C" grids, though: 968 million plus or minus 13.

About "the majority" of 18C puzzles being {-1,+1}-connected: It's a large number, I know ... but I don't know if it's a majority.
The 17's that have a "{+1}" extension in that pool, are already known, though.
The code that I used to find 17's #49153-7, was based around the idea of doing {-1,+1} on 18's, while trying as best as possible, to avoid 18's in the large pool.

For example, if blue's estimates (2200 core days) are right, then my 16-core ThreadRipper (oh, did I mention that I'm expecting this new baby any day now? 8-) ), could certainly make a major contribution. Less time, of course with the complete Gang of Four.

Completing that search -- something that I didn't intend to to -- would be the fastest way to get the complete list(s) of grids with/without a 17C puzzle.
If we could get enough cores together to complete it in under 90 days, I'ld participate.
It's heating season in my hemisphere :!:

Cheers.
Last edited by blue on Wed Oct 16, 2019 12:09 am, edited 1 time in total.
blue
 
Posts: 894
Joined: 11 March 2013

Re: scan solution grids for 17 clues as of blue

Postby Mathimagics » Tue Oct 15, 2019 8:06 pm

Thanks blue!!

So we need approx 24 cores. Does that sound right?

The new PC is 16Core x 2Thread, so I could surely get an effective yield of 20-cores, surely? How many cores can you deliver?

I will have 64Gb of RAM, which I trust will be sufficient. If not, it has spare slots for upgrade to 128Gb.

I have several questions for you about the process, but will raise them with you by PM.

This should be fun!

Cheers! 8-)
User avatar
Mathimagics
2017 Supporter
 
Posts: 1480
Joined: 27 May 2015
Location: Canberra

Re: scan solution grids for 17 clues as of blue

Postby Leren » Tue Oct 15, 2019 9:03 pm

blue wrote:There are two things overlooked in that calculaton:
  • number of candidates to choose from in each "+" cell
  • "+" cells shouldn't be restricted to "originally empty" cells.
For the the first part, I generally use "5 candidates" for this kind of calculation.
With that, the ratio is more like 300:1
Code: Select all
choose(17,4) * choose(81-17+4,4) * 5^4 = 1211397687500
choose(17,3) * choose(81-17+3,3) * 5^3 = 4071925000
1211397687500 / 4071925000 = 297.5

These are the exact same numbers I get, based on blue's" fixed 5 candidates" assumption for both [-3+3] and [-4+4] searches.

The reason I asked the question in the first place was that I recently completed a [-2+2] search in the Sudoku X project, and I wanted to check my thinking on the [-2+2] / [-3+3] ratio for 12 clue Sudoku X Puzzles.

To avoid getting off topic here it's better if I say something more about this in the Sudoku X thread.

Leren
Leren
 
Posts: 3714
Joined: 03 June 2012

Re: scan solution grids for 17 clues as of blue

Postby blue » Tue Oct 15, 2019 9:52 pm

Mathimagics wrote:So we need approx 24 cores. Does that sound right?

About right, yes ... 20 might do ... depending on performance, ability to run 64-bit code, and CPU feature list.
64-bit Windows, and SSE4.2 support (at least) would be good. AVX or AVX2 support ... even better.

How many cores can you deliver?

I only have the four.

The new PC is 16Core x 2Thread, so I could surely get an effective yield of 20-cores, surely?

I can only guess.
I mentioned in another thread, that I worry about a memory bottleneck on a "many core" machine.
Things like cache sizes and memory bandwidth(s) will be important, the way the code works.

Code: Select all
I will have 64Gb of RAM, which I trust will be sufficient.  If not, it has spare slots for upgrade to 128Gb.

64Gb is great plenty. The memory usage would be similar to what you see with the "Find18C"/"Find19C" apps.

Cheers.
blue
 
Posts: 894
Joined: 11 March 2013

Re: scan solution grids for 17 clues as of blue

Postby champagne » Thu Nov 07, 2019 8:07 am

champagne wrote:short milestone to comment on 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.

Back to the main topic of this thread with a new milestone


In between the progress has been very slow.
I identified a bug in the second version of code and had to restart some batches.
I had in mind ideas for further improvements, but it has been very tough to come to something of value.

On the count, 125 bands 1 out of 416 are closed or nearly closed with no new 17. As most of the bands are with high indexes (308-416), in terms of solutions grids processed, this is about 10% of the total covered. Most of them with bands having index 0-14

Batches with the new code have been started for the band index 15 and more will be launched for bands in the range 280 307 where the number of expected 17 is low, making easier the check of the results.

The last code has been loaded in my google drive (file sk17v3.zip) but the comments have to be updated what will be my next task
champagne
2017 Supporter
 
Posts: 7019
Joined: 02 August 2007
Location: France Brittany

Re: scan solution grids for 17 clues as of blue

Postby champagne » Wed Dec 11, 2019 8:22 am

Last milestone for the year 2019

The process is now stable with the V3 version (see post 4 in this thread for more comments).
No free cycle showed up so far, so the search goes slowly, with the limit of the power available on my side;

The search (distribution 566) will be in these conditions halted from mid January to mid April 2020.

To day, 138 "bands 1" out of 416 are closed, with no new 17.

Bands closed are bands index 0-17 31 189 298-416

This is about 20% of the work.

I continue to work on both side, with currently open

band index 18
bands index 295-298

I plan to have the next milestone in one month, before the temporary closure of the work.
champagne
2017 Supporter
 
Posts: 7019
Joined: 02 August 2007
Location: France Brittany

Re: scan solution grids for 17 clues as of blue

Postby dobrichev » Wed Dec 11, 2019 4:51 pm

I sense some entropy decrease in Western Europe. Perhaps one more 17 is very close to being discovered.
dobrichev
2016 Supporter
 
Posts: 1777
Joined: 24 May 2010

Re: scan solution grids for 17 clues as of blue

Postby champagne » Wed Dec 11, 2019 6:19 pm

dobrichev wrote:I sense some entropy decrease in Western Europe. Perhaps one more 17 is very close to being discovered.

blue's last guess is 4/5 more 17 to find, with no more free cycles, it could be 2 to 4 more years on my side :D
Just to compare, the check that no 16 exists used 820 cores of the best available computer at this time. The job lasted about one year.
I am working with about 20 cores....
But now, it's just time to check carefully that the cores did all the job. :roll:
champagne
2017 Supporter
 
Posts: 7019
Joined: 02 August 2007
Location: France Brittany

Re: scan solution grids for 17 clues as of blue

Postby Mathimagics » Tue Feb 11, 2020 7:33 am

Hi champagne!

You might be interested in the results of the distribution of 17C and 18C by band - see this post

Cheers
MM
User avatar
Mathimagics
2017 Supporter
 
Posts: 1480
Joined: 27 May 2015
Location: Canberra

Re: scan solution grids for 17 clues as of blue

Postby champagne » Tue Feb 11, 2020 1:48 pm

Mathimagics wrote:Hi champagne!

You might be interested in the results of the distribution of 17C and 18C by band - see this post

Cheers
MM


Hi Mathimagics,

Difficult to compare what is done in the full scan for 17's and the scan for the first 18 (if any).

On my side, the task is in stand by till mid april. with 149 bands closed and no new 17 so far.

I wrote a code to extract 18/19 clues puzzles from a solution grid, but Blue's code seems better as far as I can see.

Regarding correlations bands => number of puzzles found, one remark

The number of cases to check is highly dependant on the number of isomorphs in the solution grid.
Generally speaking, the more cases you have, the best chance you have to produce a puzzle,

but this correlation is poor.
champagne
2017 Supporter
 
Posts: 7019
Joined: 02 August 2007
Location: France Brittany

Previous

Return to Software

cron