How many non-overlapping paths can a rook take from one corner to the opposite on an MxN chess board?
competition/games/chess/rook.paths Added material
Problem
How many non-overlapping paths can a rook take from one corner to the opposite on an MxN chess board?
Show solution
For a 1 x 1 chessboard, there are 1 unique paths.
For a 1 x 2 chessboard, there are 1 unique paths.
For a 1 x 3 chessboard, there are 1 unique paths.
For a 1 x 4 chessboard, there are 1 unique paths.
For a 1 x 5 chessboard, there are 1 unique paths.
For a 1 x 6 chessboard, there are 1 unique paths.
For a 1 x 7 chessboard, there are 1 unique paths.
For a 1 x 8 chessboard, there are 1 unique paths.
For a 2 x 2 chessboard, there are 2 unique paths.
For a 2 x 3 chessboard, there are 4 unique paths.
For a 2 x 4 chessboard, there are 8 unique paths.
For a 2 x 5 chessboard, there are 16 unique paths.
For a 2 x 6 chessboard, there are 32 unique paths.
For a 2 x 7 chessboard, there are 64 unique paths.
For a 2 x 8 chessboard, there are 128 unique paths.
For a 3 x 3 chessboard, there are 12 unique paths.
For a 3 x 4 chessboard, there are 38 unique paths.
For a 3 x 5 chessboard, there are 125 unique paths.
For a 3 x 6 chessboard, there are 414 unique paths.
For a 3 x 7 chessboard, there are 1369 unique paths.
For a 3 x 8 chessboard, there are 4522 unique paths.
For a 4 x 4 chessboard, there are 184 unique paths.
For a 4 x 5 chessboard, there are 976 unique paths.
For a 4 x 6 chessboard, there are 5382 unique paths.
For a 4 x 7 chessboard, there are 29739 unique paths.
For a 4 x 8 chessboard, there are 163496 unique paths.
For a 5 x 5 chessboard, there are 8512 unique paths.
For a 5 x 6 chessboard, there are 79384 unique paths.
For a 5 x 7 chessboard, there are 752061 unique paths.
/***********************
* RookPaths.c
* By: David Blume
* dcb@wdl1.wdl.loral.com (Predecrement David)
*
* How many unique ways can a rook move from the bottom left corner
* of a m * n chess board to the top right right?
*
* Contraints: The rook may not passover a square it has already visited.
* What if we don't allow Down & Left moves? (much easier)
*
* This software is provided *as is.* It is not guaranteed to work on
* any platform at any time anywhere. :-) Enjoy.
***********************/
#include <stdio.h>
#define kColumns 8 /* The maximum number of columns */
#define kRows 8 /* The maximum number of rows */
/* The following rule is for you to play with. */
#define kAllowDownLeft /* Whether or not to allow the rook to move D or L */
/* Visual feedback defines... */
#undef kShowTraversals /* Whether or nor to show each successful graph */
#define kListResults /* Whether or not to list each n * m result */
#define kShowMatrix /* Display the final results in a matrix? */
char gmatrix[kColumns][kRows]; /* the working matrix */
long result[kColumns][kRows]; /* the result array */
/*********************
* traverse
*
* This is the recursive function
*********************/
traverse (short c, short r, short i, short j )
{
/* made it to the top left! increase result, retract move, and return */
if (i == c && j == r) {
#ifdef kShowTraversals
short ti, tj;
gmatrix[i][j] = 5;
for (ti = c; ti >= 0; ti--) {
for (tj = 0; tj <= r; tj++) {
if (gmatrix[ti][tj] == 0)
printf(". ");
else if (gmatrix[ti][tj] == 1)
printf("D ");
else if (gmatrix[ti][tj] == 2)
printf("R ");
else if (gmatrix[ti][tj] == 3)
printf("L ");
else if (gmatrix[ti][tj] == 4)
printf("U ");
else if (gmatrix[ti][tj] == 5)
printf("* ");
}
printf("\n");
}
printf("\n");
#endif
result[i][j] = result[i][j] + 1;
gmatrix[i][j] = 0;
return;
}
/* try to move, left up down right */
#ifdef kAllowDownLeft
if (i != 0 && gmatrix[i-1][j] == 0) { /* left turn */
gmatrix[i][j] = 1;
traverse(c, r, i-1, j);
}
#endif
if (j != r && gmatrix[i][j+1] == 0) { /* turn up */
gmatrix[i][j] = 2;
traverse(c, r, i, j+1);
}
#ifdef kAllowDownLeft
if (j != 0 && gmatrix[i][j-1] == 0) { /* turn down */
gmatrix[i][j] = 3;
traverse(c, r, i, j-1);
}
#endif
if (i != c && gmatrix[i+1][j] == 0) { /* turn right */
gmatrix[i][j] = 4;
traverse(c, r, i+1, j);
}
/* remove the marking on this square */
gmatrix[i][j] = 0;
}
main()
{
short i, j;
/* initialize the matrix to 0 */
for (i = 0; i < kColumns; i++) {
for (j = 0; j < kRows; j++) {
gmatrix[i][j] = 0;
}
}
/* call the recursive function */
for (i = 0; i < kColumns; i++) {
for (j = 0; j < kRows; j++) {
if (j >= i) {
result[i][j] = 0;
traverse (i, j, 0, 0);
#ifdef kListResults
printf("For a %d x %d chessboard, there are %d unique paths.\n",
i+1, j+1, result[i][j]); fflush(stdout);
#endif
}
}
}
/* print out the results */
#ifdef kShowMatrix
printf("\n");
for (i = 0; i < kColumns; i++) {
for (j = 0; j < kRows; j++) {
short min = (i < j) ? i : j ;
short max = (i < j) ? j : i ;
printf("%6d", result[min][max]);
}
printf("\n");
}
#endif
}
Additional material
This problem, especially for an 8x8 standard chess board, has been
raised on the IAMS mailing list. Several people were reported to have
computed the function for up to 7x8. It seems to be not easy to go
beyond that. I seem to be the first who managed that. My current table
of results:
2 3 4 5 6 7 8
2 2
3 4 12
4 8 38 184
5 16 125 976 8512
6 32 414 5382 79384 1262816
7 64 1369 29739 752061 20562673 575780564
8 128 4522 163496 7110272 336067810 16230458696 789360053252
9 256 14934 896476 67005561 5493330332 459133264944 38603590450777
10 512 49322 4913258 630588698 89803472792
To compute the 8x8 a HP-apollo/710 spent 470 seconds (<8 min).
There are also some theoretic results.
Let F(n,m) be the function in question.
F(1,n) = 1 is trivial
F(2,n) = 2^(n-1) can be shown easily.
For F(3,n) I have found 3 mutually recursive functions:
MS(1) = 1 MS(2) = 3
SS(1) = 1 SS(2) = 3
DD(1) = 1 DD(2) = 4
MS(y) = SS(y-1) + MS(y-1) + DD(y-1) [y>=2]
SS(y) = SS(y-1) + MS(y-1) + sum(k=1,y-1: DD(k)) [y>=2]
DD(y) = DD(y-1) + 1 + MS(y-1) + sum(k=1,y-1: SS(k)) [y>=2]
Now F(3,n) = DD(n).
For MS I have also found
MS(y) = 3MS(y-1) + MS(y-2) [y>=2] [Let MS(0)=0]
from which I have deduced
MS(n) = (a^n - b^n) / sqrt(13) = (a^n - b^n) / (a - b)
where
a = (3 + sqrt(13)) / 2 [ca 3.3027756377 ]
b = (3 - sqrt(13)) / 2 [ca -.3027756377 ]
I have no explicit formula for DD, but I did not try very hard to find
one. The recursive formula already allows efficient (linear)
computation of DD(n).
DD( 0) = 0
DD( 1) = 1
DD( 2) = 4
DD( 3) = 12
DD( 4) = 38
DD( 5) = 125
DD( 6) = 414
DD( 7) = 1369
DD( 8) = 4522
DD( 9) = 14934
DD(10) = 49322
DD(11) = 162899
DD(12) = 538020
DD(13) = 1776961
DD(14) = 5868904
DD(15) = 19383672
DD(16) = 64019918
DD(17) = 211443425
DD(18) = 698350194
DD(19) = 2306494009
DD(20) = 7617832222
DD(21) = 25159990674
DD(22) = 83097804242
DD(23) = 274453403399
DD(24) = 906458014440
DD(25) = 2993827446721
DD(26) = 9887940354604
DD(27) = 32657648510532
DD(28) = 107860885886198
DD(29) = 356240306169125
DD(30) = 1176581804393574
DD(31) = 3885985719349849
-- Heiner Marxen <heiner@drb.insel.de>, September 1993
Here are some more values:
5 x 8: 7,110,272
6 x 6: 1,262,816
6 x 7: 20,562,673
6 x 8: 336,067,810
7 x 7: 575,780,564
7 x 8: 16,230,458,696?
I'm embarrassed to say I'm not sure of the last value... normally longs
are big enough for me, and I didn't even make this darned thing
unsigned. The value came out -949410488, and I estimated that it should
have been in the neighborhood of 1.6 * 10^10... so I subtracted this
value from 2^32 and added a few more 2^32's until the value got close to
what I wanted to see. I didn't have the heart to run the bugger again.
I tried a couple of things to get improvements over the obvious brute
force. The main successful one was to observe that if you're ever moving
away from the goal and you're on an edge, then you've cut yourself off
and won't have any solutions from that point on. This was a major win.
It doesn't prune all the possible spirals and other annoyances, but does
get most of the biggest ones.
The one that I had great hopes for but which wasn't very successful is a
transposition table, as used in chess programs. Zobrist hashing is
perfect for this application, since you can get a new hash for a
position with a single XOR. Then simply allocate as large a hash table
as you can and save the number of paths from each known position; since
you can get to many positions in several ways, I thought it might help a
lot. It didn't -- I got a fair amount of saved search effort, but for
small values of m and n the overhead ate up the profits. For large
values of m and n (like 6x8 or so) it was a small improvement -- lots of
transpositions saved, and about a 5% overall gain in running time. Big
deal.
I tried a few heuristics with the transposition table, but no joy. The
most interesting one was replacing a position in the table that had
fewer total paths than the one I proposed to replace it with. No
visible improvement. There may be room for hackery there.
But at this point, probably simply a divide and conquer with a mass of
hardware is the easiest way to get 8x8... if anybody cares enough. I
estimate the value will be in the neighborhood of 7.6 x 10^11, which
isn't that far above the 7x8 number.
-- Jim Gillogly <jim@rand.org>, November 1993
I have been running a background job for the last 6 months to count the
paths for various sized boards up to 8 by 8. Here are the results:
[ Editor: the counts for boards up to 5 by 7 agree with the table in the
entry above and are omitted. ]
A 5 by 8 chessboard has 7,110,272 different nonintersecting rook paths.
A 6 by 6 chessboard has 1,262,816 different nonintersecting rook paths.
A 6 by 7 chessboard has 20,562,673 different nonintersecting rook paths.
A 6 by 8 chessboard has 336,067,810 different nonintersecting rook paths.
A 7 by 7 chessboard has 575,780,564 different nonintersecting rook paths.
A 7 by 8 chessboard has 16,230,458,696 different nonintersecting rook paths.
An 8 by 8 chessboard has 789,360,053,252 different nonintersecting rook paths.
-- Dave Dodson <dodson@convex.COM>, June 1994
[ Editor: the three computations agree with one another, confirming
Gillogly's doubtful 7 x 8 value. ]
I thought you might take interest in a new web page,
"Self-Avoiding Walks of a Rook on a Chessboard"
at URL
http://www.mathsoft.com/asolve/index.html
Please look over carefully and contact me with corrections
and suggestions. I would be delighted to receive more numbers
to fill out the tables. Is anyone aware of other references,
especially with regard to the asymptotic problem?
-- Steven Finch <sfinch@mathsoft.com>, September 1996