The New Sudoku Players' Forum

[blue]

Hi champagne,

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

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]

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? ), 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.

[Mathimagics]

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!

[Leren]

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

[blue]

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.

[champagne]

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]

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.

[dobrichev]

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

[champagne]

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
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.

[Mathimagics]

Hi champagne!

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

Cheers
MM

[champagne]

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]

The last milestone for the year 2019 was done Dec 11th, 2019.

A shutdown of about 3 months was planned for the current search (distribution 566) from mid-January to mid-April 2020.

Due to the current troubles, the shutdown has been between one and 2 weeks longer.

The process continues with the V3 version (see post 4 in this thread for more comments) in the limit of the power available on my side;

Today, 161 "bands 1" out of 416 are closed, with no new 17. (38.7% of the bands 1)

Bands closed are bands index 0-24 31 189 282-416

This is about 21% of the ED solution grids, but, as the worst cases are covered, my rough estimate is that a little more than 25% of the job is done.

A precise estimate of the future run times remains difficult:

The three computers used have not comparable results,
The runtime per solution grid is still in a ratio 1:60 between the current low index bands (index 25) and the current high index band (281).

This ratio will decrease in the future as I plan to continue to process bands selected on both sides. I hope to be in autumn in a position to make a better estimate of the time needed to come to the end of this search (without external free cycles).

[champagne]

Milestone end of June 2020

Several new facts this month:

Thanks to Mathimagics, he started the search on the bands index 130-140 with 16 cores. These bands are expected to give a reasonable view of the average run time for the last 15% of bands 3.

After more benchmarks and discussions with Mathimagics, I reduced the number of active cores, but the global throughput should not be seriously changed.

I made small changes in the code processing bands 3, so we have now in use the version V4. Comments on this V4 will come after one month of experimentation.


Today, 172 "bands 1" out of 416 are closed, with no new 17.
This is 41% of the bands 1, but only about 25% of the solution grids because the worst cases have been covered

Bands closed are bands index 0-25 31 189 275-415 plus bands 132-134 searched by Mathimagics.

Bands index 0 to 131 cover about 90% of the solution grids.

Band index 132 has been searched in 14 days 8 hours. This is for 16 550 000 solution grids. About 1.2 second per solution grid. This should be the order of magnitude for the last 15% of the solution grids, still 9 months for these 15% with the total current power dedicated to the search.

The upper remaining part could be covered in nearly the same time.

[ghfick]

I just tried 49158. Not only is this discovery fascinating, but 49158 is not elementary. Indeed, I had to use an XY-Chain in the path.
btw... Is there a sublist of the 49158 puzzles that are not elementary? Like needing an XY Chain or maybe SE >= 7?

[SpAce]

I just tried 49158. Not only is this discovery fascinating, but 49158 is not elementary. Indeed, I had to use an XY-Chain in the path.
btw... Is there a sublist of the 49158 puzzles that are not elementary? Like needing an XY Chain or maybe SE >= 7?

Yogi posts a non-basic 17-clue puzzle on the 17th day of each month, such as this. Just search the Puzzles section for them. They're usually pretty nice as OTP challenges. If you want more challenge, here's a few.