1、问题描述:
M行、N列棋盘，棋子从起始点P1按照中国象棋“马”的z走法，走跳遍所有点，每个点仅能走一次，最后一步跳至目的点P2。
2、算法分析:
有可采用两种算法，深度优先搜索(DFS)和广度优先搜索(BFS)。两种算法优劣可参考人工智能书籍中关于状态空间搜索算法分析。本人认为，只要方法得当，两种算法均可以求得问题的全部解。而针对“马踏棋盘”这个问题，DFS缺在效率上高于BFS，BFS求解过程的存贮空间需求要远低于BFS。DFS算法需要1个链栈表作为辅助，BFS算法需要2个双向链表。
3、实现伪码:
以下伪码实现DFS算法，函数返回TRUE表明求出一个解，数组BOARD 中各个元素值即为行走步骤。也可以逆向访问栈求解。修改部分代码可以求得全部通路，但是求解时间可能特别长(M=N=5,P1={0,0},P2={4,4}情况下求得全部解56个解时间在1秒左右)。
#define M 5
#define N 5
ElemType{POINT pt; BOOL expanded; void* parent;} 链表节点数据类型
STACK OPEN；
int BOARD[M][N]；//棋盘数组
int ExpandNode(POINT pt,POINT* pts);//根据某种策略扩展节点pt并保存在pts,返回扩展总数。
BOOL SearchByDFS(POINT P1,POINT P2) /*POINT P1,P2入口、出口点*/
{
ListNode tail,head;
POINT ptsExpanded[7];
int Marked=0;
ElemType append,data={P1,FALSE,NULL};
Push( OPEN,data );
BOARD[P1]=++marked;
while(NULL!=(tail=GetTop(OPEN)))//GetTop()返回栈顶指针
{
data=tail.data;
if( Marked==M*N && data.pt==P2) //最后一步并且是目标节点，OK
{
BOARD[data.pt]=++marked;
return TRUE;
}
if( data.expanded==TRUE )//该节点已经扩展过则移除
{
BOARD[data.pt]=0; --marked;
Pop( OPEN );
continue;
}
tail->data.expanded=true; BOARD[data.y][data.x]=++marked; //首先标记
numExpanded=ExpandNode( data.pt, ptsExpanded[]);//扩展节点
for(i=0;i<numExpanded;++)
{
append={ptsExpanded[ i], FALSE, (void *)tail };
Push(OPEN, append); //扩展节点放入OPEN表
}
}//end while
}
4。节点扩展策略：
函数ExpandNode(POINT pt,POINT* pts)的策略将极大影响求解效率及解的顺序。8个方位可供测试，若在棋盘上，再测试该点没有走过（BOARD[pt] ==0），若是目标点P2则应该满足当前已经走过的点数(marked)等于MN-1。
