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

關(guān)于馬踏棋盤的基本過程：國際象棋的棋盤為8*8的方格棋盤?，F(xiàn)將"馬"放在任意指定的方格中，按照"馬"走棋的規(guī)則將"馬"進(jìn)行移動。要求每個(gè)方格只能進(jìn)入一次，最終使得"馬"走遍棋盤的64個(gè)方格。

深度優(yōu)先搜索屬于圖算法的一種，英文縮寫為DFS即Depth First Search.其過程簡要來說是對每一個(gè)可能的分支路徑深入到不能再深入為止，而且每個(gè)節(jié)點(diǎn)只能訪問一次. （來自百度）

貪心算法（又稱貪婪算法）是指，在對問題求解時(shí)，總是做出在當(dāng)前看來是最好的選擇。也就是說，不從整體最優(yōu)上加以考慮，他所做出的僅是在某種意義上的局部最優(yōu)解。貪心算法不是對所有問題都能得到整體最優(yōu)解，但對范圍相當(dāng)廣泛的許多問題他能產(chǎn)生整體最優(yōu)解或者是整體最優(yōu)解的近似解。（來自百度）

其中基于深度優(yōu)先搜索的算法就是依據(jù)當(dāng)前點(diǎn)找到下一個(gè)可能的點(diǎn)，然后對這個(gè)點(diǎn)進(jìn)行深度優(yōu)先搜索，然后依次遞歸，當(dāng)出現(xiàn)條件不滿足時(shí)，退回來，采用其他的路勁進(jìn)行搜索，最后肯定能夠得到對應(yīng)的結(jié)果。實(shí)現(xiàn)的基本過程如下：

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