《棋盘上的“马步”探究》(三)

时间:2022-11-17 11:06:34



0. 问题背景 (本课题为九年级组探究课题)


在中国象棋中,马的走法是一直一斜,棋谚“马走日字(本质上说,“马走日字”是走1×矩形的对角线)。从棋盘上任意一点出发,马能跳到任意的一个点。

《棋盘上的“马步”探究》(三)




4. 一个走“目”的“千里马”在整幅棋盘上,能否从任意一点,跳到指定点?


分析与解答

《棋盘上的“马步”探究》(三)

如上图所示,我们假设“千里马”是一只虫子,每次走一个“目”字,都需要爬过4个格子,即从A向一个方向走3格,转90°再走1格。这样,从A出发的任何路径上的每一个能走到的点,距离A的“距离”(即经过的格子数)都是4的倍数,即一个偶数。而从黑色格子(A)出发,终点为白色格子(B),必然需要经过奇数个格子。因此,走“目”字的千里马,从A走到B是不可能的,并且这和棋盘的大小无关。


另一种解法

上述结论还有另一个解法,也比较容易理解。

《棋盘上的“马步”探究》(三)

如上图所示,从一个黑色格子出发,下一步必然也在黑色格子中(即必然停留在同色格子内)。因此,无论如何都不可能从黑色格子走到白色格子,反之也一样。


研究与拓展


那么在10×9的整幅棋盘中,从任意一个位置出发,可以跳到的位置的范围是如何的呢?下面我来证明在棋盘中,任意黑色的格子之间可以相互走到,白色的格子之间也可以相互走到。当然,前文已经证明了黑白之间是走不到的。


《棋盘上的“马步”探究》(三)

假设左上角的黑色格子为起点,我采用“宽度优先搜索”的算法思想来构造走法。图中左上角标号为1,图中任意标号为i(i > 1)的格子,必然可以找到一个标号为i -1 的格子,通过千里马走到它。实际上标号就表示为从左上角出发,能到达这个格子的最短步数。也就是说,如果从左上角出发,任意黑色格子,最远只需要跳5步(最大标号6减去1)即可到达。


那么从左上角出发,到每一个黑色格子的路径,最终形成了一个树状结构,根节点(出发点)即为左上角的格子。对于任意两个黑色格子,只要从其中一个格子出发,先到达两个黑色格子的公共祖先(共同拥有的上级祖先),当然这里最远可以回到起点,然后再沿路跳转下去就可到达另一个黑色格子。即任意两个黑色格子之间,都存在路径可以到达。


用类似的方法,我们来构造白色格子间的树形结构。


《棋盘上的“马步”探究》(三)


如上图所示,以第一行第二列为起点,遍历结构和前文的黑色格子完全相同。同样方法可以证明,任意白色格子间也可以相互走到。


综上所述,把每个格子看作一个节点,将两两之间能跳到的格子间连边,通过这样的建图的方式,整幅10×9的棋盘的90个节点的图,实际上被构造成了两个互不联通的图。一个由所有黑色格子构成,另一个由白色格子构成,两个图中两两可达(即强连通),但两个图之间没有任何交集。





…… 后续问题探究 


上文我首先证明了如果是“目”字跳跃的马,是不可能遍历整个棋盘的,和棋盘的大小无关。同时还构造出在整幅棋盘中,黑色格子和白色格子为起点的马,采用“目”字跳跃的遍历范围,且最远只要跳 5 次就可以了。


现在问题来了,马的跳跃方法从“日”拓展到了到“目”,那么如果是一个 1 x n 的“千里马”呢?在一个无限大的棋盘里,这个“千里马”能从任意指定点出发,跳跃到另一个指定点么?