Data Structures & AlgorithmsN-Queens Problem

N-Queens Problem — The Classic Backtracking Challenge

LevelIntermediate

Duration75 mins

TopicN-Queens Problem

4 / 4

Counting vs Finding All Solutions

Different Goals, Different Algorithms

Not all N-Queens problems are created equal. Sometimes you need one solution. Sometimes you need all solutions. Sometimes you just want to count them. Each objective has different algorithmic implications—and understanding these differences is crucial for choosing the right approach.

This final page explores these variations, their tradeoffs, and how to adapt your backtracking solution for each scenario. We'll also examine practical applications and performance considerations.

What You Will Master

You'll understand when to use each variant of the N-Queens algorithm, how to optimize for specific objectives, the space-time tradeoffs involved, and how these decisions apply to real-world constraint satisfaction problems.

The Three Objectives

N-Queens problems typically fall into three categories, each requiring a different algorithmic approach:

N-Queens Problem Variations
Objective	Question Answered	Output	Use Case
Find One	Does a solution exist? What is it?	Single solution or null	Existence proof, game starting positions
Find All	What are all valid configurations?	List of all solutions	Complete enumeration, analysis, visualization
Count	How many solutions exist?	Integer count	Mathematical analysis, validation, benchmarking

Why the Distinction Matters:

Early Termination — Find-one can stop immediately upon finding a solution; the others must continue.
Space Requirements — Find-all must store all solutions (potentially millions); counting uses constant extra space.
Optimization Opportunities — Different objectives enable different pruning strategies and algorithmic approaches.
Complexity — Find-one can be O(N) in practice with good heuristics; find-all/count are inherently exponential in the number of solutions.

Interview Context

Interviewers often start with 'find one solution', then ask 'what about all solutions?' as a follow-up. Being able to adapt your algorithm demonstrates deep understanding of backtracking mechanics.

Finding One Solution

The simplest objective is finding any valid solution. As soon as we place N queens successfully, we return.

find-one-solution.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
/**
 * Find ONE valid N-Queens solution
 * Returns immediately upon finding a solution
 * 
 * Time: O(N!) worst case, but typically much faster
 * Space: O(N) for recursion + constraint tracking
 */
function findOneSolution(n: number): number[] | null {
    const queens: number[] = [];
    const usedColumns = new Set<number>();
    const usedDiag1 = new Set<number>();
    const usedDiag2 = new Set<number>();
 
    function backtrack(row: number): boolean {
        // Base case: all queens placed - SUCCESS!
        if (row === n) {
            return true;  // Signal success up the call stack
        }
 
        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)) {
                continue;
            }
 
            // Place queen
            queens.push(col);
            usedColumns.add(col);
            usedDiag1.add(d1);
            usedDiag2.add(d2);
 
            // Recurse - if successful, propagate success
            if (backtrack(row + 1)) {
                return true;  // DON'T backtrack - keep the solution
            }
 
            // Backtrack - this path didn't work
            queens.pop();
            usedColumns.delete(col);
            usedDiag1.delete(d1);
            usedDiag2.delete(d2);
        }
 
        return false;  // No valid placement found
    }
 
    const found = backtrack(0);
    return found ? queens : null;
}
 
// Usage
const solution = findOneSolution(8);
if (solution) {
    console.log("Found solution:", solution);
    // e.g., [0, 4, 7, 5, 2, 6, 1, 3]
} else {
    console.log("No solution exists");
}

Key Differences from Find-All:

Return type is boolean — Signals success/failure up the call stack
Early exit on success — When base case is reached, return true without backtracking
Propagate success — if (backtrack()) return true short-circuits the search
Don't undo on success — Keep the solution in queens when returning true
Caller receives solution — No need for a separate solutions array

Existence Guaranteed for N ≥ 4

For N ≥ 4, a solution always exists. For N = 2 and N = 3, no solution exists (you can verify this). For N = 1, the trivial solution is placing the queen anywhere.

Finding All Solutions

Finding all solutions requires exhaustively searching the entire state space. Even after finding a valid placement, we backtrack to explore other possibilities.

find-all-solutions.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
/**
 * Find ALL valid N-Queens solutions
 * Continues searching after each solution found
 * 
 * Time: O(N! * N) - must visit all valid placements, O(N) to copy each
 * Space: O(N) recursion + O(S * N) for S solutions
 */
