I used a recursive enumeration approach to get 4x4, but I got kind of tired of waiting for 5x5, so I did a hash table to chop out sub-trees that I had already evaluated, using Zobrist hashing to make it cheap to go from one position to the next. I have only fair confidence because I used a "check hash" approach to collision detection, and with only 32 bits of check I got some collisions in various tests of 4x4. They went away when I moved to a 64-bit check hash, but so far I've only done one pass at 5x5, so there's no confirmation. Naturally using the Bellman's rule if I get the same answer with three different seeds it's true, right? Or, for more confidence, save the whole position (efficiently represented, of course) intact rather than just a check hash.

The 1B number for 5x5 is the right order of magnitude: if you look at ratios of ratios for various rectangles, it appears that they approach 1 fairly rapidly: e.g.

ratio 2nd

1 x 4 16 2 x 4 335 20.9 3 x 4 9754 29.1 1.39 4 x 4 323632 33.2 1.14 5 x 4 11171466 34.5 1.03

The same thing works for n x 3 -- the 2nd ratios at 6x3 and 7x3 are

- 1.00. For n x 5 we get
1 x 5 32 2 x 5 1562 48.8 3 x 5 121130 77.5 1.59 4 x 5 11171466 92.2 1.19 5 x 5 1086297184 97.2 1.05

So it at least passes the gut test. I conjecture that 6 x 6 will be about 10^11, 7 x 7 about 10^13, and 8 x 8 about 10^15.

--

Jim Gillogly 19 Foreyule S.R. 1995, 06:52

**********************************************************************

Jim found there were over a billion paths through the 5x5 checkerboard, resorting to a program that used Zobrist hashing (I've never studied Zobrism) because the simple recursive search got too long to wait for. Using a different approach, I got results that

- agree with and extend Jim's; the results for squares are
- 1x1 . . . . . . 2 2x2 . . . . . . 16 3x3 . . . . . 800 4x4 . . . . 323632 5x5 . . . 1086297184 6x6 . . 30766606427588 7x7 7466577706821521924

I also have a large number of results for rectangles. The remainder of this message is a longish description of the method.

I decided that for a hairy combinatoric problem like this, I would do better to search with combs. A "comb" is a term I use to describe a structure on the integers {0,..,n}. A comb is a disjoint family of subsets of {0,..,n} containing one singleton and arbitrarily many pairs.

I work with what I call "toothed checkerboards"--checkerboards that have an extra set of edges (teeth) added along the right side. For instance, here is a 3x4 toothed checkerboard. We number the teeth from 0 to n (top to bottom).

---+---+---+---+---tooth 0 | | | | |

- ---+---+---+---+---* tooth 1
| | | | |

- ---+---+---+---+---* tooth 2
| | | | |

- ---+---+---+---+---* tooth 3

A path system (PS) on a toothed checkerboard is a set of nonoverlapping paths along the edges of the toothed checkerboard in which exactly one path has an endpoint in the upper-left corner of the checkerboard, and all other endpoints are at the ends of the teeth. For instance, here is a PS on a 5x5 toothed checkerboard.

corner

---------------\ /---Tooth 0| |

' /-------\ \---/ '

| |

' | ' | ' /---* Tooth 2

| | |

/--/ /--\ \------/ /--* Tooth 3 | | | | | | \-----------+---* Tooth 4 | | | \---/ ' ' ' \---* Tooth 5

There are three paths in this PS, from the corner to the tooth 0, from tooth 2 to tooth 4, and from tooth 3 to tooth 5.

A comb on {0,...,n} is said to "represent" a PS on an n-by-m toothed checkerboard when

1. the singleton of the comb contains the tooth-number of the

endpoint of the path starting in the corner,

2. the pairs of the comb are the tooth-numbers of the endpoints of

the other paths in the PS.

For instance, comb {{0},{2,4},{3,5}} represents the 5x5 PS above.

It should be clear that each PS is represented by exactly one comb. So to count PSs, we count the number represented by each comb, and add them up. The reason this helps is that combs capture the essential features necessary for extending an n-by-m PS into an n-by-(m+1) PS. This is done by finding the "successors" of each comb, in the sense that the {{0},{2,4},{3,5}} above is the successor of comb {{1},{3,4}}, which represents the above PS restricted to the 5x4 toothed checkerboard. Note that a comb can be the successor of another in more than one way, corresponding to multiple ways of extending a PS. So what I construct is a matrix of nonnegative integers, indicating the multiplicity of the successor relation. Exercise: Find the other way of extending a {{1},{3,4}} PS into a {{0},{2,4},{3,5}} PS.

A final touch is to be able to tell when a PS can be extended to a path through an entire checkerboard. This is done by connecting adjacent tooth endpoints of the paths in numerical increasing pairs, with the largest endpoint connected to the corner. If the result is a single path, that is the unique way to extend the n-by-m PS into a n-by-(m+1) checkerboard path. Note that in the example, by connecting tooth 0 to 2 and 3 to 4, we arrive at a path through the 5x6 checkerboard. It is straightforward to translate this criterion into a condition on the representative comb.

So I wrote a program to count these paths by comb. The number of

- combs for various heights of checkerboard are
height #combs height #combs height #combs

0 1 4 50 8 6876 1 2 5 156 9 26200 2 6 6 532 10 104456 3 16 7 1856

Which grows superexponentially, but not as badly as factorially. Generating the transition matrix, though, takes a considerable amount of time using a naive recursive search--there may be a better way of calculating transitions. A more pressing problem is the size of the transition matrix, which is the main reason I haven't got results for 8x8. But this should be within the range of PC-class machines if you take care to avoid running out of primary memory.

Dan Hoey@AIC.NRL.Navy.Mil