文章收錄在公眾號(hào)：bigsai 更多精彩干貨敬請(qǐng)關(guān)注！

前言

說(shuō)起八皇后問(wèn)題，它是一道回溯算法類的經(jīng)典問(wèn)題，也可能是我們大部分人在上數(shù)據(jù)結(jié)構(gòu)或者算法課上遇到過(guò)的最難的一道題……

第一次遇到它的時(shí)候應(yīng)該是大一下或者大二這個(gè)期間，這個(gè)時(shí)間對(duì)啥都懵懵懂懂，啥都想學(xué)卻發(fā)現(xiàn)好像啥都挺難的，八皇后同樣把那個(gè)時(shí)候的我阻攔在外，我記得很清楚當(dāng)時(shí)大二初我們學(xué)業(yè)導(dǎo)師給我們開(kāi)班會(huì)時(shí)候講到的一句話很清晰：“如果沒(méi)有認(rèn)真的學(xué)習(xí)算法他怎么可能解出八皇后的代碼呢”。

確實(shí)，那個(gè)時(shí)候的我搞不懂遞歸，回溯也沒(méi)聽(tīng)過(guò)，連Java的集合都沒(méi)用明白，毫無(wú)邏輯可言，八皇后對(duì)我來(lái)說(shuō)確實(shí)就是無(wú)從下手。

但今天，我可以吊打八皇后了，和你們一起白銀萬(wàn)兩，佳麗三十。

淺談遞歸

對(duì)于遞歸算法，我覺(jué)得掌握遞歸是入門(mén)數(shù)據(jù)結(jié)構(gòu)與算法的關(guān)鍵，因?yàn)楹竺鎸W(xué)習(xí)很多操作涉及到遞歸，例如鏈表的一些操作、樹(shù)的遍歷和一些操作、圖的dfs、快排、歸并排序等等。

遞歸的實(shí)質(zhì)還是借助棧實(shí)現(xiàn)一些操作，利用遞歸能夠完成的操作使用棧都能夠完成，并且利用棧的話可以很好的控制停止，效率更高(遞歸是一個(gè)來(lái)回的過(guò)程回來(lái)的時(shí)候需要特判)。

遞歸實(shí)現(xiàn)和棧實(shí)現(xiàn)操作的區(qū)別，遞歸對(duì)我們來(lái)說(shuō)更簡(jiǎn)潔巧妙，并且用多了會(huì)發(fā)現(xiàn)很多問(wèn)題的處理上遞歸的思考方式更偏向人的思考方式，而棧的話就是老老實(shí)實(shí)用計(jì)算機(jī)(數(shù)據(jù)結(jié)構(gòu)特性)的思維去思考問(wèn)題。這個(gè)你可以參考二叉樹(shù)的遍歷方式遞歸和非遞歸版本，復(fù)雜性一目了然。

從遞歸算法的特征上來(lái)看，遞歸算法的問(wèn)題都是父問(wèn)題可以用過(guò)一定關(guān)系轉(zhuǎn)化為子問(wèn)題。即從后往前推導(dǎo)的過(guò)程，一般通過(guò)一個(gè)參數(shù)來(lái)表示當(dāng)前的層級(jí)。

而遞歸的主要特點(diǎn)如下：

• 自己調(diào)用自己
• 遞歸通常不在意具體操作，只關(guān)心初始條件和上下層的變化關(guān)系。
• 遞歸函數(shù)需要有臨界停止點(diǎn)，即遞歸不能無(wú)限制的執(zhí)行下去。通常這個(gè)點(diǎn)為必須經(jīng)過(guò)的一個(gè)數(shù)。
• 遞歸可以被棧替代。有些遞歸可以優(yōu)化。比如遇到重復(fù)性的可以借助空間內(nèi)存記錄而減少遞歸的次數(shù)。

而通常遞歸算法的一個(gè)流程大致為：

定義遞歸算法及參數(shù) - 停止遞歸算法條件 - (可存在)其他邏輯 - 遞歸調(diào)用(參數(shù)需要改變) - (可存在)其他邏輯

