N-Queens Problem - Learning Module

Loading content...

0/276

Placing Queens Safely

The Mechanics of Safe Queen Placement

Now that we understand the N-Queens problem conceptually, it's time to dive into the mechanics of placement. How do we represent the board state? How do we generate candidate moves? How do we systematically explore possibilities while maintaining the ability to backtrack?

This page transforms conceptual understanding into implementable algorithms. We'll build the machinery that powers the backtracking search, piece by piece.

What You Will Learn

You'll master state representation strategies, understand the choose-explore-unchoose pattern in the N-Queens context, and learn how to generate valid candidate moves efficiently. By the end, you'll be ready to implement a complete N-Queens solver.

State Representation Strategies

The first crucial decision in any backtracking algorithm is how to represent state. For N-Queens, we have several options, each with tradeoffs in simplicity, space efficiency, and constraint-checking speed.

The Obvious Choice: Full Board Representation

The most intuitive representation is a 2D array where each cell indicates whether a queen is present:

const board: boolean[][] = Array(n).fill(null).map(() => Array(n).fill(false));

// Place queen at row r, column c
board[r][c] = true;

// Check if position has a queen
if (board[r][c]) { ... }

Pros:

Intuitive mapping to the visual board
Easy to print/debug
Works for any variant (including pre-placed queens)

Cons:

O(N²) space
Checking row/column/diagonal conflicts requires O(N) scans
Unnecessary storage since each row has exactly one queen

Recommendation

For interviews and learning, use the 1D array representation. It's efficient, easy to explain, and demonstrates understanding without premature optimization. Use bitmasks only when N is large and performance is critical.

The Row-by-Row Approach

The standard N-Queens algorithm places queens one row at a time, starting from row 0. This approach has several compelling advantages:

Why Row-by-Row Works

•Eliminates row conflicts automatically — Since we place exactly one queen per row number, no two queens can ever share a row.
•Natural recursive structure — The subproblem is 'place queens in rows r through N-1, given placements in rows 0 through r-1'.
•Clear termination — When we've successfully placed a queen in the last row, we have a complete solution.
•Consistent complexity — Each level of recursion has at most N choices (columns), making analysis tractable.

The Algorithm Skeleton:

solve(row):
    if row == N:
        # All queens placed successfully!
        record/return solution
    
    for each column c in 0 to N-1:
        if position (row, c) is safe:
            place queen at (row, c)
            solve(row + 1)          # Recurse to next row
            remove queen from (row, c)  # Backtrack

This skeleton captures the essence of the backtracking approach:

Base case: All rows filled → solution found
Recursive case: Try each column in current row
Choose: Place queen if safe
Explore: Recurse to next row
Unchoose: Remove queen to try other options

Converting Mermaid diagram...

Generating Candidate Moves

For each row, we need to identify which columns are valid candidates for queen placement. This is where constraint checking comes in—but for now, let's focus on the candidate generation logic.

Naive Candidate Generation:

The simplest approach generates all N columns as candidates, then filters:

function getCandidates(row: number, queens: number[]): number[] {
    const candidates: number[] = [];
    for (let col = 0; col < n; col++) {
        if (isSafe(row, col, queens)) {
            candidates.push(col);
        }
    }
    return candidates;
}

This approach is clear but performs the full safety check for every column.

Optimized Candidate Generation:

With proper data structures, we can generate only valid candidates:

// Using Sets to track occupied columns and diagonals
const usedColumns = new Set<number>();
const usedDiag1 = new Set<number>();   // r - c values
const usedDiag2 = new Set<number>();   // r + c values

function getCandidates(row: number): number[] {
    const candidates: number[] = [];
    for (let col = 0; col < n; col++) {
        const d1 = row - col;
        const d2 = row + col;
        if (!usedColumns.has(col) && 
            !usedDiag1.has(d1) && 
            !usedDiag2.has(d2)) {
            candidates.push(col);
        }
    }
    return candidates;
}

With Sets, each check is O(1), making full candidate generation O(N).

