The N-Queens problem places N queens on an N×N chessboard such that no two queens share the same row, column, or diagonal. Backtracking tries placing a queen in each column of the current row; if a conflict is detected the placement is undone and the next column is tried. All solutions can be found by continuing after each valid placement.
bool isSafe(vector<int>& board, int row, int col) {
for(int i=0;i<row;i++)
if(board[i]==col || abs(board[i]-col)==abs(i-row)) return false;
return true;
}
void solve(int n, int row, vector<int>& board, vector<vector<int>>& res){
if(row==n){res.push_back(board);return;}
for(int col=0;col<n;col++)
if(isSafe(board,row,col)){board[row]=col;solve(n,row+1,board,res);board[row]=-1;}
}Try placing a queen in each column of the current row. Check if it is safe (no conflict with existing queens). If safe, recurse to the next row. If the recursion fails, undo the placement (backtrack) and try the next column.
A queen at (row, col) conflicts with a queen at (i, board[i]) if: same column (board[i]==col) or same diagonal (|board[i]-col| == |i-row|). Row conflicts are impossible since we place one per row.
We prune immediately when a conflict is detected, avoiding entire subtrees. For N=8, the naive search space is 8^8 ≈ 16M but backtracking finds all 92 solutions examining only thousands of states.
Quiz coming soon for this algorithm.