注：本帖主要進行個人記錄以及思考
1.八後問題：
百科介紹：
八皇後問題，是一個古老而著名的問題，是回溯算法的典型案例。該問題是國際西洋棋棋手馬克斯·貝瑟爾于1848年提出:在8×8格的國際象棋上擺放八個皇後，使其不能互相攻擊，
即任意兩個皇後都不能處于同一行、同一列或同一斜線上，問有多少種擺法。Problem Formulation ：
initial state：沒有棋子在棋盤上
goal state：八個皇後都在棋盤上，任意兩個皇後都不能處于同一行、同一列或同一斜線上
Actions：這裡開始的情況有兩種，一種是将queen放到棋盤左上角，這樣它不會受到任何queen的攻擊；另一種是随機進行擺放。
Path cost: 1 per move
遞歸解法：
遞歸是非常經典的一種解法
c語言版本：
/八皇後遞歸解法
#include<iostream>
using namespace std;
int queen[8]={-1,-1,-1,-1,-1,-1,-1,-1};int count=0;
bool available(int pointi,int pointj){//判斷某個皇後是否與已有皇後沖突 for(int i=0;i<pointi;i++){ if(pointj==queen[i])return false;//同一列拒絕 if((pointi-i)==(pointj-queen[i]))return false;//同一主對角線拒絕 if((pointi-i)==
(queen[i]-pointj))return false;//同一副對角線拒絕 } return true; }void findSpace(int queenNumber){//在第queenNumber行找能放皇後的位置
for(int i=1;i<9;i++){//從1~8周遊這一行的八個空位
if(available(queenNumber,i)){
//如果可以放這個位置就記錄下第queenNumber個皇後的位置
queen[queenNumber]=i;
if(queenNumber==8){//如果八個皇後都放滿了統計一下
count++;
return;
}
int nextNumber=queenNumber+1;//還有皇後沒放遞歸放下一個皇後
findSpace(nextNumber);
}
}
queen[--queenNumber]=-1;//如果這一行沒有可放的位置說明上一行皇後放的位置不行，要為上一個皇後尋找新的可放位置
return;
}
int main(){
findSpace(1);//從（1，1）開始遞歸好了解
cout<<count<<endl;
return 0;
}
這裡借用是的csdn上一個大佬c語言寫的解法，是以把原大佬的代碼和網址都放上來看看~
CSDN-專業IT技術社群-登入blog.csdn.net
2.“Missionaries & Cannibals” 傳道士與野人問題
三個傳教士和三個食人族來到一條河邊。有一艘可坐兩個人的劃艇。如果食人族的數量超過了在河兩岸的傳教士，傳教士就會被吃掉。
哈哈，這個問題暫時跳過
3.Tower of Hanio 漢諾塔問題
漢諾塔問題是一個經典的問題。漢諾塔（Hanoi Tower），又稱河内塔，源于印度一個古老傳說。大梵天創造世界的時候做了三根金剛石柱子，在一根柱子上從下往上按照大小順序摞着64片黃金圓盤。大梵天指令婆羅門把圓盤從下面開始按大小順序重新擺放在另一根柱子上。并且規定，任何時候，在小圓盤上都不能放大圓盤，且在三根柱子之間一次隻能移動一個圓盤。問應該如何操作？
這是個遞歸問題，上學期最後一節java的lecture上接觸到的，為什麼記憶如此深刻呢，因為我到現在才想明白....
話不多說，我們來簡單描述一下思路。
漢諾塔問題為什麼讓人迷惑呢？如果和先前的我一樣沒有一個整體的思路，隻會一步步試驗的話，就完全解決不了問題。那麼如何吧這個問題簡化分解掉呢？
這就是算法裡的merge sort了，我們首先要把問題細分為小問題。我們把目标柱稱為c柱，中轉柱（實際上他不一定一直是中轉柱，但是為了差別我還是命名為中轉柱）稱為b柱，最後把初始柱稱為a柱。
這裡我們可以确定，我們一定是先把第六十四個disk放到c柱上，那麼這個時候我們的a柱就隻有一個disk，其他63個disk都在b柱上，并且in order。
下一步我們需要幹什麼呢？我們需要把第63個disk取出，放到c柱上，這個時候其餘62個disk一定是在a柱上。
這樣一看是不是就把我們遞歸的重複行為弄清楚了？然後我們的basic case便是n=1的時候，于是我們可以寫下個一個思路。
當然這個是非常簡單的，那麼如何執行裡面的move呢？
public static void resolve(int n, Stack<Integer> a, Stack<Integer> b, Stack<Integer> c) {
if (n==0) return;
resolve(n-1, a, c, b);
c.push(a.pop());
resolve(n-1, b, a, c);
}
這是直接捉的一位大佬的代碼，我們的中轉柱的位置不變，就是abc三個變量中中間那個，，然而我們通過抽象化的表達，用柱子上的disk數目來表達柱子，我們在将source柱子上第一個disk挪到中轉柱上後，改變了我們放置下一個disk的柱子，也就是我們将b柱上的disk轉移到原先的a柱上（這個時候a為中轉柱），一直重複這個行為，直到n=0。
可能表達不大清楚！見諒！
附上大佬直通位址：
漢諾塔問題 - Antineutrino - 部落格園www.cnblogs.com
