国际象棋中马怎么不重复跳完所有格子
2024-07-18 10:26:59作者：饭克斯
国际象棋中马按规则从任一点开始将所有格跳过一次(不重复)。
我的算法分析如下：
国际象棋马的走法：先直走或横走一格，再沿离开原来格子的方向斜走一个，合起来为一步棋；国际象棋棋盘黑白交错，格数8×8，根据马的走法，它只能从白格走向黑格，再从黑格走向白格，与此类推。
格子具有集合性，故考虑使用无向图来表示格子及其间关系；以邻接表作为该无向图中结点与相邻8个结点（4黑4白）的存储结构；以顶点表存储格子，每格为顶点表中一结点，其指针域有二，左指针链接黑格邻接表，右指针链接白格邻接表，其结点域为访问标识，访问过则为1，未访问为0；如用c实现，顶点表的头结点（下标为0的数组元素）不用，用来标识每一步的访问方向（先黑后黑或者先白后白）。
(b=black,w=white)
b1w1b2w2
w3b3w4b4
b5w5b6w6
w7b8w8b8
以b3为顶点，得顶点表与邻接表片断如下
...
b6;w1-->;w3-->;w4-->;w5
...
采用图的深度遍历算法，以方向标识的取值作为约束条件，每两个半步置值（0/1），以访问标识作为是否访问该结点或跳至下一结点的判断条件，访问所有的结点（可加一计数因子或直接在头顶点开多一域来计数）。
这样便可得到遍历的一条途径。如想得到所有可能的途径，可以在这个算法基础上加以扩展。
展开全文
