Place N queens on an N×N board so none attack another. Go row by row: try each column, keep only safe squares, recurse to the next row, and rip the queen back off the instant a row has no safe spot.
Since two queens can't share a row, place exactly one per row and only decide its column. That collapses the search from "any square" to "which column in row r", pruning huge swaths instantly.
cols[c] already usedrow + colrow − col + nvoid solve(int row, int n, vector<int>& pos,
vector<bool>& col, vector<bool>& d1,
vector<bool>& d2, vector<vector<int>>& out) {
if (row == n) { // all rows filled → a solution
out.push_back(pos);
return;
}
for (int c = 0; c < n; c++) {
int id1 = row + c, id2 = row - c + n;
if (col[c] || d1[id1] || d2[id2]) continue; // under attack → prune
pos[row] = c; // CHOOSE
col[c] = d1[id1] = d2[id2] = true;
solve(row + 1, n, pos, col, d1, d2, out); // EXPLORE
col[c] = d1[id1] = d2[id2] = false; // UNCHOOSE (backtrack)
}
}
int totalNQueens(int n) {
vector<vector<int>> out; vector<int> pos(n);
vector<bool> col(n), d1(2*n), d2(2*n);
solve(0, n, pos, col, d1, d2, out);
return out.size();
}Row r has at most N-r safe columns; pruning slashes the raw Nᴺ.
Position array plus three boolean attack arrays.
N=4→2, N=6→4, N=8→92 distinct boards.
row+col; every ↙ shares row-col. Offset by n to keep the index non-negative.