棋盘上的“马步”探究

正文

请到「今天看啥」查看全文

这个问题的上述解法，是基于构造完成的，即构造出了一条遍历所有节点的遍历路径。每个点只走一次的路径，也叫做哈密尔顿路径。我认为还有另一个解法可以讨论。如下图所示，从某一个节点出发，只需要跳 3 步，即可到达相邻的位置。图中给出了以左上角和中心点这两个格子为起点的走法。这个操作所需的最大空间为3×4，所以半幅棋盘的空间足够让马跳到相邻的格子上。因此可以证明从任意方格出发，都可以在3步后到达相邻的位置。那么经过拓展，自然也就可以从任意方格出发，经过有限步，构造出一系列相邻的方格为路径，到达任意目标方格。所以起点为A时一定也能做得到，是这个结论的一个特例。

2. 在图中半幅棋盘上，马从点A出发，能否跳遍半个棋盘，且每个点恰都只走到一次？

分析与解答

如下图所示，我们将矩阵划分为黑白间隔的样式。马每走一步，必然会跳到一个异色的方格，即从黑色的跳到白色的，或是相反。因此，马跳过的任何一条路径，必然是由黑白间隔的方格组成的序列。如果从任意白色方格出发，且途中每个方格只能经过一次，则整条线路上白色方格的数量必须等于黑色方格的数量，或者比黑色方格的数量大1。而半幅棋盘，总共有45个方格，其中黑色方格为23个，白色方格为22个。因此，从任意白色方格出发，包括A点，不重复地遍历整个棋盘是不可能的。

3. 半幅棋盘上，从哪些点出发，能跳遍半个棋盘，且每个点都只跳一次？

分析与解答

如上题解答中的分析，从任何白色方格出发，都不可能不重复地遍历整个棋盘。而从任意黑色方格出发，遍历整个棋盘，每个方格只走到一次，是可能的。接下来，我们要证明这不仅是可能的，而且确实有解。如下图所示，棋盘中所有的黑色方格一共有23块，因为对称性，如果以其中用字母标出的这8块方格为起点，可以分别构造出一条哈密尔顿路径，则所有黑色方格都可以作为路径的起点了。

下图给出了以这8个黑色方格为起点的行走方案。所以，以图中任何一个黑色方格为起点，都是存在一条哈密尔顿路径的；而以任何一个白色方格为起点，是不可能做到的。

请到「今天看啥」查看全文