<pre>
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
</pre>
