【大话数据结构C语言】43 图的应用 - 马踏棋盘算法

题目要求：

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

 

马的走法就是以下几种

 

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

 

 

回溯法：

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

哈密尔顿路径：

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

 

 

 

 

TravelChessBoard.c

#include 
#include 

#define X 8
#define Y 8

int chess[X][Y];

// 找到基于(x,y)位置的下一个可走的位置
int nextxy(int *x, int *y, int count)
{
    switch(count)
    {
        case 0:
            if( *x+2=0 && chess[*x+2][*y-1]==0 )
            {
                *x = *x + 2;
                *y = *y - 1;
                return 1;
            }
            break;

        case 1:
            if( *x+2=0 && chess[*x-1][*y-2]==0 )
            {
                *x = *x - 1;
                *y = *y - 2;
                return 1;
            }
            break;

        case 7:
            if( *x-1>=0 && *y+2