八皇后問題是在8*8的棋盤上放置8枚皇后，使得棋盤中每個縱向、橫向、左上至右下斜向、右上至左下斜向均只有一枚皇后。八皇后的一個可行解如圖所示：
| ? | ? | ? | ? | ? | ? | ? |
|
| ? | ? |
| ? | ? | ? | ? | ? |
|
| ? | ? | ? | ? | ? | ? | ? |
| ? | ? | ? | ? | ? |
| ? | ? |
| ? |
| ? | ? | ? | ? | ? | ? |
| ? | ? | ? | ? |
| ? | ? | ? |
| ? | ? | ? | ? | ? | ? |
| ? |
| ? | ? | ? |
| ? | ? | ? | ? |
思路
對于八皇后的求解可采用回溯算法，從上至下依次在每一行放置皇后，進行搜索，若在某一行的任意一列放置皇后均不能滿足要求，則不再向下搜索，而進行回溯，回溯至有其他列可放置皇后的一行，再向下搜索，直到搜索至最后一行，找到可行解，輸出。
此處可用借鑒陳海濤網易博客中的思路，不用二維數組，而采用一維數組進行回溯，參見http://www.cnblogs.com/jiayouwyhit/p/3226757.html。因為1維數組的下標即可表示行或者列，再在一維數組里面賦值，即可代表列或者行。此條件即可至少滿足八皇后問題的一個條件：兩個皇后不同行或者不同列。省去后文的一個步驟判斷。
?
本人參考網上別人的回溯思路，寫的代碼如下：（注意，本代碼已經在VC6.0下通過實驗測試）
//8皇后問題
//基于遞歸的回溯算法
const int length=8;
int counter=0;
bool Check(int matrix[], int row)//檢驗是否合理
{
??? int i=0;
??? for (i=0;i<=row-1;i++)
??? {
??????? if (matrix[i]==matrix[row] || row-i==matrix[row]-matrix[i] ||i-row==matrix[row]-matrix[i])
??????????? return false;
??? }
??? return true;
}
void EightQueen(int matrix[], int row)
{
??? int i=0,j=0;
??? for (i=0;i<length;i++)
??? {
??????? matrix[row]=i;
??????? if (Check(matrix,row) && row<=length-1)//滿足要求
??????? {
??????????? if (row==length-1)
??????????? {
??????????????? ++counter;
??????????????? printf("Solution %d:\n",counter);
??????????????? for (j=0;j<length;j++)
??????????????????? printf("%4d",matrix[j]);
??????????????? printf("\n");
??????????? }
??????????? else
????????????????? EightQueen(matrix,row+1);
??????? }
??? }
}
int main(int argc, char* argv[])
{
??? int matrix[length]={0};
??? EightQueen(matrix,0);
??? printf("We have solved the problem!\n");
??? return 0;
}
?
復雜度分析：本文算法的時間復雜度為O[n^(n+1)]。比http://www.cnblogs.com/jiayouwyhit/p/3226757.html時間復雜度更高.
實際上，經過實際的實驗測試，本文的算法實際上在時間上要比前面提到的算法性能要好很多。經過仔細分析，其原因在于：本文算法中對遞歸有一個限制條件
Check(matrix,row)，即：當當前點不滿足我們的約束條件時，直接就不再進行遞歸，因此函數void EightQueen(int matrix[], int row) 的時間復雜度會遠遠小于O[n^n]（假如不考慮check函數自身的時間復雜度的話）。但該算法具體的時間復雜度是多少，由于有判斷語句的存在，本人覺得此處無法寫出具體的復雜度表達式（再一次說明本人數學功底還有待提高啊\(^o^)/~）。
的時間復雜度)
)
