The New Sudoku Players' Forum

[Leren]

Hi Champagne. Could you outline how you get the 50:1 ratio for the [-4+4] / [-3+3] searches ?

Leren

[Mathimagics]

champagne, perhaps I should make it clear that in the methodology I outlined above, when I referred to "blue's 18C functions", I was actually referring to the new functions he has created specifically for the LCT project (posted here).

[champagne]

Hi Champagne. Could you outline how you get the 50:1 ratio for the [-4+4] / [-3+3] searches ?

Leren

I just compared

taking 3 digits out of 17 and replacing them by 3 digits out of (81-17)
to
taking 4 digits out of 17 and replacing them by 4 digits out of (81-17)

If I did it in the right way, the ratio is slightly above 1:50

This should reflect in my opinion the number of situations to study.

[champagne]

champagne, perhaps I should make it clear that in the methodology I outlined above, when I referred to "blue's 18C functions", I was actually referring to the new functions he has created specifically for the LCT project (posted here).

clear, but I am nearly 100% sure that this is an extension of the code written for the 17 clues search

[Mathimagics]

He's right, Leren!

Code: Select all

?combinations(17, 3) * combinations(81-17, 3)
 28331520
?combinations(17, 4) * combinations(81-17, 4)
 1512194880
?1512194880 / 28331520
 53.375


[Mathimagics]

clear, but I am nearly 100% sure that this is an extension of the code written for the 17 clues search

Ok, thanks.

So am I right in thinking that you/we have a Find17C function which, like Find18C and Find19C, tests a solution grid (definitively) for a 17C puzzle existence?

If so, what is the average time per grid that it takes?

[champagne]

clear, but I am nearly 100% sure that this is an extension of the code written for the 17 clues search

Ok, thanks.

So am I right in thinking that you/we have a Find17C function which, like Find18C and Find19C, tests a solution grid (definitively) for a 17C puzzle existence?

If so, what is the average time per grid that it takes?

The " scan solution grids for 17 clues" does exactly this. The average time per grid is not easy to establish. Blue did it using estimates in random exploration of the field. He is so efficient in such estimates that I never tried to duplicate his work
I let him answer, but to cover the field with 20 cores in 2 years (what is by far not granted), you have to reach an average of 4.33 solution grids per second

[blue]

I haven't made an "all in one" Find17C() function yet.
With my current code running 2 passses over the inputs, I get:

Code: Select all

17's, single grid method: 5,472,730,538 inputs

xy(7+)  phase : 0.140s
665/665 phase : 0.300s
          sum : 0.440s -> 76.4 core years

17's, divide & conquer method: 983,959,110 inputs

xy(7+)  phase : 0.035s
665/665 phase : 0.230s
          sum : 0.265s -> 8.27 core years
    remaining : 830,000,000 * 0.230s -> 2210 core days

That's on a 3.6GHz AVX/AVX2 machine with with turbo-boost disabled ... one thread per core.

There are two ways (for sure), to knock 20% off the times

• 7 processes, hyperthreaded on 4 cores <- fix: with the latest version, this only knocks off ~15% of the time.
• AVX2 version, using 256-bit (ymm) registers

[blue]

Hi Champagne. Could you outline how you get the 50:1 ratio for the [-4+4] / [-3+3] searches ?

Leren

I just compared

taking 3 digits out of 17 and replacing them by 3 digits out of (81-17)
to
taking 4 digits out of 17 and replacing them by 4 digits out of (81-17)

If I did it in the right way, the ratio is slightly above 1:50

This should reflect in my opinion the number of situations to study.

He's right, Leren!

Code: Select all

?combinations(17, 3) * combinations(81-17, 3)
 28331520
?combinations(17, 4) * combinations(81-17, 4)
 1512194880
?1512194880 / 28331520
 53.375


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


[Mathimagics]

I [will] let him answer, but to cover the field with 20 cores in 2 years (what is by far not granted), you have to reach an average of 4.33 solution grids per second

And this would require blue's Find17C function to achieve per-grid average times of under 250ms, in other words it would have to be roughly 17 times faster than Find18C ...

But it makes sense that 17C would be faster than 18C, now that I think about it ...

Find18C at 4s/grid is actually roughly 20 times slower than Find19C (somewhere in the range .020 - 0.25s/grid).

But that's a peculiar case - while there are less patterns (I presume) to check for 18C than 19C, the 19C puzzles are like mosquitoes, there's billions of them, and nearly every grid has one, often many. So Find19C almost always succeeds (and thus takes an early shower), while Find18C will mostly fail (perhaps 80% of the time), and failure is very costly, despite the reduced pattern numbers, since every pattern must be checked!

17C tests will, of course, fail even more often, effectively 100% of the time, but relatively 100% vs 80% is no big deal, and the reduced 17C pattern count would then easily dominate the comparison (I assume that the number of test patterns for 17C is in fact only a fraction of the 18C patterns).

All of this suggests that my estimate based on Find18C was basically irrelevant (I was thinking in my delirium that Find17C might be slower than Find18C. )

It should of course be faster, and all that remains is to ask blue "by how much?", what average grid times he is currently getting!

Then we can calculate those estimates of core-years - that's something even I can do right!!

=========================================================

PS: this analysis might actually be worthy of "Sybil Fawlty" award nomination (given for contributions on the bleeding obvious). You'd tell me, wouldn't you?

[Mathimagics]

There are two things overlooked in that calculaton

That's right blue, kick a man (a sick man!) while he's down ...

... then post a comprehensive answer to the question he was still in the process of typing up ....


PS: only two? you must have missed something! Nyah

[champagne]

I [will] let him answer, but to cover the field with 20 cores in 2 years (what is by far not granted), you have to reach an average of 4.33 solution grids per second

And this would require blue's Find17C function to achieve per-grid average times of under 250ms, in other words it would have to be roughly 17 times faster than Find18C ...

Just to make it simpler, the scan of solution grids to extract 17 is not done for one grid alone, but for all bands 3 relevant for a couple of bands 1+2.

In average, a given bands 1+2 has 9 bands 3 attached (in the 665 distribution) so for a single solution grid, it would be close to 2.5 seconds.

And yes, if the number of 18 is small in a given solution grid, the 17 clues search is much faster. You got the point

[champagne]

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


Hi blue,
Sorry, I missed your 2 posts.
Here, I have no problem with the forgotten "possible candidates effect".
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

[champagne]

I haven't made an "all in one" Find17C() function yet.
With my current code running 2 passes over the inputs, I get:

17's, divide & conquer method: 983,959,110 inputs

xy(7+) phase : 0.035s
665/665 phase : 0.230s
sum : 0.265s -> 8.27 core years
remaining : 830,000,000 * 0.230s -> 2210 core days[/code]
That's on a 3.6GHz AVX/AVX2 machine with with turbo-boost disabled ... one thread per core.

Hi blue,

If I read this in the right way, this is better than the code currently doing the 665 search on my side

[Mathimagics]

Ok, thanks blue, champagne!

In the context of the LCT project, I am less interested in finding new 17C's than I am in the recording of all the failures.

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

Soon we will have completed the 19C status checking. 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? )

So an LCT-17 project would look like this:

• Phase 1: this is actually just LCT-18 phase 1, the generation of as large an 18C pool as possible, and this is already kicking off

• Phase 2: do a "Find17C" on the resulting pool

• Phase 3: (later) do a "Find17C" on the remaining candidate grids

The thing is, most hypothetical new 17C's will likely be found in phase 2. Both phases are doable in some months without outside assistance. 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.

(Phase 3 is of course only an aspiration at this stage)