function findAllSolutions(n: number): number[][] {
    const solutions: number[][] = [];  // Store all solutions
    const queens: number[] = [];
    const usedColumns = new Set<number>();
    const usedDiag1 = new Set<number>();
    const usedDiag2 = new Set<number>();
 
    function backtrack(row: number): void {
        // Base case: all queens placed - record and continue
        if (row === n) {
            solutions.push([...queens]);  // COPY! Not reference
            return;  // Return to continue exploring
        }
 
        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)) {
                continue;
            }
 
            // Place queen
            queens.push(col);
            usedColumns.add(col);
            usedDiag1.add(d1);
            usedDiag2.add(d2);
 
            // Recurse
            backtrack(row + 1);
 
            // ALWAYS backtrack - we want to find more solutions
            queens.pop();
            usedColumns.delete(col);
            usedDiag1.delete(d1);
            usedDiag2.delete(d2);
        }
    }
 
    backtrack(0);
    return solutions;
}
 
// Usage
const allSolutions = findAllSolutions(8);
console.log(`Found ${allSolutions.length} solutions`);  // 92
 
// Print first few solutions
allSolutions.slice(0, 3).forEach((sol, i) => {
    console.log(`Solution ${i + 1}: [${sol.join(', ')}]`);
});

Key Differences from Find-One:

Return type is void — No need to propagate success; we always continue
No early exit — After recording a solution, we return but don't stop the search
Always backtrack — Even after base case, we undo moves to explore alternatives
Copy solutions — solutions.push([...queens]) creates a copy; otherwise all entries would reference the same (eventually empty) array
Collect in array — Results accumulate in solutions array

Memory Considerations

For large N, storing all solutions can consume significant memory. N=14 has 365,596 solutions, each requiring N integers. At N=17 (~95 million solutions), memory becomes a serious concern.

For very large N, consider streaming solutions (process each as found) rather than storing them all.

Counting Solutions

Sometimes we only need to know how many solutions exist, not what they are. This allows for a simpler algorithm with minimal memory usage.

count-solutions.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
/**
 * COUNT the number of valid N-Queens solutions
 * Only tracks count, doesn't store solutions
 * 
 * Time: O(N!) - must visit all valid placements
 * Space: O(N) - only recursion stack and constraint sets
 */
function countSolutions(n: number): number {
    let count = 0;  // Just a counter!
    const usedColumns = new Set<number>();
    const usedDiag1 = new Set<number>();
    const usedDiag2 = new Set<number>();
 
    function backtrack(row: number): void {
        if (row === n) {
            count++;  // Increment counter
            return;   // No storage needed
        }
 
        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)) {
                continue;
            }
 
            usedColumns.add(col);
            usedDiag1.add(d1);
            usedDiag2.add(d2);
 
            backtrack(row + 1);
 
            usedColumns.delete(col);
            usedDiag1.delete(d1);
            usedDiag2.delete(d2);
        }
    }
 
    backtrack(0);
    return count;
}
 
// Usage
console.log(`8-Queens: ${countSolutions(8)} solutions`);   // 92
console.log(`10-Queens: ${countSolutions(10)} solutions`); // 724
console.log(`12-Queens: ${countSolutions(12)} solutions`); // 14200

Advantages of Counting:

Minimal Memory — O(N) space regardless of solution count
Simpler Code — No array management or copying
Faster in Practice — No allocation overhead per solution
Scales Better — Can count solutions for larger N

Python Closure Note:

In Python, count += 1 inside a nested function would create a local variable. Using count = [0] and count[0] += 1 or the nonlocal keyword solves this:

def count_solutions(n):
    count = 0
    
    def backtrack(row):
        nonlocal count
        if row == n:
            count += 1
            return
        # ...

Alternative: Return Value

Another clean approach returns the count:

def backtrack(row):
    if row == n:
        return 1
    
    total = 0
    for col in range(n):
        if is_safe(row, col):
            place(row, col)
            total += backtrack(row + 1)
            remove(row, col)
    return total

Performance Comparison

Let's analyze the practical performance differences between the three approaches:

Time Complexity Comparison
Objective	Best Case	Worst Case	Typical for N=8
Find One	O(N)	O(N!)	~50 nodes (first solution)
Find All	O(N! × N)	O(N! × N)	~2000 nodes, 92 solutions
Count	O(N!)	O(N!)	~2000 nodes, count = 92

Space Complexity Comparison
Objective	Recursion	Constraints	Solutions	Total
Find One	O(N)	O(N)	O(N)	O(N)
Find All	O(N)	O(N)	O(S × N)	O(S × N)
Count	O(N)	O(N)	O(1)	O(N)

Key Observations:

Find-One is fastest — Can terminate very early. For 8-Queens, the first solution is typically found within 50 nodes.
Find-All and Count visit same nodes — They must both explore the entire search tree, but Find-All has additional copy overhead.
Space matters at scale — For N=14 (365,596 solutions), Find-All needs ~4MB just for solutions. Count needs almost nothing extra.
Copy overhead adds up — Creating N-element arrays 365,596 times isn't free. Count avoids this entirely.

