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?There are several locations to read the puzzle archive:
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.
Back to the home page of Heiner Marxen.