Classic Backtracking Problem (N-Queens)

The N-Queens problem asks whether it is possible to place N queens on an N × N chessboard such that no two queens attack each other.

This is one of the most famous backtracking problems and a perfect demonstration of constraint checking, pruning, and recursive exploration.

Problem Statement

Place N queens on an N × N board such that:

• No two queens share the same row
• No two queens share the same column
• No two queens share the same diagonal

Return all valid board configurations.

Example (N = 4)

One valid solution:

. Q . .
. . . Q
Q . . .
. . Q .

Another:

. . Q .
Q . . .
. . . Q
. Q . .

So for N = 4, there are 2 solutions.

Why Backtracking Is Ideal

At each row:

• You try placing a queen in each column
• You check constraints
• If invalid → stop exploring that branch
• If valid → recurse to the next row

This avoids exploring impossible board states.

Backtracking Strategy

State

• row → current row to place a queen
• cols → occupied columns
• diag1 → occupied main diagonals (row - col)
• diag2 → occupied anti-diagonals (row + col)
• board → current board configuration

Key Insight: Diagonal Indexing

For a cell (row, col):

• Main diagonal: row - col
• Anti-diagonal: row + col

These uniquely identify diagonals.

Backtracking Template (N-Queens)

backtrack(row):
    if row == n:
        record solution
        return

    for col in 0..n:
        if column or diagonal is occupied:
            continue

        place queen
        backtrack(row + 1)
        remove queen

Rust Implementation

pub fn solve_n_queens(n: usize) -> Vec<Vec<String>> {
    let mut results = Vec::new();
    let mut board = vec![vec!['.'; n]; n];

    let mut cols = vec![false; n];
    let mut diag1 = vec![false; 2 * n]; // row - col + n
    let mut diag2 = vec![false; 2 * n]; // row + col

    backtrack(
        0,
        n,
        &mut board,
        &mut cols,
        &mut diag1,
        &mut diag2,
        &mut results,
    );

    results
}

fn backtrack(
    row: usize,
    n: usize,
    board: &mut Vec<Vec<char>>,
    cols: &mut Vec<bool>,
    diag1: &mut Vec<bool>,
    diag2: &mut Vec<bool>,
    results: &mut Vec<Vec<String>>,
) {
    if row == n {
        let solution = board
            .iter()
            .map(|r| r.iter().collect())
            .collect();
        results.push(solution);
        return;
    }

    for col in 0..n {
        let d1 = row + n - col;
        let d2 = row + col;

        if cols[col] || diag1[d1] || diag2[d2] {
            continue;
        }

        // place queen
        board[row][col] = 'Q';
        cols[col] = true;
        diag1[d1] = true;
        diag2[d2] = true;

        backtrack(row + 1, n, board, cols, diag1, diag2, results);

        // undo
        board[row][col] = '.';
        cols[col] = false;
        diag1[d1] = false;
        diag2[d2] = false;
    }
}

Example Usage

fn main() {
    let solutions = solve_n_queens(4);

    for (i, board) in solutions.iter().enumerate() {
        println!("Solution {}", i + 1);
        for row in board {
            println!("{}", row);
        }
        println!();
    }
}

Time and Space Complexity

Time Complexity

• Worst-case: O(N!)
• Pruning dramatically reduces actual search space

Space Complexity

Why N-Queens Is Important

N-Queens teaches:

• Constraint modeling
• Efficient pruning
• Diagonal indexing tricks
• How exponential problems are made tractable

It is a canonical interview and algorithm problem.

Common Mistakes

• Forgetting diagonal constraints
• Using O(N²) checks instead of O(1)
• Not undoing state correctly
• Confusing rows and columns

Summary

• N-Queens is a classic backtracking problem
• One queen per row simplifies constraints
• Columns and diagonals are tracked efficiently
• Demonstrates real power of backtracking

Playground Links

Rust Classic Backtracking Problem (N-Queens)