如果還是不理解的話就要看我的另一篇文章了：數(shù)據(jù)結(jié)構(gòu)與算法—遞歸算法(從階乘、斐波那契到漢諾塔的遞歸圖解)，寫(xiě)的是真的好！

回溯算法

談完遞歸，你可能明白有這么一種方法可以使用，但你可能感覺(jué)單單的遞歸和八皇后還是很難扯上關(guān)系，是的沒(méi)錯(cuò)，所以我來(lái)講回溯算法了。

這里插個(gè)小插曲。前天(真的前天)有個(gè)舍友我們宿舍一起聊天的時(shí)候談到回溯算法，他說(shuō)回shuo(朔)算法，我們差異的糾正了一下是回su(素)算法，他竟然讀錯(cuò)了四年……不知道路過(guò)的你們有沒(méi)有讀錯(cuò)的。

咱們言歸正傳，算法界中，有五大常用算法：貪心算法、分治算法、動(dòng)態(tài)規(guī)劃算法、回溯算法、分支界限算法。咱們回溯算法就是五大之一，因?yàn)榛厮菟惴軌蚪鉀Q很多實(shí)際的問(wèn)題，盡管很多時(shí)候復(fù)雜度可能不太小，但大部分情況都能得到一個(gè)不錯(cuò)的結(jié)果。

對(duì)于回溯法的定義，百度百科是這么定義的：

回溯算法實(shí)際上一個(gè)類似枚舉的搜索嘗試過(guò)程，主要是在搜索嘗試過(guò)程中尋找問(wèn)題的解，當(dāng)發(fā)現(xiàn)已不滿足求解條件時(shí)，就“回溯”返回，嘗試別的路徑。回溯法是一種選優(yōu)搜索法，按選優(yōu)條件向前搜索，以達(dá)到目標(biāo)。但當(dāng)探索到某一步時(shí)，發(fā)現(xiàn)原先選擇并不優(yōu)或達(dá)不到目標(biāo)，就退回一步重新選擇，這種走不通就退回再走的技術(shù)為回溯法，而滿足回溯條件的某個(gè)狀態(tài)的點(diǎn)稱為“回溯點(diǎn)”。許多復(fù)雜的，規(guī)模較大的問(wèn)題都可以使用回溯法，有“通用解題方法”的美稱。

對(duì)于回溯法，它的核心就是試探和復(fù)原。這個(gè)自動(dòng)化的過(guò)程就是利用遞歸去執(zhí)行，在遞歸函數(shù)執(zhí)行前去修改嘗試，滿足條件后向下遞歸試探，試探完畢后需要將數(shù)值復(fù)原。在這個(gè)試探的過(guò)程中找到我們所需要的一個(gè)或者所有解。這個(gè)我們也俗稱暴力。

啥？沒(méi)聽(tīng)懂？好，那我就再講講，你應(yīng)該知道深度優(yōu)先搜索(dfs)吧？其實(shí)回溯算法就是一種特殊的dfs。之所以叫回溯，就是因?yàn)檫@類算法在運(yùn)用遞歸都有個(gè)復(fù)原的過(guò)程，所以前面的操作就相當(dāng)于試探一樣。而這類算法一般常常配對(duì)一個(gè)或多個(gè)boolean類型的數(shù)組用來(lái)標(biāo)記試探途中用過(guò)的點(diǎn)。

舉個(gè)例子，我們知道回溯算法用來(lái)求所有數(shù)字的排列順序。我們分析其中一個(gè)順序。比如數(shù)列6 8 9這個(gè)序列的話，我們用來(lái)求它的排列順序。

對(duì)于代碼塊來(lái)說(shuō)，這可能很容易實(shí)現(xiàn)：

