# A standard backtracing solution

• ``````struct location{
int row;
int col;
location(int r, int c): row(r), col(c) {}
};

// recursive backtracking solution
vector<vector<string> > solveNQueens(int n) {
vector<vector<string> > ans;
vector<string> board(n, string(n, '.'));
vector<location> placed;

// row "0" try all the possibilities
for (int j = 0; j < n; j++) {
board[0][j] = 'Q';
placed.push_back(location(0, j));
solveNQueens(1, placed, board, ans);
placed.pop_back();
board[0][j] = '.';
}

return ans;
}

void solveNQueens(int r, vector<location> &placed, vector<string> &board, vector<vector<string> > &ans) {
if (r == board.size()) {
ans.push_back(board);
return;
}

// row "r" try all the possibilities
for (int j = 0; j < board.size(); j++) {
// first check whether location (r, j) is valid or not
bool conflict = false;
for (int i = 0; i < placed.size(); i++) {
//check whether the column or the diagonal line is used
if(placed[i].col == j || abs(placed[i].row - r) == abs(placed[i].col - j)) {
conflict = true;
break;
}
}

if(conflict) continue;

board[r][j] = 'Q';
placed.push_back(location(r, j));
solveNQueens(r + 1, placed, board, ans);
placed.pop_back();
board[r][j] = '.';
}
}``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.