**一. 題目描述** The n-queens puzzle is the problem of placing n queens on an nn chessboard such that no two queens attack each other.  Given an integer n, return all distinct solutions to the n-queens puzzle. Each solution contains a distinct board configuration of the n-queens’ placement, where ‘Q’ and ‘.’ both indicate a queen and an empty space respectively. For example, There exist two distinct solutions to the 4-queens puzzle: ~~~ [ [".Q..", // Solution 1 "...Q", "Q...", "..Q."], ["..Q.", // Solution 2 "Q...", "...Q", ".Q.."] ] ~~~ **二. 題目分析** 著名的N皇后問題，題目的意思是在一個`n×n`棋盤中，每行放一個棋子，使得棋子所在的列和兩條斜線上沒有其他棋子，打印所有可能。 使用深搜`dfs`去遍歷，考慮所有可能，`row`中標記每一行擺放棋子的對應下標的元素，`col`記錄當前列是否已有棋子，對角線的判斷就是兩點行差值和列差值是否相同。 當`dfs`深度達到`n`時，意味著已經可以遍歷完最低一層，存在滿足條件的解，把矩陣中個元素的信息轉化為`'.'`或`'Q'`，存到結果中。 **三. 示例代碼** ~~~ // 來源:http://blog.csdn.net/havenoidea/article/details/12167399 #include <iostream> #include <vector> using namespace std; class Solution { public: vector<vector<string> > solveNQueens(int n) { this->row = vector<int>(n, 0); // 行信息 this->col = vector<int>(n, 0); // 列信息 dfs(0, n, result); // 深搜 return result; } private: vector<vector<string> > result; // 存放打印的結果 vector<int> row; // 記錄每一行哪個下標是Q vector<int> col; // 記錄每一列是否已有Q void dfs(int r, int n, vector<vector<string> > & result) // 遍歷第r行，棋盤總共有n行 { if (r == n) // 可遍歷到棋盤底部，填入本次遍歷結果 { vector<string> temp; for (int i = 0; i < n; ++i) { string s(n, '.'); // 每行先被初始化為'.' s[row[i]] = 'Q'; // 每行下標被標記為1的元素被標記為Q temp.push_back(s); } result.push_back(temp); } int i, j; for (i = 0; i < n; ++i) { if (col[i] == 0) { for (j = 0; j < r; ++j) if (abs(r - j) == abs(row[j] - i)) break; if (j == r) { col[i] = 1; // 標記第i列，已存在Q row[j] = i; // 第j行的第i個元素放入Q dfs(r + 1, n, result); // 遍歷第r + 1行 col[i] = 0; row[j] = 0; } } } } }; ~~~  **四. 小結** 后續題目N-Queens II，其實比這一題簡化許多，因為只要求輸出解的個數，不需要輸出所有解的具體狀況。