Benchmarking Results (N=12, Typical Machine)

Find-One: ~0.1ms | Find-All: ~50ms (14,200 solutions) | Count: ~30ms

The 40% speedup of Count over Find-All comes from eliminating array copies and allocations.

Streaming Solutions

For very large N, storing all solutions is impractical. A streaming approach processes each solution as it's found, using constant extra space:

streaming-solutions.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
75
76
77
78
/**
 * Stream N-Queens solutions with a callback
 * Processes each solution without storing all
 * 
 * @param n Board size
 * @param callback Function called for each solution
 * @returns Number of solutions found
 */
function streamSolutions(
    n: number, 
    callback: (solution: readonly number[]) => void
): number {
    let count = 0;
    const queens: number[] = [];
    const usedColumns = new Set<number>();
    const usedDiag1 = new Set<number>();
    const usedDiag2 = new Set<number>();
 
    function backtrack(row: number): void {
        if (row === n) {
            count++;
            callback(queens);  // Process solution immediately
            return;
        }
 
        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)) {
                continue;
            }
 
            queens.push(col);
            usedColumns.add(col);
            usedDiag1.add(d1);
            usedDiag2.add(d2);
 
            backtrack(row + 1);
 
            queens.pop();
            usedColumns.delete(col);
            usedDiag1.delete(d1);
            usedDiag2.delete(d2);
        }
    }
 
    backtrack(0);
    return count;
}
 
// Usage examples:
 
// 1. Print each solution
streamSolutions(4, (sol) => {
    console.log(`Found: [${sol.join(', ')}]`);
});
 
// 2. Find solutions with specific property
const symmetricSolutions: number[][] = [];
streamSolutions(8, (sol) => {
    if (isPalindromic(sol)) {
        symmetricSolutions.push([...sol]);
    }
});
 
// 3. Write solutions to file (pseudo-code)
// streamSolutions(12, (sol) => {
//     fs.appendFileSync('solutions.txt', sol.join(',') + '\n');
// });
 
function isPalindromic(sol: readonly number[]): boolean {
    const n = sol.length;
    for (let i = 0; i < n / 2; i++) {
        if (sol[i] !== n - 1 - sol[n - 1 - i]) return false;
    }
    return true;
}

Benefits of Streaming

•Constant memory — Only stores current partial solution, not all solutions
•Immediate processing — Handle solutions as found, no wait for completion
•Flexible filtering — Only store solutions meeting criteria
•Cancellation — Can stop early (with modification to check return value)
•I/O interleaving — Write to file/network as solutions are found

Callback Receives Live Reference

The callback receives the actual queens array, which will be modified as backtracking continues. If you need to store the solution, copy it: solutions.push([...sol]) or solutions.push(sol.slice())

Practical Applications

While N-Queens is often treated as a puzzle, the patterns and techniques extend to real-world problems:

Real-World Applications

•Constraint Satisfaction Problems (CSP) — Scheduling, resource allocation, timetabling all follow similar patterns. The backtracking template applies directly.
•VLSI Circuit Design — Placing components on chip without interference mirrors queen placement without attack.
•Task Scheduling — Finding valid task assignments given constraints (resource conflicts, dependencies).
•Graph Coloring — Coloring vertices so no adjacent vertices share a color is structurally similar.
•Sudoku and Puzzle Solving — Same backtracking template with different constraints.
•Compiler Register Allocation — Assigning variables to registers without conflict.
•Test Case Generation — Generating valid test inputs satisfying multiple constraints.

When Each Variant Applies:

Find One	Find All	Count
Need any valid schedule	Enumerate all possibilities for user to choose	Validate algorithm correctness
Game starting position	Generate test suites	Estimate problem difficulty
Prove solvability	Analysis and visualization	Benchmark solvers
Resource allocation	Configuration enumeration	Mathematical research

Interview Connection

When asked to solve N-Queens, clarify which variant is needed. Then explain: 'The core backtracking is the same, but the base case handling differs. For find-one, I return immediately on success. For find-all, I store and continue. For count, I just increment a counter.'

Optimization Trade-offs

Different objectives allow different optimizations. Understanding these trade-offs helps you choose the right approach:

Optimization Applicability by Objective
Optimization	Find One	Find All	Count
Early termination	✓ Essential	✗ Not applicable	✗ Not applicable
Symmetry breaking (halve search)	✓ For speed	✗ Would miss solutions	✓ Count half, multiply by 2
Heuristic column ordering	✓ Very effective	✗ Changes discovery order only	✗ No benefit
Parallel search	⚠ More complex	✓ Divide-and-conquer	✓ Sum partial counts
Bitwise operations	✓ Best performance	✓ Best performance	✓ Best performance
Forward checking	✓ Worth overhead	⚠ May not pay off	⚠ May not pay off

