马走日棋盘算法

马走日棋盘算法2010-01-23哈达问题描述

在给定大小的方格状棋盘上, 将棋子”马”放在指定的起始位置 , 棋子”马” 的走子的规则为必须在棋盘上走”日”字; 从棋子”马”的起始位置开始, 搜索出一条可行的路径, 使得棋子”马”能走遍棋盘上的所有落子点, 而且每个落子点只能走一次;

例如: 棋盘大小为5*5 , 棋子马放的起始落子点为（ 3 , 3 ） ; 算法需要搜索一条从位置（ 3 , 3 ）开始的一条包括从（ 1 , 1 ） , （ 1 , 2 ） , （ 1 , 3 ） … （ 5 , 1 ） , （ 5 , 2 ） , （ 5 , 3 ） , （ 5 , 4 ） , （ 5 , 5 ）总共25个可以落子的全部位置;

问题分析

通过上面的问题描述,我们对问题的内容有了正确的理解,接下来我们开始对问题进行具体细致的分析,以求找到解决问题的正确的可行的合理的方法;

首先我们需要在程序中用合适的数据结构表示在问题中出现的棋盘 , 棋子 , 棋子的走子过程 ; 接下来我们需要对核心问题进行分析, 即如何搜索一条可行的路径 , 搜索采取何种策略 , 搜索的过程如何表示 ;

对于一个大小为n*m大小的棋盘 , 棋子从当前位置（ x , y ）出发,可以到达的下一个位置（ x’ , y’ ）:

（1）（ x +1 , y +2 ）

（2）（ x +1 , y –2 ）

（3）（ x – 1, y +2 ）

（4）（ x – 1, y – 2 ）

（5）（ x +2, y +1）

（6）（ x +2, y – 1）

（7）（ x -2, y + 1）

（8）（ x -2, y – 1 ）