遞歸算法學習系列之八皇后問題
1.引子
中國有一句古話，叫做“不撞南墻不回頭"，生動的說明了一個人的固執，有點貶義，但是在軟件編程中，這種思路確是一種解決問題最簡單的算法，它通過一種類似于蠻干的思路，一步一步地往前走，每走一步都更靠近目標結果一些，直到遇到障礙物，我們才考慮往回走。然后再繼續嘗試向前。通過這樣的波浪式前進方法，最終達到目的地。當然整個過程需要很多往返，這樣的前進方式，效率比較低下。
2.適用范圍
適用于那些不存在簡明的數學模型以闡明問題的本質，或者存在數學模型，但是難于實現的問題。
3.應用場景
在8*8國際象棋棋盤上，要求在每一行放置一個皇后，且能做到在豎方向，斜方向都沒有沖突。國際象棋的棋盤如下圖所示：
4.分析
基本思路如上面分析一致，我們采用逐步試探的方式，先從一個方向往前走，能進則進，不能進則退，嘗試另外的路徑。首先我們來分析一下國際象棋的規則，這些規則能夠限制我們的前進，也就是我們前進途中的障礙物。一個皇后q(x,y)能被滿足以下條件的皇后q(row,col)吃掉
1）x=row(在縱向不能有兩個皇后)
2) y=col（橫向）
3）col + row = y+x;（斜向正方向）
4) col - row = y-x;（斜向反方向）
遇到上述問題之一的時候，說明我們已經遇到了障礙，不能繼續向前了。我們需要退回來，嘗試其他路徑。
我們將棋盤看作是一個8*8的數組，這樣可以使用一種蠻干的思路去解決這個問題，這樣我們就是在8*8=64個格子中取出8個的組合，C(64,80) = 4426165368,顯然這個數非常大，在蠻干的基礎上我們可以增加回溯，從第0列開始，我們逐列進行，從第0行到第7行找到一個不受任何已經現有皇后攻擊的位置，而第五列，我們會發現找不到皇后的安全位置了，前面四列的擺放如下:
第五列的時候，擺放任何行都會上圖所示已經存在的皇后的攻擊，這時候我們認為我們撞了南墻了，是回頭的時候了，我們后退一列，將原來擺放在第四列的皇后（3，4）拿走，從（3，4）這個位置開始，我們再第四列中尋找下一個安全位置為（7，4），再繼續到第五列，發現第五列仍然沒有安全位置，回溯到第四列，此時第四列也是一個死胡同了，我們再回溯到第三列，這樣前進幾步，回退一步，最終直到在第8列上找到一個安全位置（成功）或者第一列已經是死胡同，但是第8列仍然沒有找到安全位置為止
總結一下，用回溯的方法解決8皇后問題的步驟為：
1）從第一列開始，為皇后找到安全位置，然后跳到下一列
2）如果在第n列出現死胡同，如果該列為第一列，棋局失敗，否則后退到上一列，在進行回溯
3）如果在第8列上找到了安全位置，則棋局成功。
8個皇后都找到了安全位置代表棋局的成功，用一個長度為8的整數數組queenList代表成功擺放的8個皇后，數組索引代表棋盤的col向量，而數組的值為棋盤的row向
量，所以(row,col)的皇后可以表示為(queenList[col],col),如上圖中的幾個皇后可表示為：
queenList[0] = 0; queenList[1] = 3; queenList[2] = 1; queenList[3] = 4; queenList = 2;
我們看一下如何設計程序:
首先判斷(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;
}設定一個函數，用于查找col列后的皇后擺放方法：
/// <summary> /// 在第col列尋找安全的row值 /// </summary> /// <param name="queenList"></param> /// <param name="col"></param> /// <returns></returns> public bool PlaceQueue(int[] queenList, int col) { int row = 0; bool foundSafePos = false; if (col == 8) //結束標志 { //當處理完第8列的完成 foundSafePos = true; } else { while (row < 8 && !foundSafePos) { if (IsSafe(col, row, queenList)) { //找到安全位置 queenList[col] = row; //找下一列的安全位置 foundSafePos = PlaceQueue(queenList, col + 1); if (!foundSafePos) { row++; } } else { row++; } } } return foundSafePos; }調用方法：
static void Main(string[] args) { EightQueen eq = new EightQueen(); int[] queenList = new int[8]; for (int j = 0; j < 8; j++) { Console.WriteLine("-----------------"+j+"---------------------"); queenList[0] = j; bool res = eq.PlaceQueue(queenList, 1); if (res) { Console.Write(" "); for (int i = 0; i < 8; i++) { Console.Write(" " + i.ToString() + " "); } Console.WriteLine(""); for (int i = 0; i < 8; i++) { Console.Write(" "+i.ToString()+" "); for (int a = 0; a < 8; a++) { if (i == queenList[a]) { Console.Write(" q "); } else { Console.Write(" * "); } } Console.WriteLine(""); } Console.WriteLine("---------------------------------------"); } else { Console.WriteLine("不能完成棋局，棋局失敗！"); } } Console.Read(); }遞歸算法PlaceQueue,完成這樣的功能：它尋找第col列后的皇后的安全擺放位置，如果該函數返回了false,表示當前進入了死胡同，需要進行回溯，直到為0-7列都找
到了安全位置或者找遍這些列都找不到安全位置的時候終止。
用遞歸算法解決8皇后問題的示例程序：
/Files/jillzhang/EightQueens.rar
歡迎大家下載；
-----------------------------------------------------------------------------------------------------------------
遞歸算法到這篇為止，已經學習到了分而治之，動態編程，回溯等重要思想，也用這些問題解決了一些具體問題，比如排序，背包，8皇后問題等，通過對理論的學習
和對實際問題的解決，充分理解遞歸算法的使用方法。在編寫學習系列的過程中，絕大多數都參考數據結構C++語言描述-應用標準模板庫 ，特此感謝原書作者：
William Ford,William Topp,和譯者陳軍。
下一系列主要想通過6-8篇的篇幅來學習圖論的基礎知識。多謝大家支持
出處：http://jillzhang.cnblogs.com/
本文版權歸作者和博客園共有，歡迎轉載，但未經作者同意必須保留此段聲明，且在文章頁面明顯位置給出原文連接，否則保留追究法律責任的權利。
浙公網安備 33010602011771號