趣闻：象棋的马能走遍棋盘么？

引入

小时候和舅舅下象棋的时候，我觉得马的移动很受限制，因为我总是得花些力气才能将马移动到我想要移动到的位置，感觉就很别扭。直到我长大以后我才直到马其实是可以走到任意一个格点的，虽然说经验上如此，但是我从未我听说过严格证明，今天在逛贴吧的时候看帖子受到启发，决定证明这个命题。

命题：中国象棋的棋子“马”在不违反蹩腿规则下在有限的移动步数下可以走到整个棋盘的任意一个格点。

接下来我将证明这个命题。

证明过程

试将整个中国象棋棋盘看作是一个平面直角坐标系. 这是一个很自然的过程，如果平面直角坐标系只有格点，那么整个坐标系自然就可以画出一个一个的方格.

已知象棋棋盘是9列10行共90个格点，我们取第一象限的部分将它视为棋盘，则有：

$$0\le x\le 8,x\in \mathbb{Z}$$$$0\le y\le 9,y\in \mathbb{Z}$$

这样取出来的所有点就是象棋棋子可以走的点.

接下来我们看“马”这个棋子的规则，马只能走日字形的对角线顶点，如果将其视为向量的话，就可以对应这些向量：

$${\xi }_1=[2,1{]}^T$$$${\xi }_2=[1,2{]}^T$$$${\xi }_3=[-2,1{]}^T$$$${\xi }_4=[-1,2{]}^T$$$${\xi }_5=[-2,-1{]}^T$$$${\xi }_6=[-1,-2{]}^T$$$${\xi }_7=[2,-1{]}^T$$$${\xi }_8=[1,-2{]}^T$$

这分别对应了横着的四种日和竖着的四种日，其中后四种是前四种的反方向，所以可以简化问题为只取前四种向量. 不难发现当且仅当$k_1=k_2=0$时，有：

$$k_1{\xi }_1+k_2{\xi }_2=0$$

成立.

这意味着这两个向量是线性无关的，而在棋盘抽象出的二维直角坐标系下需要两个线性无关的变量作为基底就可以表示出空间中的任意一个向量，或者说是，点（因为我们只关心他的终点）. 这些点当然也包括我们在第一象限划定出的那些点. 但这还不够，由于象棋的步数是量子化的，我们不可能在实际过程中走0.5步，所以接下来我们得证明在整数步数下，我们可以走到任意一个划定的格点上去.

我们设按照前四个向量的走法各走$a_i(i=1,2,3,4)$步，那么$a_i\in \mathbb{Z}$. 在这里我们无需在意$a_i$的正负，因为我们负数意味着朝着相反方向走，只需要确保是整数就可以. 那么最后落点为$P=[x,y{]}^T$时，有：

$$\mathrm{\Xi }A=P$$

其中$\mathrm{\Xi }=[{\xi }_1,{\xi }_2,{\xi }_3,{\xi }_4]$，$A=[a_1,a_2,a_3,a_4{]}^T$

接下来的思路就是我们能否通过这四个向量的线性组合生成出二维空间的标准基底$e_1=[1,0{]}^T$和$e_2=[0,1{]}^T$，若可以则可以通过$e_1$和$e_2$的线性组合来表示出$90$个格点，因为对于任意一个格点$P$都隐含着$P=x{e}_1+y{e}_2$. 这对解题很有帮助.

所以我们要解的方程是：

$$\mathrm{\Xi }{A}_1=e_1$$$$\mathrm{\Xi }{A}_2=e_2$$

方程组系数矩阵只有2行，所以方程组相对于满约束状态是欠约束的，相当于补了两行$0$后的一个降秩矩阵. 所以方程有无穷多解,我们在这无穷组解中要找到一组整数解.

可以通过简单的带入试数得到一组整数解：

$$A_1=[4,-3,2,0{]}^T$$$$A_2=[-2,2,-1,0{]}^T$$

由于棋盘上任意一格点$P$（甚至是整个平面空间的点）都隐含着$P=x{e}_1+y{e}_2$，带入可得：

$$P=x\mathrm{\Xi }{A}_1+y\mathrm{\Xi }{A}_2$$$$=\mathrm{\Xi }(x{A}_1+y{A}_2)$$

将后边的加和部分写成$M$，则：

$$P=\mathrm{\Xi }M$$

其中$M$对应的四个分量就是四种走法对应次数.

我知道到这里还有一个不严谨的点就是我们所有计算都基于马在$[0,0{]}^T$，但是实际上那里是车，马在$[1,0{]}^T$，但是这个问题不大，我们可以在所有的移动之前都减去一个$\mathrm{\Xi }{A}_1$也就是$e_1$，这样得到的就是从$[1,0{]}^T$出发到达对应点的走法. 其他三个位置的马也可以通过类似的操作根据自己的位置来修正自己的路线.

至此命题已被证明，中国象棋的棋子“马”在不违反蹩腿规则下在有限的移动步数下可以走到整个棋盘的任意一个格点。

后日谈……

这个问题就是我一拍脑门想到的一个小问题，我刚开始的思路还有点错误，后来是一点一点想出来正确思路的，但其实这个证明有一个小瑕疵就是可能在自动过程中被移动到了棋盘外，但是其实你仔细想一下就发现这个问题可以通过改变操作顺序消除，比如先往右跳可能会跳出棋盘，可以把右跳操作提前用掉，在棋盘边缘只使用上跳；或者取其他整数解构建标准基，这里略微不严谨但是我不知道如何证明所有的操作都可以在不出棋盘的情况下完成（这是一定的，因为有人已经做了实验让马走遍棋盘了）。

虽然这个问题里貌似不太严谨，但是如果问题变一下就能严谨的证明了，把问题换成证明相不能走遍半个棋盘，因为对应的操作向量构建不出标准基所以这是一定不可能的。

再者还有就是对于国际象棋的马能不能走遍整个棋盘我还没尝试证明，如果将左上角的格点代表这个格子的话国际象棋的马和中国象棋的马移动的操作向量是一样的，所以大概率也是可以走遍棋盘的，核心思路应该也是如何让马在横向和纵向走一格。

最后的最后，太伟大了线性代数！