Trade-off: Inline vs Separate Candidate Generation

Some implementations skip explicit candidate generation and just loop through all columns, checking safety inline. This saves creating an intermediate array but makes the code structure slightly less clear. Both approaches are valid; choose based on clarity needs.

The Choose-Explore-Unchoose Pattern

Every backtracking algorithm follows the same fundamental pattern: choose a candidate, explore the resulting subtree, then unchoose to restore state. Let's see this pattern concretely for N-Queens.

n-queens-pattern.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
function solveNQueens(n: number): number[][] {
    const solutions: number[][] = [];
    const queens: number[] = [];               // queens[row] = column
    const usedColumns = new Set<number>();
    const usedDiag1 = new Set<number>();       // r - c
    const usedDiag2 = new Set<number>();       // r + c
 
    function backtrack(row: number): void {
        // Base case: all queens placed
        if (row === n) {
            solutions.push([...queens]);  // Store a copy
            return;
        }
 
        // Try each column in current row
        for (let col = 0; col < n; col++) {
            const d1 = row - col;
            const d2 = row + col;
 
            // Skip if column or diagonal is attacked
            if (usedColumns.has(col) || 
                usedDiag1.has(d1) || 
                usedDiag2.has(d2)) {
                continue;
            }
 
            // ===== CHOOSE =====
            queens.push(col);
            usedColumns.add(col);
            usedDiag1.add(d1);
            usedDiag2.add(d2);
 
            // ===== EXPLORE =====
            backtrack(row + 1);
 
            // ===== UNCHOOSE (Backtrack) =====
            queens.pop();
            usedColumns.delete(col);
            usedDiag1.delete(d1);
            usedDiag2.delete(d2);
        }
    }
 
    backtrack(0);
    return solutions;
}

Critical Observation:

Notice the perfect symmetry between CHOOSE and UNCHOOSE. Every operation in CHOOSE has a corresponding reversal in UNCHOOSE:

CHOOSE	UNCHOOSE
`queens.push(col)`	`queens.pop()`
`usedColumns.add(col)`	`usedColumns.delete(col)`
`usedDiag1.add(d1)`	`usedDiag1.delete(d1)`
`usedDiag2.add(d2)`	`usedDiag2.delete(d2)`

This symmetry is essential. If UNCHOOSE doesn't perfectly reverse CHOOSE, the algorithm will have bugs—either missing valid solutions or reporting invalid ones.

Common Bug Alert

A frequent mistake is forgetting to remove entries from the used_columns, used_diag1, or used_diag2 sets during backtracking. This causes valid solutions to be incorrectly skipped. Always verify that every 'add' has a corresponding 'remove'.

State Management Strategies

Managing state correctly is crucial for backtracking correctness. There are two main paradigms:

Mutable State (In-Place)

•Modify shared data structures
•Must explicitly undo changes
•More memory efficient
•Faster (no copying)
•Requires careful bookkeeping

Immutable State (Copying)

•Create new state at each step
•No explicit undo needed
•Higher memory usage
•Slower (copying overhead)
•Simpler to reason about

Mutable State Example (Preferred for N-Queens):

// State is modified in-place and restored after recursion
queens.push(col);       // Modify
backtrack(row + 1);
queens.pop();           // Restore

Immutable State Example:

// New state created at each step
const newQueens = [...queens, col];
backtrack(row + 1, newQueens);  // Pass new state
// No restoration needed - original queens unchanged

Trade-off Analysis:

For N-Queens:

Mutable state is preferred because the modification (add/remove from set/array) is O(1)
Copying arrays at each step would be O(N) per recursion level, adding O(N²) overhead
The explicit undo is mechanical and easy to get right

For problems with complex state, immutable approaches can prevent subtle bugs at the cost of performance.

Interview Recommendation

Use mutable state with explicit undo for N-Queens. It demonstrates understanding of backtracking mechanics. If asked about the trade-off, explain that immutable state would work but adds O(N²) overhead from copying.

