Hi Champagne. Could you outline how you get the 50:1 ratio for the [-4+4] / [-3+3] searches ?
Leren
Leren wrote:Hi Champagne. Could you outline how you get the 50:1 ratio for the [-4+4] / [-3+3] searches ?
Leren
Mathimagics wrote: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).
?combinations(17, 3) * combinations(81-17, 3)
28331520
?combinations(17, 4) * combinations(81-17, 4)
1512194880
?1512194880 / 28331520
53.375
champagne wrote:clear, but I am nearly 100% sure that this is an extension of the code written for the 17 clues search
Mathimagics wrote:champagne wrote: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?
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
champagne wrote:Leren wrote: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.
Mathimagics wrote: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
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
champagne wrote: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
blue wrote:There are two things overlooked in that calculaton
Mathimagics wrote:champagne wrote: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 ...
blue wrote:There are two things overlooked in that calculaton:For the the first part, I generally use "5 candidates" for this kind of calculation.
- number of candidates to choose from in each "+" cell
- "+" cells shouldn't be restricted to "originally empty" cells.
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
blue wrote: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.