由于今天的馬踏棋盤算法并不是使用OC編寫丙躏，所以择示，今天的標(biāo)題也就不是"使用OC....."了，下面直接開始我們的正題晒旅，還是老規(guī)矩栅盲，先上一張圖：
馬踏棋盤示意圖.png
我們的需求是，將"馬"放在任意制定的方格中废恋，按照"馬"走棋的規(guī)則將"馬"進(jìn)行移動谈秫。要求每個方格只能進(jìn)入一次，最終使得"馬"走遍棋盤的64個方格鱼鼓。并且將馬走的步數(shù)標(biāo)記出來拟烫，也就是第一步就標(biāo)記為1，第二步就標(biāo)記為2迄本、依次類推硕淑，直到馬走完了64個位置之后那么就算完成了，下面我們直接來看代碼，因為我在代碼里就已經(jīng)將思路標(biāo)記上了喜颁，每一句代碼幾乎都有詳細(xì)的注釋：
#define MaxRow 8//最大行
#define MaxCol 8//最大列
int chess[MaxRow][MaxCol];//棋盤二維數(shù)組
#pragma mark - 馬踏棋盤算法（騎士周游問題）
#pragma mark -
/**
對八種情況分析尋找下一步可以走的位置
@param x 當(dāng)前馬所在棋盤位置的x坐標(biāo)
@param y 當(dāng)前馬所在棋盤位置的y坐標(biāo)
@param count 不考慮邊緣的情況，馬在任意一位置的下一個位置都可能有八種情況曹阔，count就是對這八種情況進(jìn)行判斷
只要找到其中一種就返回1
@return 找到返回1半开，否則返回0
*/
int nextStep(int *x ,int *y,int count) {
switch(count)
{
case 1:
if(*x + 2 <= MaxCol - 1 && *y - 1 >= 0 && chess[*x + 2][*y - 1] == 0)
{
*x += 2;
*y -= 1;
return 1;
}
break;
case 2:
if(*x + 2 <= MaxCol - 1 && *y + 1 <= MaxRow - 1 && chess[*x + 2][*y + 1] == 0)
{
*x += 2;
*y += 1;
return 1;
}
break;
case 3:
if(*x + 1 <= MaxCol - 1 && *y - 2 >= 0 && chess[*x + 1][*y - 2] == 0)
{
*x += 1;
*y -= 2;
return 1;
}
break;
case 4:
if(*x + 1 <= MaxCol - 1 && *y + 2 <= MaxRow - 1 && chess[*x + 1][*y + 2] == 0)
{
*x += 1;
*y += 2;
return 1;
}
break;
case 5:
if(*x - 2 >= 0 && *y - 1 >= 0 && chess[*x - 2][*y - 1] == 0)
{
*x -= 2;
*y -= 1;
return 1;
}
break;
case 6:
if(*x - 2 >= 0 && *y + 1 <= MaxRow - 1 && chess[*x - 2][*y + 1] == 0)
{
*x -= 2;
*y += 1;
return 1;
}
break;
case 7:
if(*x - 1 >= 0 && *y - 2 >= 0 && chess[*x - 1][*y - 2] == 0)
{
*x -= 1;
*y -= 2;
return 1;
}
break;
case 8:
if(*x - 1 >= 0 && *y + 2 <= MaxRow - 1 && chess[*x - 1][*y + 2] == 0)
{
*x -= 1;
*y += 2;
return 1;
}
break;
default:
break;
}
return 0;
}
/**
深度優(yōu)先搜索
@param x 開始搜索的x
@param y 開始搜索的y
@param step 第多少步
@return 返回1表示下一步可行 0表示不可行
*/
int TraversalChessBoard(int x ,int y ,int step) {
//臨時變量記錄當(dāng)前位置x和y
int x1 = x,y1 = y;
//flag作為標(biāo)記是否找到下一個位置 count為遍歷的8中情況
int flag =0,count = 1;
//標(biāo)記當(dāng)前的位置已經(jīng)被??踏過 標(biāo)記為step，也就是剛剛走的是第多少步
chess[x][y] = step;
//當(dāng)步數(shù)剛好等于棋盤的格子個數(shù) 就證明已經(jīng)走完了
if (step == MaxRow * MaxCol) {
//成功 打印結(jié)果
Print();
return 1;
}
//沒有走完就 尋找下一個位置并且將八種情況都走一遍
flag = nextStep(&x1, &y1, count);
//只要flag為0證明上一次沒有找到下一步赃份，這里我們把剩下的其他位置都走一遍
while (flag == 0 && count < MaxRow) {
//讓走法+1
count++;
//讓flag重新標(biāo)記
flag = nextStep(&x1, &y1, count);
}
//當(dāng)找到下一個位置了之后寂拆，就從找到的位置開始繼續(xù)遞歸尋找
while (flag) {
// 遞歸調(diào)用走向下一個位置，因為在NextStep函數(shù)中直接修改了當(dāng)前位置的坐標(biāo)抓韩，所以此時的x1和y1就表示下一個可走位置的坐標(biāo)
if (TraversalChessBoard(x1, y1, step+1)) {
return 1;
}
//如果不是返回1纠永，那證明剛剛的路徑?jīng)]法走完 我們就回溯到上一個位置去
x1 = x;
y1 = y;
// 前count種可走位置的情況都判斷過了，從count+1種情況繼續(xù)判斷
count++;
//沒有走完就 尋找下一個位置并且將八種情況都走一遍
flag = nextStep(&x1, &y1, count);
//只要flag為0證明上一次沒有找到下一步谒拴，這里我們把剩下的其他位置都走一遍
while (flag == 0 && count < MaxRow) {
//讓走法+1
count++;
//讓flag重新標(biāo)記
flag = nextStep(&x1, &y1, count);
}
}
//如果八種情況都是沒法找到合適的位置 那就從當(dāng)前位置回退到上一個位置 返回0就行 而且將二維數(shù)組中的位置置為0 證明它沒有走過
if (0 == flag) {
chess[x][y] = 0;
}
return 0;
}
/**
* 打印棋盤尝江，棋盤中每個格子的數(shù)值就是遍歷的次序
*/
void Print()
{
int i, j;
for(i = 0; i < MaxRow; i++)
{
for(j = 0; j < MaxCol; j++)
{
printf("%2d\t", chess[i][j]);
}
printf("\n");
}
printf("\n");
}
這里我需要對第一個方法也就是nextStep這個方法進(jìn)行一下說明，這個方法是用于尋找馬下一步要走的位置英上，假如我們當(dāng)前要走到1這個位置炭序，那么x需要-1 ，y則需要-2苍日，然后再判斷一下是否跑出了棋盤的位置惭聂，接著還需要判斷1這個位置是否馬已經(jīng)走過了，如果上面我說的幾種情況都滿足了相恃，那么就說明這個位置是可以走的辜纲，就返回1，這就是這個方法大概的意思拦耐，不考慮邊緣情況下耕腾，馬總共有8種方式可以走，因此這里通過一個switch對8中情況進(jìn)行了考慮杀糯，接著就是TraversalChessBoard這個方法了幽邓，這個方法里面我已經(jīng)寫上了詳細(xì)的注釋了，應(yīng)該都能看懂了火脉，當(dāng)然牵舵，注重要的是得理解，如果不理解倦挂，也是很難看明白的
