champagne wrote:blue wrote:For champagne,
To explain the "6^4" factor, You need to think about this: Suppose someone handed you a valid 3+4+27 puzzle. Suppose the 3+4 part didn't match one of the ED forms, and suppose the full band wasn't in any kind of canonical form. How could you show that your code would find the puzzzle, or one of its equivalents.
I like that start and here is my understanding.
We have a ED pattern corresponding to that valid puzzle (we generated all ED patterns). Morph the proposed puzzle to that ED pattern.
Take one box in the 27 clues band having the highest number of column occupied. Relabel rows 1 and 2 in that box to have 12345 in cells 1 to 5
if you are lucky, you can continue relabelling to have 123456789 in row 1, if it does not work, you have to exchange columns (and may be stacks 2 and 3) to come to the sequence 1234456789, the only one you have studied through the 401 minlex starts
It isn't always possible to do what you suggest, even if you allowed row permutations.
Example -- suppose box 1 (and its columns) must remain in place:
- Code: Select all
1 2 3 | 4 8 6 | 7 5 9
4 5 6 | 9 7 2 | 8 3 1
7 8 9 | 3 1 5 | 2 6 4
Even if it was possible, it would not guarantee that the final result matched one of the 416 minlex types.
For most of the types -- 279 of them -- if you apply a random transformation to the "minlex" version, then there is only one way to restore it to its original form. This means that for most bands, you need to consider all 6^4 "stack & column" permutations, and thier effects on the 1871 ED "3+4" patterns.
Doing that, I come up with 842724 ED patterns.
That's after applying one of the 6^4 column permutations, and then permuting rows in the 3 and 4 clue bands, to give a maxlex result in each band.
That won't mean that you definitely need to test 416*842724 (or 44*842724) different "<filled band, 3/4 pattern>" combinations.
For bands that have automorphisms (in particular, automorphisms that involve a column permutation ... which almost all of them do), you can test a subset of the 842724 of the "3+4" patterns.
To make a "smallest possible" list, for a band type, you can do this:
1) Loop through the list of 842724 patterns.
2) If the pattern is marked as "tested", skip it ... otherwise:
3) Add it to a list of patterns to be tested for that band.
4) Mark it as tested, along with every pattern that can be produced by applying the column permutation from one of the band automorphisms, and permuting rows in the 3 & 4 clue bands to give maxlex results in those bands.
When I do that for minlex bands, I come up with 283,283,376 different combinations, for an average of 680,970 per band.
Using gangster classes, the result is smaller because of two things: 44 is smaller than 416, of course, but also the "gangster types" have more automorphisms than the "minlex" types.
The number I come up with, using gangsters, is 14,760,393 combinations, for an average of 335,463 patterns per gangster type.
You can go farther than that too. Many of the gangster types (17 of 44) -- have automorphisms that don't involve column swaps -- only relabeling. When testing one those against a particular 3+4 pattern, you can check each way of setting clues in the 7 cells, for whether it is minlex with respect the "relabeling only" automorphisms, and skip the solver test for the ones that aren't minlex.
You can go one step farther, looking at automorphisms for the filled band that involve column swaps that leave the 3+4 pattern unchanged (unchanged after row permutations to restore the maxlex form). They are very rare though, and in the end, reduce the number of puzzles to be tested by only ~0.015%.
Using the 14,760,393 <gangster type, 3/4 pattern> combinations, and the reduction by "relabeling only" automorphisms, I count 1,291,535,777,143 different puzzles to be tested. Without the "relabeling" reductions, it's 2,071,606,976,120. The enumeration took around 8 hours.
So the question is: How long to test ~1.3 * 10^12 puzzles ?
[ That's assuming I haven't made any mistakes in the counting. ]
On the other hand, maybe a 3+4+27 puzzle really does exist, and one would be found quickly.
For myself, I haven't had any luck producing one by "other means".
I also tried testing a random 1% of the 14,760,393 <gangster type, 3/4 pattern> combinations (~20 hours), and found nothing.