import java.util.Arrays;public class test {public static void main(String[] args) {int arr[]={6,8,9};//需要排列組合的數(shù)組int val[]={0,0,0};//臨時(shí)儲(chǔ)存的數(shù)組boolean jud[] = new boolean[arr.length];// 判斷是否被用dfs(arr,val, jud, 0,"");//用一個(gè)字符串長(zhǎng)度更直觀看結(jié)果}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]) {//當(dāng)前不能用的int team=val[index];val[index] = arr[i];jud[i] = true;// 下層不能在用dfs(arr, val, jud, index + 1,s+" _ ");jud[i] = false;// 還原val[index]=team;}}}} }

而執(zhí)行的結(jié)果為：

這里再配張圖理解：

而通常回溯算法的一個(gè)流程大致為：

定義回溯算法及參數(shù) - (符合條件)跳出 - (不符合)不跳出： - - 遍歷需要操作的列表&&該元素可操作&&可以繼續(xù)試探 - - - 標(biāo)記該元素已使用以及其他操作 - - - 遞歸調(diào)用(參數(shù)改變) - - - 清除該元素標(biāo)記以及其他操作

也就是在使用數(shù)組進(jìn)行回溯的時(shí)候，使用過(guò)的時(shí)候需要標(biāo)記子遞歸不能再使用防止死循環(huán)，而當(dāng)回來(lái)的時(shí)候需要解封該位置，以便該編號(hào)位置被其他兄弟使用之后這個(gè)數(shù)值在后面能夠再次使用！而如果使用List或者StringBuilder等動(dòng)態(tài)空間用來(lái)進(jìn)行回溯的時(shí)候記得同樣的復(fù)原，刪了要記得增，減了要記得加。搞明白這些，我想回溯算法也應(yīng)該難不倒你了吧。

八皇后問(wèn)題

掌握了回溯算法的關(guān)鍵，八皇后問(wèn)題多思考就可以想的出來(lái)了。前面的講解都是為了解決八皇后問(wèn)題做鋪墊。首先，我們認(rèn)真的看下八皇后問(wèn)題描述。

八皇后問(wèn)題（英文：Eight queens），是由國(guó)際西洋棋棋手馬克斯·貝瑟爾于1848年提出的問(wèn)題，是回溯算法的典型案例。

問(wèn)題表述為：在8×8格的國(guó)際象棋上擺放8個(gè)皇后，使其不能互相攻擊，即任意兩個(gè)皇后都不能處于同一行、同一列或同一斜線上，問(wèn)有多少種擺法。高斯認(rèn)為有76種方案。1854年在柏林的象棋雜志上不同的作者發(fā)表了40種不同的解，后來(lái)有人用圖論的方法解出92種結(jié)果。如果經(jīng)過(guò)±90度、±180度旋轉(zhuǎn)，和對(duì)角線對(duì)稱變換的擺法看成一類，共有42類。計(jì)算機(jī)發(fā)明后，有多種計(jì)算機(jī)語(yǔ)言可以編程解決此問(wèn)題。

我們?cè)撛趺此伎歼@種問(wèn)題呢?也就是從何入手呢？

• 從限制條件入手

八皇后問(wèn)題有以下限制條件：

• 8 x 8的方格
• 每行一個(gè)，共八行(0-7)
• 每列一個(gè)，共八列(0-7)
• 每左斜杠一個(gè)，共十五左斜杠(0-14)
• 每右斜杠一個(gè)，共十五右斜杠(0-14)

當(dāng)看到這些限制條件，肯定想到這么多限制條件需要判斷。判斷的話當(dāng)然就是借助boolean數(shù)組啦。還是一維的8個(gè)大小，所以我們首先用4個(gè)boolean數(shù)組用來(lái)判斷各自的條件是否被滿足。

表示這個(gè)圖的話我們可以使用一個(gè)int類型數(shù)組表示，0表示沒(méi)有，1表示有皇后。

那么如何去設(shè)計(jì)這個(gè)算法呢？這個(gè)并不是每個(gè)格子都有數(shù)字，所以在進(jìn)行回溯的時(shí)候不應(yīng)該每個(gè)格子每個(gè)格子進(jìn)行向下遞歸(同行互斥)，也就是遞歸到當(dāng)前層的時(shí)候，循環(huán)遍歷該層的八種情況進(jìn)行試探(每個(gè)都試探)，如果不滿足條件的就不操作而被終止掉，但該行每個(gè)滿足條件的需要遞歸的時(shí)候需要進(jìn)入到下一行。

當(dāng)然你需要提前知道當(dāng)前位置橫縱坐標(biāo)怎們知道對(duì)應(yīng)的boolean位置(位置從0號(hào)開(kāi)始計(jì)算)。例如位置p(x,y)中對(duì)應(yīng)的位置為：

• hang[] : x 每一行就是對(duì)應(yīng)的i。
• lie[] : y 每一列就是對(duì)應(yīng)的j。
• zuoxie[] : x+y 規(guī)定順序?yàn)樽笊系接蚁?/li>
• youxie[] : x+(7-y) 規(guī)定順序?yàn)橛疑系阶笙?個(gè)人習(xí)慣)