Heuristics for Find-One:

When finding just one solution, column ordering can dramatically speed up search:

// Start from the middle columns - more likely to lead to solutions
function getColumnOrder(n: number): number[] {
    const order: number[] = [];
    const mid = Math.floor(n / 2);
    
    for (let offset = 0; offset <= mid; offset++) {
        if (mid + offset < n) order.push(mid + offset);
        if (offset > 0 && mid - offset >= 0) order.push(mid - offset);
    }
    
    return order;
    // For n=8: [4, 3, 5, 2, 6, 1, 7, 0] instead of [0, 1, 2, ..., 7]
}

This heuristic can reduce nodes visited by 50-80% for find-one!

Parallel N-Queens

For find-all/count on multi-core systems, parallelize by first-row choices: spawn N threads, each exploring subtrees rooted at different column choices for row 0. Sum counts or merge solution lists at the end.

LeetCode and Interview Format

The N-Queens problem appears on LeetCode and in interviews with specific format requirements. Here's the complete solution in LeetCode format:

leetcode-nqueens.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
75
76
77
78
79
80
81
82
83
84
85
86
87
/**
 * LeetCode 51: N-Queens
 * Return all distinct solutions to the n-queens puzzle.
 * Each solution contains a distinct board configuration where
 * 'Q' indicates a queen and '.' indicates an empty space.
 */
function solveNQueens(n: number): string[][] {
    const solutions: string[][] = [];
    const queens: number[] = [];
    const usedColumns = new Set<number>();
    const usedDiag1 = new Set<number>();
    const usedDiag2 = new Set<number>();
 
    function backtrack(row: number): void {
        if (row === n) {
            // Convert column array to string board format
            solutions.push(queens.map(col => 
                '.'.repeat(col) + 'Q' + '.'.repeat(n - col - 1)
            ));
            return;
        }
 
        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)) {
                continue;
            }
 
            queens.push(col);
            usedColumns.add(col);
            usedDiag1.add(d1);
            usedDiag2.add(d2);
 
            backtrack(row + 1);
 
            queens.pop();
            usedColumns.delete(col);
            usedDiag1.delete(d1);
            usedDiag2.delete(d2);
        }
    }
 
    backtrack(0);
    return solutions;
}
 
/**
 * LeetCode 52: N-Queens II
 * Return the number of distinct solutions to the n-queens puzzle.
 */
function totalNQueens(n: number): number {
    let count = 0;
    const usedColumns = new Set<number>();
    const usedDiag1 = new Set<number>();
    const usedDiag2 = new Set<number>();
 
    function backtrack(row: number): void {
        if (row === n) {
            count++;
            return;
        }
 
        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)) {
                continue;
            }
 
            usedColumns.add(col);
            usedDiag1.add(d1);
            usedDiag2.add(d2);
 
            backtrack(row + 1);
 
            usedColumns.delete(col);
            usedDiag1.delete(d1);
            usedDiag2.delete(d2);
        }
    }
 
    backtrack(0);
    return count;
}

Interview Tips

Clarify the variant — Ask if they want one solution, all solutions, or just the count.
Start simple — Explain the approach before coding.
Optimize progressively — Start with O(N) checking, then mention O(1) optimization.
Discuss trade-offs — Explain space for sets vs time for linear search.
Handle edge cases — N=1 (trivial), N=2,3 (no solution), N≥4 (solutions exist).

Module Summary: N-Queens Mastery

Congratulations! You've mastered the N-Queens problem—the quintessential backtracking challenge. Let's consolidate everything you've learned:

Module Takeaways

•The Problem — Place N queens on an N×N board with no mutual attacks. The classic demonstration of backtracking.
•Why Backtracking — Incremental construction, early constraint detection, reversible state, and exhaustive coverage make it ideal.
•State Representation — Use queens[row] = column for simplicity and efficiency. Sets track occupied columns and diagonals.
•Diagonal Mathematics — Main diagonal: r-c constant. Anti-diagonal: r+c constant. This enables O(1) conflict checking.
•Choose-Explore-Unchoose — The universal backtracking pattern. Every 'choose' must have a matching 'unchoose'.
•Three Variants — Find-one (early exit), find-all (store and continue), count (increment only). Same core, different handling.
•Optimization Options — Bitwise operations, forward checking, symmetry breaking—apply based on N and objective.
•Practical Patterns — N-Queens techniques apply to CSP, scheduling, VLSI design, and countless other constraint problems.

Quick Reference: N-Queens Variants
Variant	Return Type	Base Case	Key Code
Find One	boolean	return true	if (backtrack()) return true
Find All	void	solutions.push([...queens])	Always backtrack after base case
Count	void	count++	Increment counter, no storage

