马能否走遍棋盘的可达性证明

而题目本身要求输出 个答案，仅输出就至少需要：

所以对于原题，BFS 已经达到最优复杂度量级。

不过，继续考虑两个问题：

1. 如果只询问到某一个点的距离，是否存在直接公式？
2. 是否存在马永远到不了的点？

显然这两个问题必须区分有限棋盘与无限棋盘。

一、无限棋盘上的单点最短距离公式

将起点平移到原点 ，目标点记为 。

由于马步关于坐标轴和直线 对称，只需令：

于是总有：

在无限棋盘上，最短步数为：

其他情况

其中先计算：

再按照奇偶性修正：

例如：

这个公式中的三个限制

马的一步位移为：

首先，较大的坐标差每一步最多减少 ，因此：

其次，坐标绝对值之和每一步最多减少 ，因此：

所以：

最后，马每走一步，坐标和的奇偶性都会翻转。因为一步中坐标和的变化量一定是奇数：

因此，若走 步到达 ，必须满足：

所以，当 与 奇偶性不同时，还需要再加一步。

两个特殊点 与 属于距离过小造成的局部例外，需要单独处理。

例如：

因此从原点到 可以三步到达，但不可能更少。

二、为什么这个公式不能解决原题

上面的公式针对的是无限棋盘。

原题中的棋盘存在边界，而无限棋盘上的最短路径可能会暂时跳出矩形区域。

例如，在无限棋盘上：

所以从 到 可以两步到达。

但在 棋盘中， 已经越界，这条路径不合法。事实上，中心点 没有任何合法马步与其他位置连接。

从左上角出发时，距离表为：

因此：

无限棋盘上的最短距离有限棋盘上的最短距离

有限棋盘中，边界会改变整张马步图的结构，所以原题仍应使用 BFS。

三、无限棋盘上有没有永远到不了的点

没有。

这个结论可以直接通过生成元证明。

把所有整数格点组成的集合视为加法群：

马的一步能够产生的位移向量为：

记这些向量生成的子群为：

只需证明：

因为 与 生成整个 。

首先：

所以：

对应路径为：

其次：

所以：

对应路径为：

于是，对任意整数点 ，都有：

因此：

即无限棋盘上，马可以到达任意整数格点。

四、尝试黑白染色

将棋盘按照 的奇偶性染成黑白两色。

马每走一步， 的奇偶性都会翻转，因此格子颜色也会翻转。

所以，如果目标点与起点同色，则所需步数一定为偶数；如果目标点与起点异色，则所需步数一定为奇数。

即：

但是，这只能限制步数的奇偶性，不能证明某个点不可达。

例如， 与原点异色，所以它必须经过奇数步到达；而它确实可以在三步后到达：

因此在无限棋盘上，染色法约束步数奇偶，但不产生不可达点。

五、有限矩形棋盘什么时候连通

考虑一个没有障碍物的 矩形棋盘，不妨设：

结论为：

的马步图连通，或且

换言之，除单格棋盘外，不连通的矩形棋盘只有：

下面分别证明。

六、 棋盘不连通

如果棋盘只有一行，马不存在任何合法移动。

因为马的一步至少需要跨越两行或三行，而棋盘中只有一行。

因此当 时，每个格子都是孤立点：

不连通

七、 棋盘不连通

如果棋盘只有两行，马的一步不可能让行号变化 ，否则会越界。

因此，合法移动只能满足：

行列

也就是说，列编号每次只能变化 ：

于是列编号的奇偶性保持不变。

从奇数列出发，永远到不了偶数列；从偶数列出发，永远到不了奇数列。

因此：

不连通

这里的不变量是：

列编号模的余数

八、 棋盘不连通

考虑中心点 。

从中心点出发，马无论走：

还是：

都会越界。

所以中心点没有任何邻点。由于马步可逆，也没有任何其他点能够到达中心点。

因此：

不连通

九、 棋盘连通

下面给出一条经过全部十二个格子的合法路径。表格中的数字表示访问顺序：