当前位置:鱼C工作室 >数据结构和算法 > 查看文章

马踏棋盘算法(骑士周游问题)- 数据结构和算法60

马踏棋盘算法(骑士周游问题)

 

让编程改变世界

Change the world by program


 

马踏棋盘算法(骑士周游问题)

 

题目渊源:

 

马踏棋盘问题(又称骑士周游或骑士漫游问题)是算法设计的经典问题之一。

 

题目要求:

 

国际象棋的棋盘为8*8的方格棋盘,现将“马”放在任意指定的方格中,按照“马”走棋的规则将“马”进行移动。要求每个方格只能进入一次,最终使得“马”走遍棋盘64个方格。

编写代码,实现马踏棋盘的操作,要求用1~64来标注“马”移动的路径(看演示)。

 

关于国际象棋“马”的走法

 

国际象棋“马”的走法

国际象棋“马”的走法

 

马踏棋盘的一个解

 

对于在n*n的棋盘上,当n>=5且为偶数的时候,以任意点作点都有解。

骑士周游问题

骑士周游问题

 

一些相关的知识点

 

回溯法:

之前我们谈过回溯法,还是那句话,指导思想很简单,就是一条路走到黑,碰壁了再回来一条路走到黑……一般和递归可以很好的搭配使用,还有深度优先搜索(DFS)。

 

哈密尔顿路径:

图G中的哈密尔顿路径指的是经过图G中每个顶点,且只经过一次的一条轨迹。如果这条轨迹是一条闭合的路径(从起点出发不重复地遍历所有点后仍能回到起始点),那么这条路径称为哈密尔顿回路。

 

算法描述及代码编写

 

那么就让我们愉快的开始今天的代码之旅吧!

参考代码


为您推荐

报歉!评论已关闭.