Moving Forward:

The N-Queens pattern—choosing, constraining, exploring, and undoing—is the template for all backtracking problems. Whether you're solving Sudoku, generating permutations, or finding graph colorings, the structure remains the same.

The next modules will apply these patterns to Sudoku solving, constraint satisfaction frameworks, and more complex backtracking scenarios. The foundation you've built here will serve you well.

Module Complete!

You've conquered the N-Queens problem! You can now solve it efficiently, explain the mathematics behind diagonal detection, adapt to different objectives, and apply the patterns to real-world constraint satisfaction problems. This is backtracking mastery.

4 / 4

Loading learning content...

Data Structures & AlgorithmsN-Queens Problem

N-Queens Problem — The Classic Backtracking Challenge

LevelIntermediate

Duration75 mins

TopicN-Queens Problem

4 / 4

Counting vs Finding All Solutions

Different Goals, Different Algorithms

This final page explores these variations, their tradeoffs, and how to adapt your backtracking solution for each scenario. We'll also examine practical applications and performance considerations.

What You Will Master

The Three Objectives

N-Queens problems typically fall into three categories, each requiring a different algorithmic approach:

N-Queens Problem Variations
Objective	Question Answered	Output	Use Case
Find One	Does a solution exist? What is it?	Single solution or null	Existence proof, game starting positions
Find All	What are all valid configurations?	List of all solutions	Complete enumeration, analysis, visualization
Count	How many solutions exist?	Integer count	Mathematical analysis, validation, benchmarking

Why the Distinction Matters:

Early Termination — Find-one can stop immediately upon finding a solution; the others must continue.
Space Requirements — Find-all must store all solutions (potentially millions); counting uses constant extra space.
Optimization Opportunities — Different objectives enable different pruning strategies and algorithmic approaches.
Complexity — Find-one can be O(N) in practice with good heuristics; find-all/count are inherently exponential in the number of solutions.

Interview Context

Interviewers often start with 'find one solution', then ask 'what about all solutions?' as a follow-up. Being able to adapt your algorithm demonstrates deep understanding of backtracking mechanics.

Finding One Solution

The simplest objective is finding any valid solution. As soon as we place N queens successfully, we return.

find-one-solution.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
/**
 * Find ONE valid N-Queens solution
 * Returns immediately upon finding a solution
 * 
 * Time: O(N!) worst case, but typically much faster
 * Space: O(N) for recursion + constraint tracking
 */
function findOneSolution(n: number): number[] | null {
    const queens: number[] = [];
    const usedColumns = new Set<number>();
    const usedDiag1 = new Set<number>();
    const usedDiag2 = new Set<number>();
 
    function backtrack(row: number): boolean {
        // Base case: all queens placed - SUCCESS!
        if (row === n) {
            return true;  // Signal success up the call stack
        }
 
        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)) {
                continue;
            }
 
            // Place queen
            queens.push(col);
            usedColumns.add(col);
            usedDiag1.add(d1);
            usedDiag2.add(d2);
 
            // Recurse - if successful, propagate success
            if (backtrack(row + 1)) {
                return true;  // DON'T backtrack - keep the solution
            }
 
            // Backtrack - this path didn't work
            queens.pop();
            usedColumns.delete(col);
            usedDiag1.delete(d1);
            usedDiag2.delete(d2);
        }
 
        return false;  // No valid placement found
    }
 
    const found = backtrack(0);
    return found ? queens : null;
}
 
// Usage
const solution = findOneSolution(8);
if (solution) {
    console.log("Found solution:", solution);
    // e.g., [0, 4, 7, 5, 2, 6, 1, 3]
} else {
    console.log("No solution exists");
}

Key Differences from Find-All:

Return type is boolean — Signals success/failure up the call stack
Early exit on success — When base case is reached, return true without backtracking
Propagate success — if (backtrack()) return true short-circuits the search
Don't undo on success — Keep the solution in queens when returning true
Caller receives solution — No need for a separate solutions array

Existence Guaranteed for N ≥ 4

For N ≥ 4, a solution always exists. For N = 2 and N = 3, no solution exists (you can verify this). For N = 1, the trivial solution is placing the queen anywhere.

Finding All Solutions

Finding all solutions requires exhaustively searching the entire state space. Even after finding a valid placement, we backtrack to explore other possibilities.

find-all-solutions.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
/**
 * Find ALL valid N-Queens solutions
 * Continues searching after each solution found
 * 
 * Time: O(N! * N) - must visit all valid placements, O(N) to copy each
 * Space: O(N) recursion + O(S * N) for S solutions
 */
