馬踏棋盤是經典的程序設計問題之一，主要的解決方案有兩種：一種是基于深度優先搜索的方法，另一種是基于貪婪算法的方法。第一種基于深度優先搜索的方法是比較常用的算法，深度優先搜索算法也是數據結構中的經典算法之一，主要是采用遞歸的思想，一級一級的尋找，最后找到合適的解。而基于貪婪的算法則是依據貪婪算法的思想設置一種標準，然后依據標準進行選擇，從而得到解，但是他不一定能夠得到最優解。
關于馬踏棋盤的基本過程：國際象棋的棋盤為8*8的方格棋盤�，F將"馬"放在任意指定的方格中，按照"馬"走棋的規則將"馬"進行移動。要求每個方格只能進入一次，最終使得"馬"走遍棋盤的64個方格。
深度優先搜索屬于圖算法的一種，英文縮寫為DFS即Depth First Search.其過程簡要來說是對每一個可能的分支路徑深入到不能再深入為止，而且每個節點只能訪問一次. （來自百度）
貪心算法（又稱貪婪算法）是指，在對問題求解時，總是做出在當前看來是最好的選擇。也就是說，不從整體最優上加以考慮，他所做出的僅是在某種意義上的局部最優解。貪心算法不是對所有問題都能得到整體最優解，但對范圍相當廣泛的許多問題他能產生整體最優解或者是整體最優解的近似解。（來自百度）
其中基于深度優先搜索的算法就是依據當前點找到下一個可能的點，然后對這個點進行深度優先搜索，然后依次遞歸，當出現條件不滿足時，退回來，采用其他的路勁進行搜索，最后肯定能夠得到對應的結果。實現的基本過程如下：
/*deepsearch to solve the horse chess problem*/
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#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\t",chess[i][j]);
}
printf("\n\n\n");
}
}
/*find the next point*/
int nextxy(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 find next point*/
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("\n%d\n",seconds);
return;
}
采用貪婪算法的實現，首先應該設置一定的判斷準則，然后根據設定的準則進行選擇，在馬踏棋盤中設定的準備是選擇出路最少（至少為1）的一個方向為準則，能夠實現馬踏棋盤問題的解決。當然該問題為什么要選擇出路最少，我暫時還不是很清楚�；镜膶崿F如下：
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define ROWS 8
#define COLS 8
/*axis i move matrix*/
const int iktmove[8] = {-2,-1,1,2,2,1,-1,-2};
/*axis j move matrix*/
const int jktmove[8] = {1,2,2,1,-1,-2,-2,-1};
int board[ROWS][COLS];
/*inital the matrix*/
void matrix_init(int matrix[][COLS],int rows,int cols)
{
int i, j;
for(i = 0; i < rows ; ++ i)
for (j = 0; j < cols ; ++ j)
{
matrix[i][j] = 0;
}
}
/*print the matrix*/
void print_matrix(int matrix[][COLS],int rows,int cols)
{
int i,j;
for(i = 0; i < rows; ++ i)
{
for(j = 0; j < cols; ++ j)
printf("%d\t",matrix[i][j]);
printf("\n\n\n");
}
}
/*find the index of min non-zeros positive*/
int minindex_in_matrix(int a[],int cols)
{
int i = 0,index = 0;
int min = a[0];
for(i = 0 ; i< cols; ++ i)
{
if(a[i] >0)
{
min = a[i];
index = i;
break;
}
}
for(i = index + 1; i < cols ; ++ i)
{
if(a[i] > 0 && min > a[i])
{
min = a[i];
index = i;
}
}
if(a[index] > 0)
return index;
return -1;
}
int maxindex_in_matrix(int a[],int cols)
{
int i = 0,index;
int max ;
for(i = 0 ; i< cols; ++ i)
{
if(a[i] >0)
{
max = a[i];
index = i;
break;
}
}
for(i = index + 1; i < cols ; ++ i)
{
if(a[i] > 0 && max < a[i])
{
max = a[i];
index = i;
}
}
if(a[index] > 0)
return index;
return -1;
}
/**/
void warnsdorff_role(int matrix[][COLS],int rows,int cols,int start_i,int start_j)
{
int i,npos,m,min,j,nnpos;
int nexti[8] = {0,0,0,0,0,0,0,0};
int nextj[8] = {0,0,0,0,0,0,0,0};
int exit[8] = {0,0,0,0,0,0,0,0};
/*steps a*/
matrix_init(matrix,rows,cols);
/*steps b*/
matrix[start_i][start_j] = 1;
/*steps c*/
for(m = 1; m < 64; ++ m)
{
/*steps d*/
npos = 0;
for(i = 0; i < 8; ++ i)
{
/*ignore the point which doesn't satisfy the conditions*/
if( start_i + iktmove[i] < 0 ||
start_i + iktmove[i] >= rows ||
start_j + jktmove[i] < 0 ||
start_j + jktmove[i] >= cols ||
matrix[start_i + iktmove[i]][start_j+jktmove[i]] > 0)
{
continue;
}
/*save the point which satisfy the conditions*/
nexti[npos] = start_i + iktmove[i];
nextj[npos] = start_j + jktmove[i];
/*statistics how many point satisfy conditions*/
npos ++;
}
/*steps e*/
if(npos == 0)
{
printf("Can not finish the game!!\n,The steps of game can be %d\n",m);
goto print;
}
/*steps e*/
if(npos == 1)
{
min = 0;
goto set_nextpoint;
}
/*steps f*/
if(npos > 1)
{
/*calculate the possible way of the next next step */
for(i = 0; i < npos ; ++ i)
{
nnpos = 0;
for(j = 0; j < 8; ++ j)
{
/*statistics the point which satisfy conditions*/
if( nexti[i] + iktmove[j] >= 0 &&
nexti[i] + iktmove[j] < rows &&
nextj[i] + jktmove[j] >= 0 &&
nextj[i] + jktmove[j] < cols &&
matrix[nexti[i] + iktmove[j]][nextj[i] + jktmove[j]] == 0)
{
nnpos ++;
}
}
/*save the numbers of points for next step*/
exit[i] = nnpos;
}
/*find the proper point*/
if((min = minindex_in_matrix(exit,npos)) >= 0)
{
goto set_nextpoint;
}
else /*failed*/
{
printf("Can not finish the game!!\n,The steps of game can be %d\n",m);
goto print;
}
}
set_nextpoint:
/*step g*/
/*set the next start point of game*/
start_i = nexti[min];
start_j = nextj[min];
matrix[start_i][start_j] = m+1;
}
print:
/*step h*/
print_matrix(matrix,rows,cols);
}
void main()
{
warnsdorff_role(board,ROWS,COLS,5,1);
}
實現結果：當采用深度優先搜索算法的過程中發現當棋盤為8X8時，計算速度非常的慢，而當棋盤為5X5以后，計算速度非常的快速。說明算法存在一定的缺陷。而采用貪婪算法實現的速度非常的快，棋盤的大小對算法性能影響較小。
將矩陣改為5X5得到如下的結果：從結果中可以看見兩種算法得到的結果存在一定的差異，但是都能解決馬踏棋盤問題。
1、深度優先搜索算法：
2、貪婪算法：
