Self-Avoiding Walks of a Rook on a Chessboard

Rook Paths is the name of a mathematical puzzle: how many different, non-intersecting paths are there for a rook, which start in the upper left corner of an M×N grid, and finish in the lower right corner.

The original question was for a standard chess board, i.e. an 8×8 grid. It turned out that the naive programming approach was way too slow for computing this.

Steven Finch has collected quite a bit of theory, some results and further links. There are also rather extensive tables of results. The puzzle archive has a short entry and a naive program. Here is the problem definition in the puzzle archive:

 ==> competition/games/chess/rook.paths.p <==
 How many non-overlapping paths can a rook take from one corner to the opposite
 on an MxN chess board?

• This is partially HTMLized, and appears to be kind of official. Here is a direct link to the rook paths solution.
• This has a keyword search and links to other puzzle sites. I extracted the above link from the short FAQ, which is archived in the news group "news.answers". Here are the corresponding direct links to the rook paths puzzle and its solution (including a small C program).

Frans Faase has extended his program for counting Hamilton cycles to even compute formulas for the number of rook paths for 3×N, 4×N and 5×N.

• My own Results
• My own Method of Computation

Back to the home page of Heiner Marxen.