马踏棋盘.txt

马踏棋盘 讲述的是一些在棋盘上的算法

1. 问题描述
写出一个回溯算法来求解马周游问题：
给出一个8 ╳ 8的棋盘，一个放在棋盘某个位置上的马（规定马的走法为走“日”）是否可以愉好访问每个方格一次，并回到起始位置上？
2. 回溯法的一般思路
对于马所在其中一格时，它可以走的位置有以下8种情况：
⑧ ① 
⑦ ②
马 
⑥ ③
⑤ ④ 
所以对于每一个马所在的格子里，马可以走对应的8个方向。
用满8叉树，每一个子树对应马可跳的方向
当要走下一子树（跳下一格）时，该子树可走（还没有走过并且在棋盘里边），即沿该方向走下去，当不可以走，即回溯到上一步，选择另一方向往下走；当该子树的8个子棋都遍历完了（即8个方向都走过了），则回溯到它父亲那里。
重复一直做下去，到棋盘每个格子都走过一遍，而且回到出发点或者找不到路径即结束。
3. 求解问题的回溯算法描述
算法如下：
输入：V（x,y）马开始的起点
输出：马从第一步到最后一步（64）的先后次序数字......