马踏棋盘的实现

/*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;
}

采用贪婪算法的实现，首先应该设置一定的判断准则，然后根据设定的准则进行选择，在马踏棋盘中设定的准备是选择出路最少（至少为1）的一个方向为准则，能够实现马踏棋盘问题的解决。当然该问题为什么要选择出路最少，我暂时还不是很清楚。基本的实现如下：

#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);
}

实现结果：