马步遍历：骑士走遍棋盘每一格

题目

在国际象棋棋盘上，让马从某格出发，每步走“日”字（横2竖1或横1竖2），要求不重复地走遍全部 64 格。这能做到吗？若能回到起点（闭巡回），更好。

答案与解析

能做到。 早在 18 世纪，数学家就已找到 8×8 棋盘上的马步遍历（Knight’s Tour）。闭合巡回（最后一跳能回起点）也存在。

一个著名构造是“Warnsdorff 启发式”：每步都走向后续可去的格子数最少的那一格——这个贪心策略在 8×8 上几乎总能成功，配合少量回溯即可。它属于图论里的哈密顿路径/回路问题：把 64 格当顶点、合法马步当边，找一条经过所有顶点恰好一次的路径。

背后的数学

马步遍历是哈密顿问题的具象化。一般地，对 $m\times n$ 棋盘，何时存在闭巡回有完整判定（如 Schwenk 定理：除少数小尺寸外，矩形棋盘在边长不都小时都有闭巡回）。它也是算法课的常客——展示如何用启发式+回溯在巨大搜索空间里找解，而非暴力枚举 $64!\approx10^{89}$ 种走法。