馬踏棋盤的實現(xiàn)

采用貪婪算法的實現(xiàn)，首先應該設置一定的判斷準則，然后根據(jù)設定的準則進行選擇，在馬踏棋盤中設定的準備是選擇出路最少（至少為1）的一個方向為準則，能夠實現(xiàn)馬踏棋盤問題的解決。當然該問題為什么要選擇出路最少，我暫時還不是很清楚。基本的實現(xiàn)如下：

#include
#include
#include

#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*/
voidmatrix_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 ",matrix[i][j]);
printf("");
}
}
/*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};
intnextj[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 doesnt 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 notfinishthegame!!,The steps of game can be %d",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 fornextstep*/
exit[i] = nnpos;
}
/*find the proper point*/
if((min = minindex_in_matrix(exit,npos)) >= 0)
{
goto set_nextpoint;
}
else /*failed*/
{
printf("Can notfinishthe game!!,The steps of game can be %d",m);
goto print;
}
}
set_nextpoint:
/*step g*/
/*set the next start point ofgame*/
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);
}

實現(xiàn)結果：當采用深度優(yōu)先搜索算法的過程中發(fā)現(xiàn)當棋盤為8X8時，計算速度非常的慢，而當棋盤為5X5以后，計算速度非常的快速。說明算法存在一定的缺陷。而采用貪婪算法實現(xiàn)的速度非常的快，棋盤的大小對算法性能影響較小。

將矩陣改為5X5得到如下的結果：從結果中可以看見兩種算法得到的結果存在一定的差異，但是都能解決馬踏棋盤問題。

1、深度優(yōu)先搜索算法：

2、貪婪算法：