一个有趣的 5 X 5 方阵一笔画问题

分手后的思念是犯贱 2021-11-04 13:30 1001阅读 0赞

![image.png][]  
  这个问题是在我上小学时同学告诉我的，当时觉得好玩，就随便瞎画这玩儿，不过从小学到大学，没有一次画成功过。这个问题起初同学告诉我的时候，图不是这样画的，我只是为了好表达，将问题抽象成网格了，原问题是说有25个小球，如下图：  
![image.png][image.png 1]  
用一笔画，将所有蓝色小球串起来，要求画出的线不允许超过矩阵之外，不允许斜，且每个小球只被经过一次。  
两种对问题描述的本质是一样的。  
  答案是我的大学同学用数学方法找到的，本质上这确实是一个数学问题，他给出的结论是：不可能存在一条满足要求的路线，证明过程如下：  
![image.png][image.png 2]  
  将小球相间着涂成不同颜色，这样，就出现黑球相邻的周围是白球，白球相邻的周围是黑球（忽略橙色球）。换句话说，假如要连线的话，被这条线连起来的小球形成的顺序串儿，一定是黑白小球相间的，不可能出现同色小球相邻。另外，数一数黑色和白色小球的个数，你会发现，黑球有13个，白球有11个，这就存在一个矛盾：要求把所有黑色和白色球都串起来的话，就会出现，13个黑球和11个白球异色相间地出现在一个序列里。而这中情况不可能出现，因为异色相间的有限序列，两色个数相差不可能超过1，即出现矛盾。到这里，确实感觉我的同学的方法很巧妙，甚是佩服。  
  虽然知道此题的结果，但作为一个程序员还是手痒，心生要写一个可视化寻路算法。请参考文章链接《 [5 X 5 方阵引出的寻路算法 之 小试牛刀][5 X 5 _ _]》和《[5 X 5 方阵引出的寻路算法 之 迷宫探秘][5 X 5 _ _ 1]》，附程序链接 [矩阵寻路][Link 1] 和 [迷宫探秘][Link 2]。

转载于:https://www.cnblogs.com/hudk/p/11208708.html

[image.png]: /images/20211104/cc4d2b7796d04ea5a504a453b0dc367a.png
[image.png 1]: /images/20211104/e9e524ccb6bb45ae9508d1a152c46fd6.png
[image.png 2]: /images/20211104/cea5a53c987a4625967f8c4d15aa913b.png
[5 X 5 _ _]: http://www.mjhdk.cn/articles/2019/07/18/1563436984871.html
[5 X 5 _ _ 1]: http://www.mjhdk.cn/articles/2019/07/18/1563437230679.html
[Link 1]: http://www.mjhdk.cn/matrix1
[Link 2]: http://www.mjhdk.cn/maze