Coding Exercise: N-Queens Problem Using Backtracking

Place N queens on NxN chessboard so no two queens attack each other.

Rules: No two queens in same row, column, or diagonal.

Example: N=4 has 2 solutions.

Problem Statement

Input: Integer N (board size, 1 ≤ N ≤ 12)

Output: All valid configurations

Constraint: No queen attacks another

Backtracking Strategy

1. Place queen in current row

2. Check if safe (no attacks)

3. If safe → recurse next row

4. If conflict → backtrack (try next column)

Complete N-Queens Solution

              
            
C++

          N-Queens backtracking implementation
        
#include <iostream>
#include <vector>
using namespace std;

bool isSafe(int row, int col, vector<int>& pos) {
    for (int prev = 0; prev < row; prev++) {
        if (pos[prev] == col ||  // same column
            pos[prev] - prev == col - row ||  // diagonal /
            pos[prev] + prev == col + row) {  // diagonal \
            return false;
        }
    }
    return true;
}

void solveNQueens(int row, int n, vector<int>& pos, int& count) {
    if (row == n) {
        count++;
        cout << "Solution " << count << ": ";
        for (int c : pos) cout << c << " ";
        cout << endl;
        return;
    }
    
    for (int col = 0; col < n; col++) {
        if (isSafe(row, col, pos)) {
            pos[row] = col;
            solveNQueens(row + 1, n, pos, count);
        }
    }
}

int main() {
    int n = 4;
    vector<int> pos(n, -1);
    int count = 0;
    
    solveNQueens(0, n, pos, count);
    cout << "Total solutions: " << count << endl;
    return 0;
}

Sample Output (N=4)

              
TEXT

          4-Queens solutions
        
Solution 1: 1 3 0 2
Solution 2: 2 0 3 1
Total solutions: 2

Board visualization: Q = Queen, . = Empty

Test Cases

              
TEXT

          Solutions count
        
N=1 → 1 solution
N=4 → 2 solutions
N=8 → 92 solutions

Complexity

Time: O(N!) - backtracking tree

Space: O(N) - recursion stack + board

Practice Variations

1. Print board visually (2D array)

2. N-Rooks problem

3. Sudoku solver (similar backtracking)

Conclusion

Mastered backtracking! N-Queens = classic interview problem.

Next: Graph DFS or subset sum.