有这么一个问题: 国际象棋中马按照“马跳日”的规则行走. 一匹马从下图标记为 \(A\) 的点出发, 能否不重复不遗漏的走过每个点, 最后停在标记为 \(33\) 的点?
Chessboard and Knight’s tour problem
答案是: 不可以! 但是, 最后可以停在标记为 \(B\) 的点, 按照这个顺序行走, 就可以
\begin{equation}A\rightarrow1\rightarrow2\rightarrow\cdots\rightarrow43\rightarrow B.\end{equation}
这是一个 \(5\times9\) 的棋盘. 可以考虑从任意一点出发, 不重复不遗漏的走过每个点, 最后停在某个指定的点. 这个最后的落脚点当然也可以是出发点. 显然的, 这个事情, 有时候可以实现, 有时候令人遗憾. 赋予处于第 \(i\) 行第 \(j\) 列的点一个数 \(i+j\), 那么, 有下述性质：
当马从一个点跳到另一个点的时候, 这两个点所赋予的数, 奇偶性是不同的.
注意, 对于这个 \(5\times9\) 的棋盘, 赋予的 \(45\) 个数, 有 \(23\) 个偶数, \(22\) 个奇数. 于是, 只有从赋予的数是偶数的点出发, 才有成功的可能. 那么, 是不是随意指定两个赋予的数是偶数的点, 马就可以从一个出发, 不重复不遗漏的走过每个点, 最后停在另一个? 这个比较困难. 事实上, 这个问题, 和图论（graph theory）中的 哈密尔顿道路（Hamiltonian path）或哈密尔顿圈（ Hamiltonian cycle） 有关. 不过, 把 \((1)\) 稍作修改, 就可证明: 马从任意一个赋予的数是偶数的点出发, 不重复不遗漏的走过每个点,最后停在某个赋予的数是偶数的点.
怎么证明 \(4\times4\) 或 \(5\times5\) 的棋盘, 不存在哈密尔顿道路? 看下图, 从标记为 \(A\) 的点出发, 只能落在标记为 \(B\) 的点:
Chessboard and Knight’s tour
很自然的一般性问题是: 考虑 \(m\times n\)\(（m\leq n)\) 的长方形棋盘.