function findAllSolutions(n: number): number[][] {
    const solutions: number[][] = [];  // Store all solutions
    const queens: number[] = [];
    const usedColumns = new Set<number>();
    const usedDiag1 = new Set<number>();
    const usedDiag2 = new Set<number>();
 
    function backtrack(row: number): void {
        // Base case: all queens placed - record and continue
        if (row === n) {
            solutions.push([...queens]);  // COPY! Not reference
            return;  // Return to continue exploring
        }
 
        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)) {
                continue;
            }
 
            // Place queen
            queens.push(col);
            usedColumns.add(col);
            usedDiag1.add(d1);
            usedDiag2.add(d2);
 
            // Recurse
            backtrack(row + 1);
 
            // ALWAYS backtrack - we want to find more solutions
            queens.pop();
            usedColumns.delete(col);
            usedDiag1.delete(d1);
            usedDiag2.delete(d2);
        }
    }
 
    backtrack(0);
    return solutions;
}
 
// Usage
const allSolutions = findAllSolutions(8);
console.log(`Found ${allSolutions.length} solutions`);  // 92
 
// Print first few solutions
allSolutions.slice(0, 3).forEach((sol, i) => {
    console.log(`Solution ${i + 1}: [${sol.join(', ')}]`);
});

Key Differences from Find-One:

Return type is void — No need to propagate success; we always continue
No early exit — After recording a solution, we return but don't stop the search
Always backtrack — Even after base case, we undo moves to explore alternatives
Copy solutions — solutions.push([...queens]) creates a copy; otherwise all entries would reference the same (eventually empty) array
Collect in array — Results accumulate in solutions array

Memory Considerations

For large N, storing all solutions can consume significant memory. N=14 has 365,596 solutions, each requiring N integers. At N=17 (~95 million solutions), memory becomes a serious concern.

For very large N, consider streaming solutions (process each as found) rather than storing them all.

Counting Solutions

Sometimes we only need to know how many solutions exist, not what they are. This allows for a simpler algorithm with minimal memory usage.

count-solutions.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
/**
 * COUNT the number of valid N-Queens solutions
 * Only tracks count, doesn't store solutions
 * 
 * Time: O(N!) - must visit all valid placements
 * Space: O(N) - only recursion stack and constraint sets
 */
function countSolutions(n: number): number {
    let count = 0;  // Just a counter!
    const usedColumns = new Set<number>();
    const usedDiag1 = new Set<number>();
    const usedDiag2 = new Set<number>();
 
    function backtrack(row: number): void {
        if (row === n) {
            count++;  // Increment counter
            return;   // No storage needed
        }
 
        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)) {
                continue;
            }
 
            usedColumns.add(col);
            usedDiag1.add(d1);
            usedDiag2.add(d2);
 
            backtrack(row + 1);
 
            usedColumns.delete(col);
            usedDiag1.delete(d1);
            usedDiag2.delete(d2);
        }
    }
 
    backtrack(0);
    return count;
}
 
// Usage
console.log(`8-Queens: ${countSolutions(8)} solutions`);   // 92
console.log(`10-Queens: ${countSolutions(10)} solutions`); // 724
console.log(`12-Queens: ${countSolutions(12)} solutions`); // 14200

Advantages of Counting:

Minimal Memory — O(N) space regardless of solution count
Simpler Code — No array management or copying
Faster in Practice — No allocation overhead per solution
Scales Better — Can count solutions for larger N

Python Closure Note:

In Python, count += 1 inside a nested function would create a local variable. Using count = [0] and count[0] += 1 or the nonlocal keyword solves this:

def count_solutions(n):
    count = 0
    
    def backtrack(row):
        nonlocal count
        if row == n:
            count += 1
            return
        # ...

Alternative: Return Value

Another clean approach returns the count:

def backtrack(row):
    if row == n:
        return 1
    
    total = 0
    for col in range(n):
        if is_safe(row, col):
            place(row, col)
            total += backtrack(row + 1)
            remove(row, col)
    return total

Performance Comparison

Let's analyze the practical performance differences between the three approaches:

Time Complexity Comparison
Objective	Best Case	Worst Case	Typical for N=8
Find One	O(N)	O(N!)	~50 nodes (first solution)
Find All	O(N! × N)	O(N! × N)	~2000 nodes, 92 solutions
Count	O(N!)	O(N!)	~2000 nodes, count = 92

Space Complexity Comparison
Objective	Recursion	Constraints	Solutions	Total
Find One	O(N)	O(N)	O(N)	O(N)
Find All	O(N)	O(N)	O(S × N)	O(S × N)
Count	O(N)	O(N)	O(1)	O(N)

Key Observations:

