马踏棋盘是经典的程序设计问题之一，首要的解决方案有两种：一种是根据深度优先查找的办法，另一种是根据贪婪算法的办法。第一种根据深度优先查找的办法是比较常用的算法，深度优先查找算法也是数据结构中的经典算法之一，首要是选用递归的思维，一级一级的寻觅，终究找到适宜的解。而根据贪婪的算法则是根据贪婪算法的思维设置一种规范，然后根据规范进行挑选，然后得到解，可是他纷歧定可以得到最优解。
关于马踏棋盘的根本进程：国际象棋的棋盘为8*8的方格棋盘。现将”马”放在恣意指定的方格中，依照”马”走棋的规则将”马”进行移动。要求每个方格只能进入一次，终究使得”马”走遍棋盘的64个方格。
深度优先查找归于图算法的一种，英文缩写为DFS即Depth First Search.其进程扼要来说是对每一个或许的分支途径深化到不能再深化停止，并且每个节点只能拜访一次. （来自百度）
贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当时看来是最好的挑选。也便是说，不从全体最优上加以考虑，他所做出的仅是在某种意义上的部分最优解。贪心算法不是对一切问题都能得到全体最优解，但对规模适当广泛的许多问题他能发生全体最优解或者是全体最优解的近似解。（来自百度）
其间根据深度优先查找的算法便是根据当时点找到下一个或许的点，然后对这个点进行深度优先查找，然后顺次递归，当呈现条件不满足时，退回来，选用其他的路劲进行查找，终究必定可以得到对应的成果。完成的根本进程如下：
/*deepsearch to solve the horse chessproblem*/
#include
#include
#include
#define ROWS 8
#define COLS 8
int chess[ROWS][COLS];
/*eight directions of x moved*/
const int x_move[] = {-2,-1,1,2,2,1,-1,-2};
/*eight directions of y moved*/
const int y_move[] = {1,2,2,1,-1,-2,-2,-1};
void print_matrix()
{
int i = 0,j = 0;
for (i = 0; i < ROWS; ++ i)
{
for (j = 0; j < COLS; ++ j)
{
printf(“%d “,chess[i][j]);
}
printf(“”);
}
}
/*find the next point*/
intnextxy(int *x,int *y,int count)
{
if(count > 7 && count < 0)
return -1;
switch(count)
{
case 0:
/*check the conditions*/
if(*x + x_move[0] < ROWS &&
*x + x_move[0]>= 0 &&
*y + y_move[0]< COLS &&
*y + y_move[0]>= 0 &&
chess[*x + x_move[0]][*y + y_move[0]] == 0)
{
*x += x_move[0];
*y += y_move[0];
break;
}
else/*failed*/
return 0;
case 1:
if(*x + x_move[1] < ROWS &&
*x + x_move[1]>= 0 &&
*y + y_move[1]< COLS &&
*y + y_move[1]>= 0 &&
chess[*x + x_move[1]][*y + y_move[1]] == 0)
{
*x += x_move[1];
*y += y_move[1];
break;
}
else
return 0;
case 2:
if(*x + x_move[2] < ROWS &&
*x + x_move[2]>= 0 &&
*y + y_move[2]< COLS &&
*y + y_move[2]>= 0 &&
chess[*x + x_move[2]][*y + y_move[2]] == 0)
{
*x += x_move[2];
*y += y_move[2];
break;
}
else
return 0;
case 3:
if(*x + x_move[3] < ROWS &&
*x + x_move[3]>= 0 &&
*y + y_move[3]< COLS &&
*y + y_move[3]>= 0 &&
chess[*x + x_move[3]][*y + y_move[3]] == 0)
{
*x += x_move[3];
*y += y_move[3];
break;
}
else
return 0;
case 4:
if(*x + x_move[4] < ROWS &&
*x + x_move[4]>= 0 &&
*y + y_move[4]< COLS &&
*y + y_move[4]>= 0 &&
chess[*x + x_move[4]][*y + y_move[4]] == 0)
{
*x += x_move[4];
*y += y_move[4];
break;
}
else
return 0;
case 5:
if(*x + x_move[5] < ROWS &&
*x + x_move[5]>= 0 &&
*y + y_move[5]< COLS &&
*y + y_move[5]>= 0 &&
chess[*x + x_move[5]][*y + y_move[5]] == 0)
{
*x += x_move[5];
*y += y_move[5];
break;
}
else
return 0;
case 6:
if(*x + x_move[6] < ROWS &&
*x + x_move[6]>= 0 &&
*y + y_move[6]< COLS &&
*y + y_move[6]>= 0 &&
chess[*x + x_move[6]][*y + y_move[6]] == 0)
{
*x += x_move[6];
*y += y_move[6];
break;
}
else
return 0;
case 7:
if(*x + x_move[7] < ROWS &&
*x + x_move[7]>= 0 &&
*y + y_move[7]< COLS &&
*y + y_move[7]>= 0 &&
chess[*x + x_move[7]][*y + y_move[7]] == 0)
{
*x += x_move[7];
*y += y_move[7];
break;
}
else
return 0;
default:
return 0;
}
return 1;
}
int deepsearch(int x,int y, int j)
{
/*save the value x,y*/
int x1 = x, y1 = y;
int tag = 0, i = 0;
/*save j on chess[x][y]*/
chess[x][y] = j;
/*recursion exit condition*/
if(j == COLS*ROWS)
{
return 1;
}
/*find the next point in eight directions*/
tag = nextxy(&x1,&y1,i);
/*find the nextx,nexty */
while (tag == 0 && i < 7)
{
i ++;
tag =nextxy(&x1,&y1, i);
}
/*the nextxy be found*/
while(tag)
{
if(deepsearch(x1,y1,j+1))
return 1;
/*if failed, a new finding process */
x1 = x; y1 = y;
i ++;
tag = nextxy(&x1,&y1,i);
while (tag == 0 && i < 7)
{
i ++;
tag = nextxy(&x1,&y1,i);
}
}
/*no direction can findnextpoint*/
if(tag == 0)
chess[x][y] = 0;
return 0;
}
void main()
{
clock_t start = clock();
deepsearch(2,0,1);
print_matrix();
int seconds = (clock()-start)/CLOCKS_PER_SEC;
printf(“%d”,seconds);
return;
}
