The n-queens puzzle is the problem of placing n queens on an n×n 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.
Example:
Input: 4 Output: [ [".Q..", // Solution 1 "...Q", "Q...", "..Q."], ["..Q.", // Solution 2 "Q...", "...Q", ".Q.."] ] Explanation: There exist two distinct solutions to the 4-queens puzzle as shown above.题意：返回N皇后的具体方案。
思路：做过很多次的题目了，就是形成方案的时候有点麻烦。代码如下：
class Solution { public: vector<int> colNote; //记录之前的每行(以1开始)的列号 vector<bool> colVis; //记录列号是否被使用过 vector<vector<string>> ans; //记录答案 string rowstr; //记录每行的字符串答案 int endGame; bool check(int row, int col) { for (int j = 0; j < row; ++j) if (abs(col - colNote[j]) == abs(row - j)) //和前几行是否成对角线 return false; return true; } void dfs(int row) { if (row >= endGame) { vector<string> tmp; for (int i = 0; i < colNote.size(); ++i) { //得到每行的列号 tmp.push_back(rowstr); tmp[i][colNote[i]] = 'Q'; //原来记录的行列都从1开始 } ans.push_back(tmp); return; } for (int i = 0; i < endGame; ++i) { if (!colVis[i] && check(row, i)) { //和前几行的列号是否相等或者成对角线 colNote[row] = i; colVis[i] = true; dfs(row + 1); colVis[i] = false; } } } vector<vector<string>> solveNQueens(int n) { if (n == 0 || n == 2 || n == 3) return vector<vector<string>>(); colNote.resize(n, 0); colVis.resize(n, false); endGame = n; rowstr.resize(n, '.'); dfs(0); //从第0行开始 return ans; } };感觉写的不咋地，但还是比Python快得多：
