【說明】本文來自由周世平老師主編的《c語言程式設計》教材。我作為參編人員執筆了第7、8章。“第8章 問題求解與算法”中“8.6.1 回溯法”以8皇後問題的求解為例，介紹了回溯法的解題過程。這個解決方案中用到了“棧”，引用至此，作為棧應用的例子。需要說明的是，教材面向程式設計初學者，并全文中并未提出過任何關于“棧”的描述。這樣做，隐藏了術語，減少初學者的認知難度。對于資料結構的學習者而言，由于知識面的擴大，卻用不着回避這樣的術語了。于是，在閱讀本文時，作為體會棧的應用，需要自行從中提取出應用棧式存儲及處理的部分來。
【全文】
回溯法是一種通用的搜尋算法，幾乎可以用于求解任何可計算的問題。算法的執行過程就像是在迷宮中搜尋一條通往出口的路線，總是沿着某一方向向前試探，若能走通，則繼續向前進；如果走不通，則要做上标記，換一個方向再繼續試探，直到得出問題的解，或者所有的可能都試探過為止。
下面，用經典的8皇後問題為例來講解如何使用回溯的思想解決問題。
8皇後問題是：在8×8的棋盤上擺放8個皇後，使其不能互相攻擊，即任意的兩個皇後不能處在同一行，同一列，或同一斜線上。可以把八皇後問題拓展為n皇後問題，即在n×n的棋盤上擺放n個皇後，使其任意兩個皇後都不能處于同一行、同一列或同一斜線上。
首先需要對棋盤進行描述。直覺地，棋盤可以用二維數組表示，有皇後的棋格對應數組元素值為1，無皇後的棋格對應數組元素值為0。但這種存儲結構并不是最簡單有效的選擇。
圖8.21中左邊部分給棋盤的行、列編了号，提供的擺放方法，就是問題的一個解。右邊的部分，将各行上皇後所在的列數記錄下來，用這8個數字（4, 6, 8, 2, 7, 1, 3, 5），也構成了對問題解的一種描述。
圖8.21 8皇後問題的一個解
由此可以看出，可以定義一個一維數組int x[n];，用x[i]的值表示第i行上皇後所在的列數，n皇後問題的解可以用（x[1], x[2], ….. x[n]）的形式描述。
解決了資料表示的問題，設計資料處理的方法。這裡要用回溯的政策，設計計算機對n皇後問題的求解方法。以4皇後為例，如圖8.22所示，在圖8.22(a)中，第1行第1列上放置一個皇後，圖8.22(b)中确定第2行的可能放法，在嘗試第1列、第2列由于互相攻擊而放棄之後，确定在第3列放置可以繼續，在圖8.22(c)中繼續對第3行進行考察，發現将所有4列都嘗試過了，也沒有辦法将皇後安排一個合适的位置，對第4行做任何的嘗試都沒有意義，這時産生回溯，結果是在圖8.22(d)中将第2行的皇後安排到第4列，然後第3行的暫時可以放在第2列，在圖8.22(e)中試着确定第4行的皇後，卻發現無解再次回溯，隻能夠如圖8.22(f)所示将第1行的皇後放到第2列，再經圖8.22(g)、(f)之後找到4皇後問題的一個解，那就是圖8.22(g)的（2, 4, 1, 3）。
圖8.22 用回溯找出4皇後問題一個解的過程
在圖8.23中，給出了求出4皇後問題所有解的完整過程的描述。圖中（1 * * *)對應圖8.22(a)中第1行皇後安排在第1列，其他行待定的狀态，接下來的（1 3 * *）對應了圖8.22(b)中第2行皇後安排在第3列的狀态。可以判斷出在這個狀态下，繼續嘗試并不能夠完成求解，于是發生回溯（其下方的b代表回溯），于是下一個嘗試的狀态将是（1 4 * *），……。将這樣的過程繼續下去，能夠找出4皇後問題的所有解（2 4 1 3）和（3 1 4 2），如圖8.23中兩個加網格背景的結點。
圖8.23 求出4皇後問題所有解的完整過程
搞清楚用回溯法求解的過程後，将關注如何基于（x[1], x[2], ….. x[n]）形式的解結構，寫出讓計算機完成求解過程的代碼。4皇後問題尚且可以在紙上畫出解，8皇後問題的可能解有8!=40320種，最終解有92種，必須要依靠計算機求解了。
什麼樣的解才是可行的？需要描述出任何兩個皇後可以“互相攻擊”這樣的條件：
（1）有兩個皇後處在同一行：解的結構（x[1], x[2], ….. x[n]）已經保證同一行不會出現兩個皇後。
（2）有兩個皇後處在同一列：表示為x[i]=x[k]，假如在圖8.23中出現表示為（1 1 * *）、（4 2 3 2）之類的結點，則說明有兩個皇後在同一列了。
（3）有兩個皇後處在同一斜線：若兩個皇後的擺放位置分别是第i行第x[i]列、第k行第x[k]列，若他們在棋盤上斜率為-1的斜線上，滿足條件i-x[i]=k-x[k]，例如（1 4 3 *）、（4 1 2 *）；若他們在棋盤上斜率為1的斜線上，滿足條件i+x[i]=k+x[k]。将這兩個式子分别變換成i-k=x[i]-x[k]和i-k=x[k]-x[i]，例如（3 4 1 *）。綜合兩種情況，兩個皇後位于同一斜線上表示為|i-k|=|x[i]-x[k]|。
在下面的程式實作中，place(x, k)函數用于判斷在第k行第x[k]列放置皇後，是否會與前面擺放好的皇後産生互相攻擊。隻要有某行（第i行）的皇後與這個第k行的皇後處在同一列（x[i]=x[k]）或者處在同一斜線（|i-k|=|x[i]-x[k]|），則立即傳回假(0)，表示不可能構成解。
再接下來，就是在實作問題求解的nqueens(x, n)函數中，從第1行開始，逐行逐列地考察皇後的擺放，當遇到某一行所有可能情況試過不必再深入到下一行考察時，及時回溯到上一行，接着考察。
程式實作中，将儲存解的數組定義成了動态數組。多配置設定一個單元，因為數組的首元素x[0]一直空閑未用，有用的單元是x[1]到x[n]。
【例8.12】 求解8皇後問題的程式
【思考題】請從解題政策和程式中，找出何處使用了棧，是如何将棧應用于回溯過程的？