馬踏棋盤是經(jīng)典的程序設(shè)計(jì)問題之一，主要的解決方案有兩種：一種是基于深度優(yōu)先搜索的方法，另一種是基于貪婪算法的方法。第一種基于深度優(yōu)先搜索的方法是比較常用的算法，深度優(yōu)先搜索算法也是數(shù)據(jù)結(jié)構(gòu)中的經(jīng)典算法之一，主要是采用遞歸的思想，一級一級的尋找，最后找到合適的解。而基于貪婪的算法則是依據(jù)貪婪算法的思想設(shè)置一種標(biāo)準(zhǔn)，然后依據(jù)標(biāo)準(zhǔn)進(jìn)行選擇，從而得到解，但是他不一定能夠得到最優(yōu)解。
關(guān)于馬踏棋盤的基本過程：國際象棋的棋盤為8*8的方格棋盤�，F(xiàn)將"馬"放在任意指定的方格中，按照"馬"走棋的規(guī)則將"馬"進(jìn)行移動。要求每個方格只能進(jìn)入一次，最終使得"馬"走遍棋盤的64個方格。
深度優(yōu)先搜索屬于圖算法的一種，英文縮寫為DFS即Depth First Search.其過程簡要來說是對每一個可能的分支路徑深入到不能再深入為止，而且每個節(jié)點(diǎn)只能訪問一次. （來自百度）
貪心算法（又稱貪婪算法）是指，在對問題求解時，總是做出在當(dāng)前看來是最好的選擇。也就是說，不從整體最優(yōu)上加以考慮，他所做出的僅是在某種意義上的局部最優(yōu)解。貪心算法不是對所有問題都能得到整體最優(yōu)解，但對范圍相當(dāng)廣泛的許多問題他能產(chǎn)生整體最優(yōu)解或者是整體最優(yōu)解的近似解。（來自百度）
其中基于深度優(yōu)先搜索的算法就是依據(jù)當(dāng)前點(diǎn)找到下一個可能的點(diǎn)，然后對這個點(diǎn)進(jìn)行深度優(yōu)先搜索，然后依次遞歸，當(dāng)出現(xiàn)條件不滿足時，退回來，采用其他的路勁進(jìn)行搜索，最后肯定能夠得到對應(yīng)的結(jié)果。實(shí)現(xiàn)的基本過程如下：
/*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;
}
采用貪婪算法的實(shí)現(xiàn)，首先應(yīng)該設(shè)置一定的判斷準(zhǔn)則，然后根據(jù)設(shè)定的準(zhǔn)則進(jìn)行選擇，在馬踏棋盤中設(shè)定的準(zhǔn)備是選擇出路最少（至少為1）的一個方向?yàn)闇?zhǔn)則，能夠?qū)崿F(xiàn)馬踏棋盤問題的解決。當(dāng)然該問題為什么要選擇出路最少，我暫時還不是很清楚�；镜膶�(shí)現(xiàn)如下：
#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);
}
實(shí)現(xiàn)結(jié)果：當(dāng)采用深度優(yōu)先搜索算法的過程中發(fā)現(xiàn)當(dāng)棋盤為8X8時，計(jì)算速度非常的慢，而當(dāng)棋盤為5X5以后，計(jì)算速度非常的快速。說明算法存在一定的缺陷。而采用貪婪算法實(shí)現(xiàn)的速度非常的快，棋盤的大小對算法性能影響較小。
將矩陣改為5X5得到如下的結(jié)果：從結(jié)果中可以看見兩種算法得到的結(jié)果存在一定的差異，但是都能解決馬踏棋盤問題。
1、深度優(yōu)先搜索算法：
2、貪婪算法：