Handling the Base Case

The base case is reached when we've successfully placed a queen in every row. At this point, we have a valid solution. What we do depends on the problem variant.

base-case-variants.ts
TypeScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
// Variant 1: Find ONE solution
function findOneSolution(n: number): number[] | null {
    let solution: number[] | null = null;
    
    function backtrack(row: number): boolean {
        if (row === n) {
            solution = [...queens];
            return true;  // Signal to stop searching
        }
        
        for (let col = 0; col < n; col++) {
            if (isSafe(row, col)) {
                place(row, col);
                if (backtrack(row + 1)) {
                    return true;  // Propagate stop signal
                }
                remove(row, col);
            }
        }
        return false;  // No solution found in this branch
    }
    
    backtrack(0);
    return solution;
}
 
// Variant 2: Find ALL solutions
function findAllSolutions(n: number): number[][] {
    const solutions: number[][] = [];
    
    function backtrack(row: number): void {
        if (row === n) {
            solutions.push([...queens]);  // Store copy, continue searching
            return;  // Don't return early - explore more
        }
        
        for (let col = 0; col < n; col++) {
            if (isSafe(row, col)) {
                place(row, col);
                backtrack(row + 1);
                remove(row, col);  // Always backtrack to find more solutions
            }
        }
    }
    
    backtrack(0);
    return solutions;
}
 
// Variant 3: COUNT solutions (don't store them)
function countSolutions(n: number): number {
    let count = 0;
    
    function backtrack(row: number): void {
        if (row === n) {
            count++;  // Just increment counter
            return;
        }
        
        for (let col = 0; col < n; col++) {
            if (isSafe(row, col)) {
                place(row, col);
                backtrack(row + 1);
                remove(row, col);
            }
        }
    }
    
    backtrack(0);
    return count;
}

Key Differences:

Variant	Base Case Action	Return Type	Early Exit?
Find one	Store and signal stop	`boolean`	Yes
Find all	Store and continue	`void`	No
Count	Increment counter	`void`	No

Important: Deep Copy Requirement

When storing solutions, you must create a copy: solutions.push([...queens]).

Why? Because queens is a mutable array that will be modified as backtracking continues. If you push the reference without copying, all entries in solutions will point to the same array, which will be empty when the algorithm completes.

Critical Bug

DO NOT write: solutions.push(queens)

DO write: solutions.push([...queens]) or solutions.push(queens.slice())

This is one of the most common backtracking bugs. The same array reference gets modified, so all 'solutions' end up identical (and usually empty).

Solution Representation

Different contexts require different output formats. Let's explore common ways to represent N-Queens solutions.

solution-formats.ts
TypeScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
// Format 1: Column array (internal representation)
// queens[row] = column
const columnFormat: number[] = [1, 3, 0, 2];
// Means: Row 0 → Col 1, Row 1 → Col 3, Row 2 → Col 0, Row 3 → Col 2
 
// Format 2: Coordinate pairs
const coordFormat: [number, number][] = [
    [0, 1], [1, 3], [2, 0], [3, 2]
];
 
// Format 3: Visual board (for display/debugging)
function toVisualBoard(queens: number[]): string[] {
    const n = queens.length;
    return queens.map(col => {
        return '.'.repeat(col) + 'Q' + '.'.repeat(n - col - 1);
    });
}
// Result for [1, 3, 0, 2]:
// [".Q..",
//  "...Q",
//  "Q...",
//  "..Q."]
 
// Format 4: LeetCode format (strings with Q and .)
function toLeetCodeFormat(queens: number[]): string[] {
    const n = queens.length;
    return queens.map(col => {
        const row = Array(n).fill('.');
        row[col] = 'Q';
        return row.join('');
    });
}
 
// Converting between formats
function columnToCoord(queens: number[]): [number, number][] {
    return queens.map((col, row) => [row, col]);
}
 
