LeetCode #51

# Description:

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:

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

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

["..Q.",  // Solution 2
"Q...",
"...Q",
".Q.."]
]
``````

# Idea:

N Queens与N Queens II很类似，II需要把结果存下来，而不是count增加。

Mark的是occupy哪列和哪些对角线，Backtrack也是这些。II的时候，还要存暂时的结果，不过不需要backtrack temporary result.

# Code:

``````class Solution {
public:
vector<vector<string>> solveNQueens(int n) {
vector<bool> column_occupy(n, false);
vector<bool> diag_occupy(2*n-1, false);
vector<bool> anti_diag_occupy(2*n-1, false);
vector<vector<string>> result;
vector<int> queens(n, -1);
DFS(0, queens, result, column_occupy, diag_occupy, anti_diag_occupy);
return result;
}

void DFS(int row, vector<int>& queens, vector<vector<string>>& result, vector<bool>& column_o, vector<bool>& diag_o, vector<bool>& anti_diag_o){
int N=column_o.size();
if(row==N){
vector<string> solution(N, string(N, '.'));
for(int i=0; i<row; ++i){
solution[i][queens[i]]='Q';
}
result.push_back(solution);
return;
}

// j is column index
for(int j=0; j<N; ++j){
if(!column_o[j] && !diag_o[row+j] && !anti_diag_o[N-1-row+j]){
queens[row]=j;
column_o[j]=diag_o[row+j]=anti_diag_o[N-1-row+j]=true;
DFS(row+1, queens, result, column_o, diag_o, anti_diag_o);
column_o[j]=diag_o[row+j]=anti_diag_o[N-1-row+j]=false;
}
}
}
};
``````