Find-One is fastest — Can terminate very early. For 8-Queens, the first solution is typically found within 50 nodes.
Find-All and Count visit same nodes — They must both explore the entire search tree, but Find-All has additional copy overhead.
Space matters at scale — For N=14 (365,596 solutions), Find-All needs ~4MB just for solutions. Count needs almost nothing extra.
Copy overhead adds up — Creating N-element arrays 365,596 times isn't free. Count avoids this entirely.

Benchmarking Results (N=12, Typical Machine)

Find-One: ~0.1ms | Find-All: ~50ms (14,200 solutions) | Count: ~30ms

The 40% speedup of Count over Find-All comes from eliminating array copies and allocations.

Streaming Solutions

For very large N, storing all solutions is impractical. A streaming approach processes each solution as it's found, using constant extra space:

streaming-solutions.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
75
76
77
78
/**
 * Stream N-Queens solutions with a callback
 * Processes each solution without storing all
 * 
 * @param n Board size
 * @param callback Function called for each solution
 * @returns Number of solutions found
 */
function streamSolutions(
    n: number, 
    callback: (solution: readonly number[]) => void
): number {
    let count = 0;
    const queens: number[] = [];
    const usedColumns = new Set<number>();
    const usedDiag1 = new Set<number>();
    const usedDiag2 = new Set<number>();
 
    function backtrack(row: number): void {
        if (row === n) {
            count++;
            callback(queens);  // Process solution immediately
            return;
        }
 
        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)) {
                continue;
            }
 
            queens.push(col);
            usedColumns.add(col);
            usedDiag1.add(d1);
            usedDiag2.add(d2);
 
            backtrack(row + 1);
 
            queens.pop();
            usedColumns.delete(col);
            usedDiag1.delete(d1);
            usedDiag2.delete(d2);
        }
    }
 
    backtrack(0);
    return count;
}
 
// Usage examples:
 
// 1. Print each solution
streamSolutions(4, (sol) => {
    console.log(`Found: [${sol.join(', ')}]`);
});
 
// 2. Find solutions with specific property
const symmetricSolutions: number[][] = [];
streamSolutions(8, (sol) => {
    if (isPalindromic(sol)) {
        symmetricSolutions.push([...sol]);
    }
});
 
// 3. Write solutions to file (pseudo-code)
// streamSolutions(12, (sol) => {
//     fs.appendFileSync('solutions.txt', sol.join(',') + '\n');
// });
 
function isPalindromic(sol: readonly number[]): boolean {
    const n = sol.length;
    for (let i = 0; i < n / 2; i++) {
        if (sol[i] !== n - 1 - sol[n - 1 - i]) return false;
    }
    return true;
}

Benefits of Streaming

•Constant memory — Only stores current partial solution, not all solutions
•Immediate processing — Handle solutions as found, no wait for completion
•Flexible filtering — Only store solutions meeting criteria
•Cancellation — Can stop early (with modification to check return value)
•I/O interleaving — Write to file/network as solutions are found

Callback Receives Live Reference

Practical Applications

While N-Queens is often treated as a puzzle, the patterns and techniques extend to real-world problems:

Real-World Applications

•Constraint Satisfaction Problems (CSP) — Scheduling, resource allocation, timetabling all follow similar patterns. The backtracking template applies directly.
•VLSI Circuit Design — Placing components on chip without interference mirrors queen placement without attack.
•Task Scheduling — Finding valid task assignments given constraints (resource conflicts, dependencies).
•Graph Coloring — Coloring vertices so no adjacent vertices share a color is structurally similar.
•Sudoku and Puzzle Solving — Same backtracking template with different constraints.
•Compiler Register Allocation — Assigning variables to registers without conflict.
•Test Case Generation — Generating valid test inputs satisfying multiple constraints.

When Each Variant Applies:

Find One	Find All	Count
Need any valid schedule	Enumerate all possibilities for user to choose	Validate algorithm correctness
Game starting position	Generate test suites	Estimate problem difficulty
Prove solvability	Analysis and visualization	Benchmark solvers
Resource allocation	Configuration enumeration	Mathematical research

Interview Connection

Optimization Trade-offs

Different objectives allow different optimizations. Understanding these trade-offs helps you choose the right approach:

Optimization Applicability by Objective
Optimization	Find One	Find All	Count
Early termination	✓ Essential	✗ Not applicable	✗ Not applicable
Symmetry breaking (halve search)	✓ For speed	✗ Would miss solutions	✓ Count half, multiply by 2
Heuristic column ordering	✓ Very effective	✗ Changes discovery order only	✗ No benefit
Parallel search	⚠ More complex	✓ Divide-and-conquer	✓ Sum partial counts
Bitwise operations	✓ Best performance	✓ Best performance	✓ Best performance
Forward checking	✓ Worth overhead	⚠ May not pay off	⚠ May not pay off

