Rook Endgame Problems in $m$ by $n$ Chess

Abstract

We consider Chess played on an $m\times n$ board (with $m$ and $n$ arbitrary positive integers), with only the two kings and the white rook remaining, but placed at arbitrary positions. Using the symbolic finite state method, developed by Thanatipanonda and Zeilberger, we prove that on a $3\times n$ board, for almost all initial positions, White can checkmate Black in $\le n+2$ moves, and that this upper bound is sharp. We also conjecture that for an arbitrary $m\times n$ board, with $m,n\ge 4$ (except for $(m,n)=(4,4)$ when it equals $7$), the number of needed moves is $\le m+n$, and that this bound is also sharp.