好啦，該算法的實(shí)現(xiàn)代碼為：

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);//進(jìn)行下去}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);//dfshang[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+"個(gè)排列為");for(int a[]:map){System.out.println(Arrays.toString(a));}} }

跑一邊就知道到底有多少種皇后，最終是92種皇后排列方式，不得不說(shuō)能用數(shù)學(xué)方法接出來(lái)的是真的牛叉。

八皇后變種

此時(shí)我想八皇后問(wèn)題已經(jīng)搞得明明白白了，但是智慧的人們總是想出各種方法變化題目想難到我們，這種八皇后問(wèn)題有很多變種，例如n皇后，數(shù)獨(dú)等問(wèn)題。

這里就簡(jiǎn)單講講兩數(shù)獨(dú)問(wèn)題的變種。

力扣36 有效的數(shù)獨(dú)

像這種題需要考慮和八皇后還是很像，改成9*9，只不過(guò)在具體處理需要考慮橫、豎和3x3小方格。

當(dāng)然這題比較簡(jiǎn)單，還有一題就比較麻煩了 力扣37解數(shù)獨(dú)。

這一題有難度的就是需要我們每個(gè)位置都有數(shù)據(jù)都要去試探。

這種二維的回溯需要考慮一些問(wèn)題，我們對(duì)于每一行每一行考慮。 每一行已經(jīng)預(yù)有一些數(shù)據(jù)事先標(biāo)記，在從開(kāi)始試探放值，滿足條件后向下遞歸試探。一直到結(jié)束如果都滿足那么就可以結(jié)束返回?cái)?shù)組值。

這里的話有兩點(diǎn)需要注意的在這里提一下：

• 用二維兩個(gè)參數(shù)進(jìn)行遞歸回溯判斷起來(lái)誰(shuí)加誰(shuí)減比較麻煩，所以我們用一個(gè)參數(shù)index用它來(lái)計(jì)算橫縱坐標(biāo)進(jìn)行轉(zhuǎn)換，這樣就減少二維遞歸的一些麻煩。
• 回溯是一個(gè)來(lái)回的過(guò)程，在回來(lái)的過(guò)程正常情況需要將數(shù)據(jù)改回去，但是如果已經(jīng)知道結(jié)果就沒(méi)必要再該回去可以直接停止放置回溯造成值的修改(這里我用了一個(gè)isfinish的boolean類型進(jìn)行判斷)。

代碼可以參考為：

結(jié)語(yǔ)

好啦，不知道這個(gè)專題結(jié)束之后能否能夠掌握這個(gè)八皇后的回溯算法以及思想，能否理清遞歸，回溯，深搜以及八皇后為關(guān)系？

總的來(lái)說(shuō)

• 遞歸更注重一種方式，自己調(diào)用自己。
• 回溯更注重試探和復(fù)原，這個(gè)過(guò)程一般借助遞歸。
• dfs深度優(yōu)先搜素，一般用棧或者遞歸去實(shí)現(xiàn)，如果用遞歸可能會(huì)復(fù)原也可能不復(fù)原數(shù)據(jù)，所以回溯是深搜的一種。
• 八皇后是經(jīng)典回溯算法解決的問(wèn)題，你說(shuō)深度優(yōu)先搜素其實(shí)也沒(méi)問(wèn)題，但回溯更能精準(zhǔn)的描述算法特征。

好啦，不說(shuō)啦，我bigsai去領(lǐng)取佳麗30和白銀萬(wàn)兩啦！(不錯(cuò)的話記得一鍵三聯(lián)，微信搜索bigsai，回復(fù)bigsai 下次迎娶美杜莎女王！)

總結(jié)

以上是生活随笔為你收集整理的回溯算法 | 追忆那些年曾难倒我们的八皇后问题的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。