马踏棋盘问题

来自计算思维百科
跳转至: 导航搜索
马踏棋盘问题1.png

将马放到国际象棋的8*8棋盘上的任意指定方格中,按照“马”的走棋规则将“马”进行移动,要求每个方格进入且只进入一次,走遍棋盘上的64个方格,将数字1,2,3…,64依次填入一个8*8的方阵。马在国际象棋中的走法如右图所示。

涉及的计算思维

解决这个问题可以利用到计算机中的两种方法,一种是深度优先搜索,也就是回溯法,体现了计算思维的递归思想。另一种是利用贪心法进行再优化,总是选择最优者,体现了计算思维的“规划”思想。

解决方案

方案一――深度优先搜索法

我们可以采用深度优先法求解,深度优先搜索是指对每一个可能的分支路径深入到不能再深入为止,而且每个节点只能访问一次。如图1所示,当马在当前位置时(节点1),将它下一跳的所有位置看作分支结点,然后选择一个分支结点进行移动,如节点2,然后再走该结点的分支结点,如节点3,如果节点3不能再走下去,则退回到节点2,再选择另一种走法,如节点4,一直走下去,直至不能派生出其他的分支结点,也就是“马”走不通了。此时则需要返回上一层结点,顺着该结点的下一条路径进行深度优先搜索下去,直至马把棋盘走遍。

马踏棋盘问题2.png

图1

方案二——贪心法

贪心法是指,在对问题求解时总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,该方法所做出的仅是在某种意义上的局部最优解。我们在回溯法的基础上,用贪心法进行优化,在每个结点对其子结点进行选取时,优先选择“出口”最少的进行搜索,“出口”的意思是在这些子结点中它们的可行子结点的个数,也就是“孙子”结点越少的越优先跳,因为这样选择时出口少的结点会越来越少,这样跳成功的机会就更大一些。

如下图,可以先选择3、4、5、6这几个“出口”少的先跳,跳完一步再选择“出口”少的往下跳,如没有可跳出则回溯上一结点。

马踏棋盘问题3.png