大家好，我是“Stephen·謝”第练，本文以古老的八皇后問題的文字解釋和代碼實(shí)現(xiàn)，將遞歸回溯的思想概念介紹給大家呕寝。
國際象棋中的皇后比中國象棋里的大車還厲害下梢，皇后能橫向，縱向和斜向移動(dòng)讶坯，在這三條線上的其他棋子都可以被吃掉岗屏。所謂八皇后問題就是：將八位皇后放在一張8x8的棋盤上这刷，使得每位皇后都無法吃掉別的皇后，（即任意兩個(gè)皇后都不在同一條橫線似袁，豎線和斜線上），問一共有多少種擺法扬霜。此問題是在1848年由棋手馬克思·貝瑟爾提出的而涉，后面陸續(xù)有包括高斯等大數(shù)學(xué)家們給出自己的思考和解法婴谱，所以此問題不只是有年頭了，簡直比82年的拉菲還有年頭华糖，我們今天不妨嘗嘗這老酒瘟裸。
我們先舉例來理解一下這個(gè)問題的場景到底是什么樣子的话告，下面的綠色格子是一個(gè)皇后在棋盤上的“封鎖范圍”，其他的皇后不能放置在這些綠格子中：
我們再放入一個(gè)皇后佛呻，看一下兩個(gè)皇后的“封鎖范圍”（綠格子不能放）：
如此繼續(xù)下去吓著，能安放下一位皇后的位置越來越少绑莺，那么我們最終如何能安放完這8位皇后呢惕耕？
首先我們看一下特別暴力的方法：從8x8的格子里選8個(gè)格子司澎，放皇后，然后測試是否滿足條件浪南，若滿足則結(jié)果加1漱受，否則換8個(gè)格子繼續(xù)試。很顯然絮记，64選8怨愤，并不是個(gè)小數(shù)字，十億級(jí)別的次數(shù)篮愉，夠暴力差导。如果換成圍棋的棋盤设褐，畫面就會(huì)太美而不敢算。
稍加分析犀被，我們可以得到另一個(gè)不那么暴力的方法：顯然寡键，每行每列最多只能有一位皇后雪隧，如果基于這個(gè)事實(shí)再進(jìn)行暴力破解，那結(jié)果會(huì)好很多膀跌。安排皇后時(shí)，第一行有8種選法固灵，一旦第一行選定捅伤，假設(shè)選為（1，i）巫玻，那么第二行只能選（2丛忆，j），其中仍秤，j不等于i熄诡，所以有7種選法。以此類推诗力，需要窮舉的情況有8！=40320種，比十億級(jí)別的小很多了袜茧。
這看起來已經(jīng)不錯(cuò)了菜拓，但嘗試的次數(shù)還是隨著問題規(guī)模按階乘水平提高的，我們?nèi)匀徊粷M意笛厦，所以纳鼎，“遞歸回溯”的思想就被提出了，專治這種問題裳凸。
為了理解“遞歸回溯”的思想贱鄙，我們不妨先將4位皇后打入冷宮，留下剩下的4位安排進(jìn)4x4的格子中且不能互相打架姨谷，有多少種安排方法呢逗宁？如果按照上面方式窮舉，需要4菠秒！=24次嘗試嗎疙剑？
現(xiàn)在我們把第一個(gè)皇后放在第一個(gè)格子，被涂黑的地方是不能放皇后的：
第二行的皇后只能放在第三格或第四格践叠，比如我們放在第三格：
這樣一來前面兩位皇后已經(jīng)把第三行全部鎖死了言缤，第三位皇后無論放在第三行的哪里都難逃被吃掉的厄運(yùn)。于是在第一個(gè)皇后位于第一格禁灼，第二個(gè)皇后位于第三格的情況下此問題無解管挟。所以我們只能返回上一步，來給2號(hào)皇后換個(gè)位置：
此時(shí)弄捕，第三個(gè)皇后只有一個(gè)位置可選僻孝。當(dāng)?shù)谌齻€(gè)皇后占據(jù)第三行藍(lán)色空位時(shí)，第四行皇后無路可走守谓，于是發(fā)生錯(cuò)誤穿铆，則返回上層調(diào)整3號(hào)皇后，而3號(hào)皇后也別無可去斋荞，繼續(xù)返回上層調(diào)整2號(hào)皇后荞雏，而2號(hào)皇后已然無路可去，則再繼續(xù)返回上層調(diào)整1號(hào)皇后平酿，于是1號(hào)皇后往后移一格位置如下凤优，再繼續(xù)往下安排：
上面的圖例正是回溯遞歸思想的展現(xiàn)，然而知易行難蜈彼，在代碼中我們怎樣來實(shí)現(xiàn)這種算法呢筑辨？實(shí)現(xiàn)的代碼有很多種，我們找一個(gè)最簡單的來舉例吧：
我們來重點(diǎn)看一下這段代碼（這段代碼雖短幸逆，但真的非常非常重要棍辕，是整個(gè)算法的核心和靈魂）：
第一次進(jìn)來暮现，row=0，意思是要在第一行擺皇后痢毒，只要傳進(jìn)來的row參數(shù)不是8送矩，表明還沒出結(jié)果，就都不會(huì)走if里面的return哪替，那么就進(jìn)入到for循環(huán)里面栋荸，column從0開始，即第一列凭舶。此時(shí)第一行第一列肯定合乎要求（即check方法肯定通過）晌块，能放下皇后，因?yàn)檫€沒有任何其他皇后來干擾帅霜。
關(guān)鍵是check方法通過了之后匆背，在if里面又會(huì)調(diào)用一下自己（即遞歸），row加了1身冀，表示擺第二行的皇后了钝尸。第二行的皇后在走for循環(huán)的時(shí)候，分兩種情況搂根，第一種情況：for循環(huán)沒走到頭時(shí)就有通過check方法的了珍促，那么這樣就順理成章地往下走再調(diào)用一下自己（即再往下遞歸），row再加1（即擺第三行的皇后了剩愧，以此類推）猪叙。第二種情況：for循環(huán)走到頭了都沒有通過check方法的，說明第二行根本一個(gè)皇后都擺不了仁卷，也觸發(fā)不了遞歸穴翩，下面的第三行等等后面的就更不用提了，此時(shí)控制第一行皇后位置的for循環(huán)column加1锦积，即第一行的皇后往后移一格芒帕，即擺在第一行第二列的位置上，然后再往下走丰介，重復(fù)上述邏輯背蟆。
注意，一定要添加清零的代碼基矮，它只有在皇后擺不下去的時(shí)候會(huì)執(zhí)行清0的動(dòng)作（避免臟數(shù)據(jù)干擾）淆储，如果皇后擺放很順利的話從頭到尾是不會(huì)走這個(gè)請0的動(dòng)作的冠场，因?yàn)橐呀?jīng)提前走if里面的return方法結(jié)束了家浇。
總之，這段核心代碼很繞碴裙，原理一定要想通钢悲，想個(gè)十幾二十遍差不多就能理解其中的原理了点额，遞歸回溯的思想也就不言而喻了。八皇后問題一共有92種情況莺琳，下面是用Java實(shí)現(xiàn)的完整代碼：
public static int[][] arry=new int[8][8];//棋盤还棱，放皇后
public static int map=0;//存儲(chǔ)方案結(jié)果數(shù)量
public static void main(String[] args) {
// TODO Auto-generated method stub
System.out.println("八皇后問題");
findQueen(0);
System.out.println("八皇后問題共有："+map+"種可能");
}
public static void findQueen(int i){//尋找皇后節(jié)點(diǎn)
if(i>7){//八皇后的解
map++;
print();//打印八皇后的解
return;
}
for(int m=0;m<8;m++){//深度回溯,遞歸算法
if(check(i,m)){//檢查皇后擺放是否合適
arry[i][m]=1;
findQueen(i+1);
arry[i][m]=0;//清零，以免回溯的時(shí)候出現(xiàn)臟數(shù)據(jù)
}
}
}
public static boolean check(int k,int j){//判斷節(jié)點(diǎn)是否合適
for(int i=0;i<8;i++){//檢查行列沖突
if(arry[i][j]==1){
return false;
}
}
for(int i=k-1,m=j-1; i>=0 && m>=0; i--,m--){//檢查左對(duì)角線
if(arry[i][m]==1){
return false;
}
}
for(int i=k-1,m=j+1; i>=0 && m<=7; i--,m++){//檢查右對(duì)角線
if(arry[i][m]==1){
return false;
}
}
return true;
}
public static void print(){//打印結(jié)果
System.out.print("方案"+map+":"+"\n");
for(int i=0;i<8;i++){
for(int m=0;m<8;m++){
if(arry[i][m]==1){
//System.out.print("皇后"+(i+1)+"在第"+i+"行惭等，第"+m+"列\(zhòng)t");
System.out.print("o ");
}
else{
System.out.print("+ ");
}
}
System.out.println();
}
System.out.println();
}
