1.引子

　　中國(guó)有一句古話，叫做“不撞南墻不回頭"，生動(dòng)的說(shuō)明了一個(gè)人的固執(zhí)，有點(diǎn)貶義，但是在軟件編程中，這種思路確是一種解決問(wèn)題最簡(jiǎn)單的算法，它通過(guò)一種類似于蠻干的思路，一步一步地往前走，每走一步都更靠近目標(biāo)結(jié)果一些，直到遇到障礙物，我們才考慮往回走。然后再繼續(xù)嘗試向前。通過(guò)這樣的波浪式前進(jìn)方法，最終達(dá)到目的地。當(dāng)然整個(gè)過(guò)程需要很多往返，這樣的前進(jìn)方式，效率比較低下。

2.適用范圍

　　適用于那些不存在簡(jiǎn)明的數(shù)學(xué)模型以闡明問(wèn)題的本質(zhì)，或者存在數(shù)學(xué)模型，但是難于實(shí)現(xiàn)的問(wèn)題。

3.應(yīng)用場(chǎng)景

　　在8*8國(guó)際象棋棋盤上，要求在每一行放置一個(gè)皇后，且能做到在豎方向，斜方向都沒(méi)有沖突。國(guó)際象棋的棋盤如下圖所示：

4.分析

　　基本思路如上面分析一致，我們采用逐步試探的方式，先從一個(gè)方向往前走，能進(jìn)則進(jìn)，不能進(jìn)則退，嘗試另外的路徑。首先我們來(lái)分析一下國(guó)際象棋的規(guī)則，這些規(guī)則能夠限制我們的前進(jìn)，也就是我們前進(jìn)途中的障礙物。一個(gè)皇后q(x,y)能被滿足以下條件的皇后q(row,col)吃掉

1）x=row(在縱向不能有兩個(gè)皇后)

2）y=col（橫向）

3）col + row = y+x;（斜向正方向）

4）col - row = y-x;（斜向反方向）

遇到上述問(wèn)題之一的時(shí)候，說(shuō)明我們已經(jīng)遇到了障礙，不能繼續(xù)向前了。我們需要退回來(lái)，嘗試其他路徑。

我們將棋盤看作是一個(gè)8*8的數(shù)組，這樣可以使用一種蠻干的思路去解決這個(gè)問(wèn)題，這樣我們就是在8*8=64個(gè)格子中取出8個(gè)的組合，C(64,80) = 4426165368,顯然這個(gè)數(shù)非常大，在蠻干的基礎(chǔ)上我們可以增加回溯，從第0列開始，我們逐列進(jìn)行，從第0行到第7行找到一個(gè)不受任何已經(jīng)現(xiàn)有皇后攻擊的位置，而第五列，我們會(huì)發(fā)現(xiàn)找不到皇后的安全位置了，前面四列的擺放如下:

第五列的時(shí)候，擺放任何行都會(huì)上圖所示已經(jīng)存在的皇后的攻擊，這時(shí)候我們認(rèn)為我們撞了南墻了，是回頭的時(shí)候了，我們后退一列，將原來(lái)擺放在第四列的皇后（3，4）拿走，從（3，4）這個(gè)位置開始，我們?cè)俚谒牧兄袑ふ蚁乱粋€(gè)安全位置為（7，4），再繼續(xù)到第五列，發(fā)現(xiàn)第五列仍然沒(méi)有安全位置，回溯到第四列，此時(shí)第四列也是一個(gè)死胡同了，我們?cè)倩厮莸降谌?，這樣前進(jìn)幾步，回退一步，最終直到在第8列上找到一個(gè)安全位置（成功）或者第一列已經(jīng)是死胡同，但是第8列仍然沒(méi)有找到安全位置為止

總結(jié)一下，用回溯的方法解決8皇后問(wèn)題的步驟為：

1）從第一列開始，為皇后找到安全位置，然后跳到下一列

2）如果在第n列出現(xiàn)死胡同，如果該列為第一列，棋局失敗，否則后退到上一列，在進(jìn)行回溯

3）如果在第8列上找到了安全位置，則棋局成功。

8個(gè)皇后都找到了安全位置代表棋局的成功，用一個(gè)長(zhǎng)度為8的整數(shù)數(shù)組queenList代表成功擺放的8個(gè)皇后，數(shù)組索引代表棋盤的col向量，而數(shù)組的值為棋盤的row向

量，所以(row,col)的皇后可以表示為(queenList[col],col),如上圖中的幾個(gè)皇后可表示為：

queenList[0] = 0;  queenList[1] = 3;   queenList[2] = 1;  queenList[3] = 4;   queenList = 2;

我們看一下如何設(shè)計(jì)程序:

首先判斷(row,col)是否是安全位置的算法：

bool IsSafe(int col,int row,int[] queenList){ //只檢查前面的列 for (int tempCol = 0; tempCol < col; tempCol++) {  int tempRow = queenList[tempCol];  if (tempRow == row)  {   //同一行   return false;  }  if (tempCol == col)  {   //同一列   return false;  }  if (tempRow - tempCol == row - col || tempRow + tempCol == row + col)  {   return false;  } } return true;}