N皇后解决方法

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.

For example,
There exist two distinct solutions to the 4-queens puzzle:

[
 [".Q..",  // Solution 1
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // Solution 2
  "Q...",
  "...Q",
  ".Q.."]
]
思路：回溯法去遍历一遍。

 1 #include<iostream>
 2 #include<vector>
 3 #include<string>
 4 using namespace std;
 5 class Solution {
 6 public:
 7     vector<vector<string>> solveNQueens(int n) {
 8         vector<vector<string>>res;
 9         vector<string> nQueens(n, string(n, '*'));
10         solveNqueens(res, nQueens, 0, n);
11         return res;
12     }
13     void solveNqueens(vector<vector<string>>&res, vector<string>&nQueens, int row, int &n)
14     {
15         if (row == n)
16         {
17             res.push_back(nQueens);
18             //vector<string> tmp(n, string(n, '****'));
19             //res.push_back(tmp);
20             return;
21         }
22         for (int i = 0; i<n; i++)
23         {
24             if (isValid(nQueens, row, i, n))
25             {
26                 nQueens[row][i] = 'Q';
27                 solveNqueens(res, nQueens, row + 1, n);
28                 nQueens[row][i] = '*';
29             }
30         }
31     }
32     bool isValid(vector<string>&nQueens, int row, int col, int n)
33     {
34         for (int i = 0; i<row; i++)
35         {
36             if (nQueens[i][col] == 'Q')return false;
37         }
38         for (int j = 0; j < col; j++)
39         {
40             if (nQueens[row][j] == 'Q')return false;
41         }
42         //check if the 45° diagonal had a queen before.
43         for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; --i, --j)
44         if (nQueens[i][j] == 'Q')
45             return false;
46         //check if the 135° diagonal had a queen before.
47         for (int i = row - 1, j = col + 1; i >= 0 && j < n; --i, ++j)
48         if (nQueens[i][j] == 'Q')
49             return false;
50         return true;
51     }
52 };
53 int main()
54 {
55     Solution a;
56     vector<vector<string>>res = a.solveNQueens(4);
57     for (int i = 0; i < res.size(); i++)
58     {
59         for (int j = 0; j < res[i].size(); j++)
60             cout << res[i][j] <<endl;
61         cout << endl;
62     }
63     cin.get();
64     return 0;
65 }