function coordToColumn(coords: [number, number][]): number[] {
    const queens: number[] = [];
    for (const [row, col] of coords.sort((a, b) => a[0] - b[0])) {
        queens[row] = col;
    }
    return queens;
}

LeetCode Note

LeetCode's N-Queens problem requires output as string[][] where each solution is an array of strings like [".Q..","...Q","Q...","..Q."]. Use the column array internally but convert for output.

Complete Implementation

Let's assemble everything into a clean, complete implementation that demonstrates best practices:

n-queens-complete.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
/**
 * N-Queens: Find all valid placements of N queens on an N×N board
 * such that no two queens attack each other.
 * 
 * Time Complexity: O(N!) in the worst case, but pruning reduces this significantly
 * Space Complexity: O(N) for recursion stack + O(N) for tracking sets
 */
function solveNQueens(n: number): string[][] {
    const solutions: string[][] = [];
    const queens: number[] = [];            // queens[row] = column
    const usedColumns = new Set<number>();
    const usedDiag1 = new Set<number>();    // r - c (main diagonal)
    const usedDiag2 = new Set<number>();    // r + c (anti-diagonal)
 
    function backtrack(row: number): void {
        // Base case: all N queens placed successfully
        if (row === n) {
            solutions.push(formatBoard(queens, n));
            return;
        }
 
        // Try each column in the current row
        for (let col = 0; col < n; col++) {
            // Calculate diagonal identifiers
            const d1 = row - col;  // Main diagonal: constant along ↘ direction
            const d2 = row + col;  // Anti-diagonal: constant along ↗ direction
 
            // Skip if any constraint is violated
            if (usedColumns.has(col) || usedDiag1.has(d1) || usedDiag2.has(d2)) {
                continue;
            }
 
            // CHOOSE: Place queen and mark constraints
            queens.push(col);
            usedColumns.add(col);
            usedDiag1.add(d1);
            usedDiag2.add(d2);
 
            // EXPLORE: Recurse to next row
            backtrack(row + 1);
 
            // UNCHOOSE: Remove queen and unmark constraints
            queens.pop();
            usedColumns.delete(col);
            usedDiag1.delete(d1);
            usedDiag2.delete(d2);
        }
    }
 
    // Convert column array to visual board format
    function formatBoard(queens: number[], n: number): string[] {
        return queens.map(col => {
            return '.'.repeat(col) + 'Q' + '.'.repeat(n - col - 1);
        });
    }
 
    backtrack(0);
    return solutions;
}
 
// Example usage and test
function test(): void {
    console.log("4-Queens Solutions:");
    const solutions = solveNQueens(4);
    solutions.forEach((solution, i) => {
        console.log(`Solution ${i + 1}:`);
        solution.forEach(row => console.log(row));
        console.log();
    });
    console.log(`Total: ${solutions.length} solutions`);
    
    // Test for N = 8
    console.log(`\n8-Queens: ${solveNQueens(8).length} solutions`);  // Should print 92
}

Summary: Placement Mechanics

We've covered the complete mechanics of placing queens safely:

Key Takeaways

•State Representation — Use 1D array queens[row] = column for optimal balance of simplicity and efficiency.
•Row-by-Row Approach — Process one row at a time, eliminating row conflicts by construction.
•Choose-Explore-Unchoose — The fundamental backtracking pattern. Every CHOOSE operation must have a matching UNCHOOSE.
•Mutable State — Prefer in-place modification with explicit undo for N-Queens performance.
•Base Case Handling — Copy solutions when storing; differentiate between find-one, find-all, and count variants.
•Hash Sets for Tracking — Use Sets for O(1) column and diagonal conflict checking.

What's Next:

With placement mechanics in place, the next page dives deep into constraint checking—the heart of the pruning that makes backtracking efficient. We'll explore the mathematics of diagonal detection and optimize our conflict detection to O(1).

Page Complete

You can now implement the core N-Queens backtracking algorithm. You understand state representation, the choose-explore-unchoose pattern, and how to handle different problem variants. Next, we'll optimize constraint checking for maximum efficiency.