==> competition/games/chess/rook.paths.s <==
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
}