One week later, I am more confident that the idea will work.
From blue enumerations, we know that the costly step, in his process to generate some 27+X+Y puzzles is the brute force, checking, in nearly all cases, that the puzzle has multiple solutions.
I made some tests on the gangster type
123456789124357689136278459 index 34 in blues table.
that gangster has no automorphism, so it is a very very long to process it against the ED X+Y patterns.
I made the test on the 3+5 file.
In blue's process, the elementary task is to process one of the morphs of the ED basic patterns, having cleared all possible redundancy seen.
The current process gives 4 282 308 calls but only 432 different patterns for the band having 3 clues (here after band3.
These 432 patterns for the band3 have been tested against all possible gangsters for the band3 derived from the gangster 34 in band1.
2 remarks at that point
I got 80136 band 3 (3 given) which is an average of 185.5 bands per pattern not so far from a maximum possible 6x6x6 = 216.
I finished that step with 29 459 760 valid band3 an average of 368 possible gangsters per band 3No evidence here that we can here reduce significantly (the target should be a reduction of 80% or more) the number of calls to the brute force at a reasonnable price.
splitting the average 368 gangster per band3, I got the following frequency table
- Code: Select all
gangsters; number of bands
<50 13786
<100 10162
<200 10463
<400 13398
<800 21926
>799 10401
I made some tests comparing the number of brute force calls using the pairs {gangster + band3} on one side, a full expansion of the band 2 for a given band3 on the other side.
When you pass 1000 possible gangsters for a given band, you have in that process to test the brute force for all or nearly all of the possible values for the band 2 (5 clues).
But we can do more.
We know that the puzzle will have multiple solutions if several of the gangsters possible for a given band3 (average 368, with the split of the frequency table) give the same solutiion in band 2(5 clues).
One special case is very interesting. If 2 gangsters possible in band 2 have exactly the same expansion, then all the corresponding expanded band 2 will lead to a non valid bands2;3 puzzle.Let's take one example
- Code: Select all
123 456 789 | 124 357 689 | 136 278 459 here is our gangster in band 1
- Code: Select all
4 | |
1 | |
| |2 here is the band 3 clues giving several (381) valid bands
- Code: Select all
1 1 | |
1 |1 |
| |1 here a valid 5 clues pattern for that 3 clues band
and now 2 different gangsters for the band 2 complementary to valid band3 gangsters
- Code: Select all
A B C |D E F |G H I
689 237 145 |789 146 235 |578 469 123
689 237 145 |789 146 235 |578 469 123
689 237 145 |789 146 235 |578 469 123
A B C |D E F |G H I
689 237 145 |789 146 235 |578 349 126
689 237 145 |789 146 235 |578 349 126
689 237 145 |789 146 235 |578 349 126
both will produce exactly the same set of 5 given.
for that entire set , the puzzle will have multiple solutions.
The key point here is that the set of given generated depends only on the columns pattern in the band with 5 clues.
Both gangsters have identical columns 1;2;4;7, this is enough to consider them as equivalent to expand the band with 5 clues.
and we see now what can be the "optimal process"
Shrink the list of (381) gangsters replacing each gangster by the smallest equivalent for the 5 clues pattern,
Flag all gangsters having duplicates and flag as multiples the corresponding sets of 5 clues given
expand the rest (if any) till the brute force check.
My expectation is that such a process in 27+5+3 would cut dramatically the runtime. The code should be ready for tests and validation when I am back home in a little more than a week.
