# [leetcode] N-Queens

### N-Queens

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.."]
]```

tag: backtracking

```class Solution {
public:
//I try to fill the board row by row
vector<vector<string> > solveNQueens(int n) {
vector<vector<bool> > board(n, vector<bool>(n, false));//false means empty; true means occupied by a queen
vector<vector<string>> re;
if(n == 0){
return re;
}
//fill the first row
for(int j = 0; j < n; j++){
board[0][j] = true;
_solveQueens(1, board, re);
board[0][j] = false;
}
return re;
}
void _solveQueens(int row, vector<vector<bool> > &board, vector<vector<string> > &re){
int size = board.size();
if(row == size){//finish
re.push_back(generateResult(board));
return;
}

//not finish
for(int j = 0; j < size; j++){
board[row][j] = true;
if(checkBoard(board, row, j) == true){//leagal
_solveQueens(row + 1, board, re);
}
board[row][j] = false;
}
}

vector<string> generateResult(vector<vector<bool> > &board){
vector<string> strs;
string s;
for(int i = 0; i < board.size(); i++){
for(int j = 0; j < board.size(); j++){
char c = board[i][j] == true?'Q': '.';
s.push_back(c);
}
strs.push_back(s);
s.clear();
}
return strs;
}
bool checkBoard(vector<vector<bool> > &board, int row, int column){
int size = board.size();
for(int k = 0; k < size; k++){
//check row
if(board[row][k] == true && k != column){
return false;
}
//check column
if(board[k][column] == true && k != row){
return false;
}
//check diagonal
int r0 = row - k;
int c0 = column - k;
int c1 = column + k;
bool flag = false;
if(r0 >= 0 && c0 >= 0){
flag |= board[r0][c0];
}
if(r0 >= 0 && c1 < size){
flag |= board[r0][c1];
}
//no need to check below part of the board
if(flag == true && k != 0){
return false;
}
}
return true;
}
};```

This site uses Akismet to reduce spam. Learn how your comment data is processed.