Band 1 counting for 3xC grids is very easy, because box 1 is fixed in canonical form, and box 3 is uniquely determined (up to row permutations) by boxes 1 and 2. The count reduces to the simple formula that Kjell posted, which specifies a computation that is simple enough to be done by hand.
RxC for R >= 4 is much harder. Kjell's 4xC formula specifies the count but not an efficient way to compute it. The key, as usual, is to find and exploit equivalence classes. For my 4xC and 5xC counts, I find a set of equivalence classes (gangsters) for box 2 where box 2 permutations are in the same class if the "structure" of the mapping from box 1 rows to box 2 rows is the same. This structure is represented by a directed, labelled graph (DLG) containing R nodes.
This can best be explained by example. Here are representative members of two gangsters from the 4x4 case:
- Code: Select all
Box 1 Box 2 Box 2
0 1 2 3 C D E F C D E F
4 5 6 7 8 9 A B 8 9 A B
8 9 A B 3 5 6 7 1 2 3 7
C D E F 0 1 2 4 0 4 5 6
___ 4 ___ ___ 4 ___
/ \-------->/ \ / \-------->/ \
| 1 | | 4 | | 1 | | 4 |
\___/<--------\___/ \___/<--------\___/
^ 3 | ^ 1 |
| | | |
|1 |1 |3 |3
_|_ 3 _V_ _|_ 1 _V_
/ \-------->/ \ / \-------->/ \
| 3 | | 2 | | 3 | | 2 |
\___/<--------\___/ \___/<--------\___/
4 4
Node "4" of the left DLG, for example, has an arc labelled "3" directed to node "1" that specifies that 3 symbols in box 2 row 4 came from box 1 row 1. Box 2 permutations are in the same class if their DLGs are isomorphic (identical topology and arc labels, but ignoring node numbers). Note that the above two DLGs are not isomorphic. The topology is the same, but the arcs labels are different, and indeed they yield different box 3 counts.
I have a lot of confidence in this method, and in the specific implementation I've coded, because it gives the right results for the 4x4 and 4x5 cases, which have been confirmed independently (I also ran the 4x4 case without the equivalence classes and got the same result).
There may be a simpler way of defining the box 2 equivalence classes, but if so I don't know what it would be.
Here are the number of box 2 gangsters for various cases:
- Code: Select all
4x4: 28
4x5: 53
5x3: 89
5x4: 618
5x5: 3087
Using the gangsters, my 4x4 running time is 32 ms, and my 4x5 time is 830 ms. These could be improved significantly using methods I developed for the 5xC cases, but I didn't see any point in doing so.
The 5x3 count can be done quickly without further equivalence classes, but 5x4 was reduced from what would have been about one month to under three days by finding some simple equivalences for box 3. For any box 2 gangster, any arc in the DLG with a label >= 2 represents multiple symbols that moved together from one row of box 1 to another row of box 2. These symbols are interchangable in box 3 without affecting the box 4 count. Those that happen to be in the same row in box 3 do not yield a different case and so do not offer any help, but those that end up in different rows of box 3 can be counted just for a canonical configuration.
For example, consider the symbols 0, 1, and 2 for the left DLG above. These symbols can be interchanged in box 3. In permutations where they are all in the same box 3 row, there is no benefit. If two are in one row and one in another, there are three equivalent permutations. If all three are in different rows, there are six equivalent permutations. These equivalences can be used independently for all of the DLG arcs with labels >= 2, resulting in a huge advantage in many cases. For the 5x4 count, the one gangster with only two arcs whose labels are "2" took 4015 seconds, but the best case, with many independent equivalences, took only 7 seconds. There is also one gangster where all arcs have label "1", and in that case I use the box 3 / box 4 swapping equivalence to reduce the time by a factor of 2. On average each gangster took about 400 seconds.
I ran the 5x3 case with and without the box 3 equivalences and got the same result, so I trust the method. I also ran one 5x4 gangster without the box 3 equivalences and got the same result. Since the same source code is used for all of the 5xC band 1 counting, the 5x3 checks provide some confidence that the 5x4 results are correct. There are more such checks that I need to run, however.
I am convinced that much better box 3 equivalences can be found, which might reduce the 5x4 case to hours instead of days. But I suspect that even such improvements would not bring the 5x5 band 1 count within reach. We'd need a qualitatively different method.
I also used quite a few programming tricks to get the 5x4 count within reach. The first version of the code I wrote (no box 3 equivalences, very simple loops) would have needed 60 hours to do one gangster if I had let it run all the way. I sped it up to 3.6 hours for one gangster before letting it run all the way, and then made sure I got the same result as I sped it up further. I used permutation tables, some assembly language that takes advantage of the Pentium's bit scan instruction, and any other tricks I could think of.
See later comments. I'll clean this up later.)
) Two (canonical) band CCs will have the same NC(band) if one can be permuted to the other using: relabeling (9!) and permutations for column-cells (6^9), box-columns (6^3) and boxes (6), i.e. 9! 3!^13 alternatives. (numbers reflect a 3x3 box grid, the 6 row permutations are subsumed under the column-cell permutations.) The rest of the post explains why this works and how to apply it to gangster hunting.