文章首發公衆号：bigsai 更多精彩幹貨敬請關注！
前言
說起八皇後問題，它是一道回溯算法類的經典問題，也可能是我們大部分人在上資料結構或者算法課上遇到過的最難的一道題……
第一次遇到它的時候應該是大一下或者大二這個期間，這個時間對啥都懵懵懂懂，啥都想學卻發現好像啥都挺難的，八皇後同樣把那個時候的我阻攔在外，我記得很清楚當時大二初我們學業導師給我們開班會時候講到的一句話很清晰："如果沒有認真的學習算法他怎麼可能解出八皇後的代碼呢"。
确實，那個時候的我搞不懂遞歸，回溯也沒聽過，連Java的集合都沒用明白，毫無邏輯可言，八皇後對我來說确實就是無從下手。
但今天，我可以吊打八皇後了，和你們一起白銀萬兩，佳麗三十。
淺談遞歸
對于遞歸算法，我覺得掌握遞歸是入門資料結構與算法的關鍵，因為後面學習很多操作涉及到遞歸，例如連結清單的一些操作、樹的周遊和一些操作、圖的dfs、快排、歸并排序等等。
遞歸的實質還是借助棧實作一些操作，利用遞歸能夠完成的操作使用棧都能夠完成，并且利用棧的話可以很好的控制停止，效率更高(遞歸是一個來回的過程回來的時候需要特判)。
遞歸實作和棧實作操作的差別，遞歸對我們來說更簡潔巧妙，并且用多了會發現很多問題的處理上遞歸的思考方式更偏向人的思考方式，而棧的話就是老老實實用計算機(資料結構特性)的思維去思考問題。這個你可以參考二叉樹的周遊方式遞歸和非遞歸版本，複雜性一目了然。
從遞歸算法的特征上來看，遞歸算法的問題都是父問題可以用過一定關系轉化為子問題。即從後往前推導的過程，一般通過一個參數來表示目前的層級。
而遞歸的主要特點如下：
- 自己調用自己
- 遞歸通常不在意具體操作，隻關心初始條件和上下層的變化關系。
- 遞歸函數需要有臨界停止點，即遞歸不能無限制的執行下去。通常這個點為必須經過的一個數。
- 遞歸可以被棧替代。有些遞歸可以優化。比如遇到重複性的可以借助空間記憶體記錄而減少遞歸的次數。
而通常遞歸算法的一個流程大緻為：
定義遞歸算法及參數
- 停止遞歸算法條件
- (可存在)其他邏輯
- 遞歸調用(參數需要改變)
- (可存在)其他邏輯 如果還是不了解的話就要看我的另一篇文章了：
資料結構與算法—遞歸算法(從階乘、斐波那契到漢諾塔的遞歸圖解)，寫的是真的好！
回溯算法
談完遞歸，你可能明白有這麼一種方法可以使用，但你可能感覺單單的遞歸和八皇後還是很難扯上關系，是的沒錯，是以我來講回溯算法了。
這裡插個小插曲。前天(真的前天)有個舍友我們宿舍一起聊天的時候談到回溯算法，他說
回shuo(朔)
算法，我們差異的糾正了一下是
回su(素)
算法，他竟然讀錯了四年……不知道路過的你們有沒有讀錯的。
咱們言歸正傳，算法界中，有五大常用算法：貪心算法、分治算法、動态規劃算法、回溯算法、分支界限算法。咱們回溯算法就是五大之一，因為回溯算法能夠解決很多實際的問題，盡管很多時候複雜度可能不太小，但大部分情況都能得到一個不錯的結果。
對于回溯法的定義，百度百科是這麼定義的：
回溯算法實際上一個類似枚舉的搜尋嘗試過程，主要是在搜尋嘗試過程中尋找問題的解，當發現已不滿足求解條件時，就“回溯”傳回，嘗試别的路徑。回溯法是一種選優搜尋法，按選優條件向前搜尋，以達到目标。但當探索到某一步時，發現原先選擇并不優或達不到目标，就退回一步重新選擇，這種走不通就退回再走的技術為回溯法，而滿足回溯條件的某個狀态的點稱為“回溯點”。許多複雜的，規模較大的問題都可以使用回溯法，有“通用解題方法”的美稱。
對于回溯法，它的核心就是試探和複原。這個自動化的過程就是利用遞歸去執行，在遞歸函數執行前去修改嘗試，滿足條件後向下遞歸試探，試探完畢後需要将數值複原。在這個試探的過程中找到我們所需要的一個或者所有解。這個我們也俗稱暴力。
啥？沒聽懂？好，那我就再講講，你應該知道深度優先搜尋(dfs)吧？其實回溯算法就是一種特殊的dfs。之是以叫回溯，就是因為這類算法在運用遞歸都有個複原的過程，是以前面的操作就相當于試探一樣。而這類算法一般常常配對一個或多個boolean類型的數組用來标記試探途中用過的點。
舉個例子，我們知道回溯算法用來求所有數字的排列順序。我們分析其中一個順序。比如數列
6 8 9
這個序列的話，我們用來求它的排列順序。
對于代碼塊來說，這可能很容易實作：
import java.util.Arrays;
public class test {
public static void main(String[] args) {
int arr[]={6,8,9};//需要排列組合的數組
int val[]={0,0,0};//臨時儲存的數組
boolean jud[] = new boolean[arr.length];// 判斷是否被用
dfs(arr,val, jud, 0,"");//用一個字元串長度更直覺看結果
}
private static void dfs(int[] arr, int val[],boolean[] jud, int index,String s) {
System.out.println(s+Arrays.toString(val));
if (index == arr.length){ }//停止遞歸條件
else{
for (int i = 0; i < arr.length; i++) {
if (!jud[i]) {//目前不能用的
int team=val[index];
val[index] = arr[i];
jud[i] = true;// 下層不能在用
dfs(arr, val, jud, index + 1,s+" _ ");
jud[i] = false;// 還原
val[index]=team;
}
}
}
}
} 而執行的結果為：
這裡再配張圖了解：
而通常回溯算法的一個流程大緻為：
定義回溯算法及參數
- (符合條件)跳出
- (不符合)不跳出：
- - 周遊需要操作的清單&&該元素可操作&&可以繼續試探
- - - 标記該元素已使用以及其他操作
- - - 遞歸調用(參數改變)
- - - 清除該元素标記以及其他操作 也就是在使用數組進行回溯的時候，使用過的時候需要标記子遞歸不能再使用防止死循環，而當回來的時候需要解封該位置，以便該編号位置被其他兄弟使用之後這個數值在後面能夠再次使用！而如果使用List或者StringBuilder等動态空間用來進行回溯的時候記得同樣的複原，删了要記得增，減了要記得加。搞明白這些，我想回溯算法也應該難不倒你了吧。
八皇後問題
掌握了回溯算法的關鍵，八皇後問題多思考就可以想的出來了。前面的講解都是為了解決八皇後問題做鋪墊。首先，我們認真的看下八皇後問題描述。
八皇後問題（英文：Eight queens），是由國際西洋棋棋手馬克斯·貝瑟爾于1848年提出的問題，是回溯算法的典型案例。
問題表述為：在8×8格的國際象棋上擺放8個皇後，使其不能互相攻擊，即任意兩個皇後都不能處于同一行、同一列或同一斜線上，問有多少種擺法。高斯認為有76種方案。1854年在柏林的象棋雜志上不同的作者發表了40種不同的解，後來有人用圖論的方法解出92種結果。如果經過±90度、±180度旋轉，和對角線對稱變換的擺法看成一類，共有42類。計算機發明後，有多種計算機語言可以程式設計解決此問題。
我們該怎麼思考這種問題呢?也就是從何入手呢？
- 從限制條件入手
八皇後問題有以下限制條件：
- 8 x 8的方格
- 每行一個，共八行(0-7)
- 每列一個，共八列(0-7)
- 每左斜杠一個，共十五左斜杠(0-14)
- 每右斜杠一個，共十五右斜杠(0-14)
當看到這些限制條件，肯定想到這麼多限制條件需要判斷。判斷的話當然就是借助boolean數組啦。還是一維的8個大小，是以我們首先用4個boolean數組用來判斷各自的條件是否被滿足。
表示這個圖的話我們可以使用一個int類型數組表示，0表示沒有，1表示有皇後。
那麼如何去設計這個算法呢？這個并不是每個格子都有數字，是以在進行回溯的時候不應該每個格子每個格子進行向下遞歸(同行互斥)，也就是遞歸到目前層的時候，循環周遊該層的八種情況進行試探(每個都試探)，如果不滿足條件的就不操作而被終止掉，但該行每個滿足條件的需要遞歸的時候需要進入到下一行。
當然你需要提前知道目前位置橫縱坐标怎們知道對應的boolean位置(位置從0号開始計算)。例如位置p(x,y)中對應的位置為：
- hang[] :
x
- lie[] :
y
- zuoxie[] :
x+y
- youxie[] :
x+(7-y)
好啦，該算法的實作代碼為：
import java.util.Arrays;
public class EightQueens {
static int allnum=0;
public static void main(String[] args) {
boolean hang[]=new boolean[8];//行
boolean lie[]=new boolean[8];//列
boolean zuoxie[]=new boolean[15];//左斜杠
boolean youxie[]=new boolean[15];//右斜杠
int map[][]=new int[8][8];//地圖
dfs(0,hang,lie,zuoxie,youxie,map);//進行下去
}
private static void dfs(int hindex, boolean[] hang, boolean[] lie, boolean[] zuoxie, boolean[] youxie, int[][] map) {
if(hindex==8){
allnum++;
printmap(map);//輸出map
}
else{
//hindex為行 i為具體的某一列
for(int i=0;i<8;i++)
{
if(!hang[hindex]&&!lie[i]&&!zuoxie[hindex+i]&&!youxie[hindex+(7-i)])
{
hang[hindex]=true;//試探
lie[i]=true;
zuoxie[hindex+i]=true;
youxie[hindex+(7-i)]=true;
map[hindex][i]=1;
dfs(hindex+1,hang,lie,zuoxie,youxie,map);//dfs
hang[hindex]=false;//還原
lie[i]=false;
zuoxie[hindex+i]=false;
youxie[hindex+(7-i)]=false;
map[hindex][i]=0;
}
}
}
}
//輸出地圖
private static void printmap(int[][] map) {
System.out.println("第"+allnum+"個排列為");
for(int a[]:map)
{
System.out.println(Arrays.toString(a));
}
}
} 跑一邊就知道到底有多少種皇後，最終是92種皇後排列方式，不得不說能用數學方法接出來的是真的牛叉。
八皇後變種
此時我想八皇後問題已經搞得明明白白了，但是智慧的人們總是想出各種方法變化題目想難到我們，這種八皇後問題有很多變種，例如n皇後，數獨等問題。
這裡就簡單講講兩數獨問題的變種。
力扣36 有效的數獨
像這種題需要考慮和八皇後還是很像，改成9*9，隻不過在具體處理需要考慮
橫
、
豎
和
3x3小方格
。
當然這題比較簡單，還有一題就比較麻煩了 力扣37解數獨。
這一題有難度的就是需要我們每個位置都有資料都要去試探。
這種二維的回溯需要考慮一些問題，我們對于每一行每一行考慮。 每一行已經預有一些資料事先标記，在從開始試探放值，滿足條件後向下遞歸試探。一直到結束如果都滿足那麼就可以結束傳回數組值。
這裡的話有兩點需要注意的在這裡提一下：
- 用二維兩個參數進行遞歸回溯判斷起來誰加誰減比較麻煩，是以我們用一個參數index用它來計算橫縱坐标進行轉換，這樣就減少二維遞歸的一些麻煩。
- 回溯是一個來回的過程，在回來的過程正常情況需要将資料改回去，但是如果已經知道結果就沒必要再該回去可以直接停止放置回溯造成值的修改(這裡我用了一個isfinish的boolean類型進行判斷)。
代碼可以參考為：
結語
好啦，不知道這個專題結束之後能否能夠掌握這個八皇後的回溯算法以及思想，能否理清遞歸，回溯，深搜以及八皇後為關系？
總的來說
- 遞歸更注重一種方式，自己調用自己。
- 回溯更注重試探和複原，這個過程一般借助遞歸。
- dfs深度優先搜素，一般用棧或者遞歸去實作，如果用遞歸可能會複原也可能不複原資料，是以回溯是深搜的一種。
- 八皇後是經典回溯算法解決的問題，你說深度優先搜素其實也沒問題，但回溯更能精準的描述算法特征。
好啦，不說啦，我bigsai去領取佳麗30和白銀萬兩啦！(不錯的話記得一鍵三聯，微信搜尋bigsai，回複bigsai 下次迎娶美杜莎女王！)