題目
上一篇我們使用了回溯法，然而提到回溯法就不得不提一個1848年提出的經典題目：8皇後問題，這個問題描述非常簡單，一個8*8的棋盤上，放置8個皇後，使得每個皇後都不行互相攻擊，既每個皇後的所在行、所在列、所在斜線上都不能有其他皇後，問有多少種解法，題目初看非常像圖論問題，實際上也确實是，對圖論感興趣的同學可以去看離散數學的相關内容，這裡我們用一種更巧妙也更直覺的方法來解決這個問題，那就是——回溯法
在這道經典題目和後面的幾篇微網誌所讨論的題目，我們可以感受到回溯法在解決一些限定某些條件求解（求路徑）的問題上是一個多麼萬能又精巧的的算法
題目:
The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.
return the total number of distinct solutions.
Difficulty: Hard
分析：
題目沒有局限于8皇後而是進行了延伸，擴充到n皇後，實際上原理是一模一樣的
初看題目可能沒有頭緒，想到回溯法卻不知道切入點在哪，實際上，對于回溯法問題，無非是給定的“圖”和限定條件：
這裡圖就是一個n*n的方格，我們先抽象成一個n*n的矩陣，用二維數組代替，皇後可以抽象為矩陣中的元素，用二維數組中的元素代替，不妨設0是沒有放皇後，1是放了皇後
限定條件既矩陣中的元素互相不在同一行同一列同一斜線，轉化為二維數組後我們發現對于不同行不同列是很好判斷的，比如，方格坐标為(i,j)，隻要在決定一個方格放不放皇後的時候檢查第i行第j列是否有其他皇後就可以，斜線似乎有點棘手，實際上我們抽象出兩個皇後就可以看出來解決方案：
看看這兩條線，假設方程分别為： y=kx+b; 其中 A(x1,y1) B(x2,y2) 兩點分别是兩條線上的點，我麼代入原方程然後相減就可以得到： y2−y1=k(x2−x1) 因為是棋盤，這裡 k 隻有+1,−1兩個取值，于是我們就可以得到 |y2−y1|=|x2−x1|
最後一個問題就是怎樣儲存已經放置皇後的位置，最直覺的想法就是把二位數組放置皇後的位置置1
方案：
解決了這三個個問題，我們很直覺得出解法：
start：
初始化數組
放置皇後{
if(放置位置超出範圍){
求解數自增，傳回
}
else{
for(從第一行開始到最後一行){
if(位置可放皇後) 放置
遞歸檢查下一個放置皇後位置
}
}
}
end
代碼
這裡我們可以發現，由于規則中同一行隻能有一個皇後，是以我們不必要用一個二維數組來模拟棋盤，隻要一個一位數組，每個元素代表是否存在皇後就可以完成記錄放置點的任務，是以最終的代碼如下：
class Solution {
private:
vector<int> queen;
//記錄解的個數
int count = ;
public:
//檢查位置是否可放皇後
bool CheckPlace(int Checkline, int Checkrow) {
for (int i = ; i < Checkline; i++) {
if (queen[i] == Checkrow || abs(Checkline - i) == abs(Checkrow - queen[i])) {
return false;
}
}
return true;
}
//放置皇後
void PlaceQueen(int Checkline, int n) {
if (Checkline == n) {
count++;
return;
}
//如果沒有完成一個解就繼續
else {
for (int i = ; i < n; i++) {
if (CheckPlace(Checkline, i)) {
queen[Checkline] = i;
PlaceQueen(Checkline + , n);
}
}
}
}
int totalNQueens(int n) {
queen.resize(n);
PlaceQueen(, n);
return count;
}
};
通過上面的分析，這個代碼是很容易了解的，但是歲回溯法或者對遞歸不熟悉的同學肯定會有疑問（就是當初的我。。。），代碼裡隻有一個0-n的循環，如何保證求出所有解，沒有足夠的判斷語句又是如何保證不會出現相同的解的呢？
而這實際上就是遞歸實作回溯法的優點，要想說明這個問題，我們需要看這段代碼：
void PlaceQueen(int Checkline, int n) {
if (Checkline == n) {
count++;
return;
}
//如果沒有完成一個解就繼續
else {
for (int i = ; i < n; i++) {
if (CheckPlace(Checkline, i)) {
queen[Checkline] = i;
PlaceQueen(Checkline + , n);
}
}
}
}
一個重要問題
我們跟着代碼走一遍，看看他做了什麼，第一個解的求解非常好了解，我們假設第一個解求完，由于每次都是for循環隻進行一次就從
PlaceQueen(Checkline + 1, n)
進入了下次遞歸，是以我們已經進入了8次遞歸嵌套，此時for循環中 依然
i==0
，然後放置皇後，
Checkline==7
，代表第8行皇後放置完畢
PlaceQueen(Checkline + 1, n)
語句會進入下一次遞歸，然後
Checkline==8
if (Checkline == n)
條件成立，執行
return
指令，傳回到哪裡了呢？
傳回到了上一層進入點，就是這裡：
PlaceQueen(Checkline + 1, n)
下面，既這條語句已經執行完，
i++
，此時繼續循環
由于我們每次遞歸的退出都是确定了8個點的位置，然後改變最後的點，求下個解，這樣一步步的回退，保證不會有重複解，而且，一個8次的循環，每次要嵌套8層遞歸，實際上是做了8^8次探測，保證不會漏解
從上面的分析可以看出來，N皇後的結題時間是指數倍增長，上面的算法，解8皇後不到1ms，解10皇後20ms，12皇後就需要596ms之多
總結
回溯法的遞歸實作對于解決這樣的大規模複雜問題不是最高效的，但往往是最直覺也是最容易了解的，畢竟當年數學之王高斯都隻算出76中解法的問題我們用回溯法，不用1ms就求出了正确答案
當然，想隻憑這一道題就掌握回溯法是不可能的，下面我會寫一系列的回溯法題解，隻有大量的練習，才是真正了解問題并能夠實際解決問題的唯一途徑