Heuristics for Find-One:

When finding just one solution, column ordering can dramatically speed up search:

// Start from the middle columns - more likely to lead to solutions
function getColumnOrder(n: number): number[] {
    const order: number[] = [];
    const mid = Math.floor(n / 2);
    
    for (let offset = 0; offset <= mid; offset++) {
        if (mid + offset < n) order.push(mid + offset);
        if (offset > 0 && mid - offset >= 0) order.push(mid - offset);
    }
    
    return order;
    // For n=8: [4, 3, 5, 2, 6, 1, 7, 0] instead of [0, 1, 2, ..., 7]
}

This heuristic can reduce nodes visited by 50-80% for find-one!

Parallel N-Queens

LeetCode and Interview Format

The N-Queens problem appears on LeetCode and in interviews with specific format requirements. Here's the complete solution in LeetCode format:

leetcode-nqueens.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
75
76
77
78
79
80
81
82
83
84
85
86
87
/**
 * LeetCode 51: N-Queens
 * Return all distinct solutions to the n-queens puzzle.
 * Each solution contains a distinct board configuration where
 * 'Q' indicates a queen and '.' indicates an empty space.
 */
function solveNQueens(n: number): string[][] {
    const solutions: string[][] = [];
    const queens: number[] = [];
    const usedColumns = new Set<number>();
    const usedDiag1 = new Set<number>();
    const usedDiag2 = new Set<number>();
 
    function backtrack(row: number): void {
        if (row === n) {
            // Convert column array to string board format
            solutions.push(queens.map(col => 
                '.'.repeat(col) + 'Q' + '.'.repeat(n - col - 1)
            ));
            return;
        }
 
        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)) {
                continue;
            }
 
            queens.push(col);
            usedColumns.add(col);
            usedDiag1.add(d1);
            usedDiag2.add(d2);
 
            backtrack(row + 1);
 
            queens.pop();
            usedColumns.delete(col);
            usedDiag1.delete(d1);
            usedDiag2.delete(d2);
        }
    }
 
    backtrack(0);
    return solutions;
}
 
/**
 * LeetCode 52: N-Queens II
 * Return the number of distinct solutions to the n-queens puzzle.
 */
function totalNQueens(n: number): number {
    let count = 0;
    const usedColumns = new Set<number>();
    const usedDiag1 = new Set<number>();
    const usedDiag2 = new Set<number>();
 
    function backtrack(row: number): void {
        if (row === n) {
            count++;
            return;
        }
 
        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)) {
                continue;
            }
 
            usedColumns.add(col);
            usedDiag1.add(d1);
            usedDiag2.add(d2);
 
            backtrack(row + 1);
 
            usedColumns.delete(col);
            usedDiag1.delete(d1);
            usedDiag2.delete(d2);
        }
    }
 
    backtrack(0);
    return count;
}

Interview Tips

Clarify the variant — Ask if they want one solution, all solutions, or just the count.
Start simple — Explain the approach before coding.
Optimize progressively — Start with O(N) checking, then mention O(1) optimization.
Discuss trade-offs — Explain space for sets vs time for linear search.
Handle edge cases — N=1 (trivial), N=2,3 (no solution), N≥4 (solutions exist).

Module Summary: N-Queens Mastery

Congratulations! You've mastered the N-Queens problem—the quintessential backtracking challenge. Let's consolidate everything you've learned:

Module Takeaways

•The Problem — Place N queens on an N×N board with no mutual attacks. The classic demonstration of backtracking.
•Why Backtracking — Incremental construction, early constraint detection, reversible state, and exhaustive coverage make it ideal.
•State Representation — Use queens[row] = column for simplicity and efficiency. Sets track occupied columns and diagonals.
•Diagonal Mathematics — Main diagonal: r-c constant. Anti-diagonal: r+c constant. This enables O(1) conflict checking.
•Choose-Explore-Unchoose — The universal backtracking pattern. Every 'choose' must have a matching 'unchoose'.
•Three Variants — Find-one (early exit), find-all (store and continue), count (increment only). Same core, different handling.
•Optimization Options — Bitwise operations, forward checking, symmetry breaking—apply based on N and objective.
•Practical Patterns — N-Queens techniques apply to CSP, scheduling, VLSI design, and countless other constraint problems.

Quick Reference: N-Queens Variants
Variant	Return Type	Base Case	Key Code
Find One	boolean	return true	if (backtrack()) return true
Find All	void	solutions.push([...queens])	Always backtrack after base case
Count	void	count++	Increment counter, no storage

Moving Forward:

The next modules will apply these patterns to Sudoku solving, constraint satisfaction frameworks, and more complex backtracking scenarios. The foundation you've built here will serve you well.

Module Complete!

4 / 4