Newsgroups: rec.puzzles From: hoey@aic.nrl.navy.mil (Dan Hoey) Date: 1995/12/10 Subject: Re: Checkerboard Problem [more spoilers] Roland Curit asks how many paths there are from one corner of a checkerboard to the opposite corner, using edges of the squares. A path may cross itself but may not reuse an edge. Thanks to Roland for an interesting problem and to Jim Gillogly for showing it worthy of attack (or at least of a bit of weekend hacking). 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