LeetCode 51. N皇后

n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

上图为 8 皇后问题的一种解法。

给定一个整数 n，返回所有不同的 n 皇后问题的解决方案。

每一种解法包含一个明确的 n 皇后问题的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。

示例:

输入: 4
输出: [
 [".Q..",  // 解法 1
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // 解法 2
  "Q...",
  "...Q",
  ".Q.."]
]
解释: 4 皇后问题存在两个不同的解法。

 1 class Solution {
 2 public:
 3     vector<vector<string>> v;
 4     vector<string> vv;
 5     vector<int> path;
 6     int size;
 7     vector<vector<string>> solveNQueens(int n) {
 8         size = n;
 9         string s = "";
10         for(int i = 0;i < n;++i)
11         {
12             s += ".";
13         }
14         for(int i = 0;i < n;++i)
15         {
16             path.push_back(-1);
17         }
18         for(int i = 0;i < n;++i)
19             vv.push_back(s);
20         dfs(0);
21         return v;
22     }
23     void dfs(int x)
24     {      
25         if(x == size)
26         {
27             v.push_back(vv);
28         }
29         for(int i = 0;i < size; ++i)
30         {
31             if(check(x,i))
32             {
33                 path[x] = i;
34                 vv[x][i] = 'Q';
35                 dfs(x+1);
36                 path[x] = -1;
37                 vv[x][i] = '.';
38             }
39         }
40     }
41     bool check(int x,int k)
42     {
43         if(x == 0)
44             return true;
45         for(int i = 0;i < x;i++)
46         {
47             if(path[i] == k || abs(i - x) == abs(k - path[i]))
48             {
49                 return false;
50             }
51         }
52         return true;
53     }
54     
55 };