Data Structures & AlgorithmsN-Queens Problem

N-Queens Problem — The Classic Backtracking Challenge

LevelIntermediate

Duration75 mins

TopicN-Queens Problem

3 / 4

Constraint Checking

The Art of Efficient Constraint Checking

The power of backtracking lies in early pruning—detecting constraint violations as soon as possible to avoid exploring dead-end branches. For N-Queens, this means efficiently determining whether a proposed queen placement conflicts with existing queens.

This page dives deep into the mathematics and implementation of constraint checking. We'll transform intuitive conflict detection into optimized O(1) operations that form the heart of an efficient solver.

What You Will Master

You'll understand the mathematical properties that make diagonal detection elegant, implement multiple approaches to conflict checking with different trade-offs, and learn optimization techniques that can speed up your solver by orders of magnitude.

The Three Constraints

A queen placement at (row, col) is valid if and only if no previously placed queen:

Shares the same row — Trivially satisfied by our row-by-row approach
Shares the same column — Must check column uniqueness
Shares a diagonal — Must check both diagonal directions

Since we place exactly one queen per row (by construction), we only need to check columns and diagonals. Let's examine each constraint in detail.

Column Constraint (Easy):

No two queens can occupy the same column. If we've placed queens in previous rows, we simply check if the new column has been used.

// Naive: O(row) - check all previous queens
function columnConflict(row: number, col: number, queens: number[]): boolean {
    for (let prevRow = 0; prevRow < row; prevRow++) {
        if (queens[prevRow] === col) return true;
    }
    return false;
}

// Optimized: O(1) - use a Set
const usedColumns = new Set<number>();
function hasColumnConflict(col: number): boolean {
    return usedColumns.has(col);
}

The Row Constraint 'For Free'

Our row-by-row algorithm inherently satisfies the row constraint. By processing row 0, then row 1, then row 2, etc., we guarantee exactly one queen per row. This is why choosing a good exploration strategy matters—it can eliminate entire constraint categories.

The Mathematics of Diagonals

Diagonal detection is where N-Queens gets mathematically interesting. A queen can attack along two diagonal directions—understanding their properties enables O(1) conflict checking.

The Naive Approach:

Two queens at (r1, c1) and (r2, c2) are on the same diagonal if and only if:

|r1 - r2| = |c1 - c2|

This checks if the vertical distance equals the horizontal distance, which is the definition of a diagonal line at 45°.

function onSameDiagonal(r1: number, c1: number, r2: number, c2: number): boolean {
    return Math.abs(r1 - r2) === Math.abs(c1 - c2);
}

This works, but requires O(row) comparisons since we must check against all previously placed queens.

The Key Insight

Every diagonal can be uniquely identified by a single number. This transforms diagonal checking from 'compare against all queens' to 'check if diagonal ID is in a set'—reducing complexity from O(N) to O(1).

Diagonal Identification:

Consider an N×N board. There are two types of diagonals:

Main Diagonals (↘ direction):

Run from top-left to bottom-right
All cells (r, c) on the same main diagonal have the same value of r - c
There are 2N - 1 distinct main diagonals
Values range from -(N-1) to (N-1)

Anti-Diagonals (↗ direction):

Run from bottom-left to top-right
All cells (r, c) on the same anti-diagonal have the same value of r + c
There are 2N - 1 distinct anti-diagonals
Values range from 0 to 2(N-1)

Diagonal Identifiers for a 4×4 Board
Position (r,c)	r - c (Main Diag)	r + c (Anti-Diag)
(0,0)	0	0
(0,1)	-1	1
(0,2)	-2	2
(0,3)	-3	3
(1,0)	1	1
(1,1)	0	2
(1,2)	-1	3
(1,3)	-2	4
(2,0)	2	2
(2,1)	1	3
(2,2)	0	4
(2,3)	-1	5
(3,0)	3	3
(3,1)	2	4
(3,2)	1	5
(3,3)	0	6

Visual Representation:

Main Diagonals (r - c):        Anti-Diagonals (r + c):

     0   1   2   3               0   1   2   3
   ┌───┬───┬───┬───┐           ┌───┬───┬───┬───┐
 0 │ 0 │-1 │-2 │-3 │         0 │ 0 │ 1 │ 2 │ 3 │
   ├───┼───┼───┼───┤           ├───┼───┼───┼───┤
 1 │ 1 │ 0 │-1 │-2 │         1 │ 1 │ 2 │ 3 │ 4 │
   ├───┼───┼───┼───┤           ├───┼───┼───┼───┤
 2 │ 2 │ 1 │ 0 │-1 │         2 │ 2 │ 3 │ 4 │ 5 │
   ├───┼───┼───┼───┤           ├───┼───┼───┼───┤
 3 │ 3 │ 2 │ 1 │ 0 │         3 │ 3 │ 4 │ 5 │ 6 │
   └───┴───┴───┴───┘           └───┴───┴───┴───┘

Notice: Same values form diagonals!
- Main diagonal 0: (0,0), (1,1), (2,2), (3,3)
- Anti-diagonal 3: (0,3), (1,2), (2,1), (3,0)

O(1) Conflict Detection

Using diagonal identifiers, we can achieve O(1) conflict detection using sets:

o1-detection.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
class NQueensO1 {
    private n: number;
    private usedColumns = new Set<number>();
    private usedDiag1 = new Set<number>();   // r - c (main diagonal)
    private usedDiag2 = new Set<number>();   // r + c (anti-diagonal)
 
    /**
     * Check if placing a queen at (row, col) is safe.
     * Time: O(1)
     */
    isSafe(row: number, col: number): boolean {
        const d1 = row - col;   // Main diagonal identifier
        const d2 = row + col;   // Anti-diagonal identifier
 
        return !this.usedColumns.has(col) &&
               !this.usedDiag1.has(d1) &&
               !this.usedDiag2.has(d2);
    }
 
    /**
     * Place a queen at (row, col) and update constraints.
     * Time: O(1)
     */
    placeQueen(row: number, col: number): void {
        this.usedColumns.add(col);
        this.usedDiag1.add(row - col);
        this.usedDiag2.add(row + col);
    }
 
    /**
     * Remove a queen from (row, col) and revert constraints.
     * Time: O(1)
     */
    removeQueen(row: number, col: number): void {
        this.usedColumns.delete(col);
        this.usedDiag1.delete(row - col);
        this.usedDiag2.delete(row + col);
    }
}

Complexity Analysis:

Operation	Naive (check all queens)	Set-Based
`isSafe()`	O(row) ≈ O(N)	O(1)
`placeQueen()`	O(1)	O(1)
`removeQueen()`	O(1)	O(1)
Space	O(N) for queens array only	O(N) for 3 sets

For the full backtracking algorithm:

Naive: Each node visits O(N) children, each with O(N) safety check → O(N²) per node
Set-based: Same traversal but O(1) safety check → O(N) per node

This is a significant speedup, especially for larger N.

Why This Works

Hash sets provide O(1) average-case lookup. By using diagonal identifiers as keys, we transform 'is any queen on this diagonal?' into a simple set membership test. The mathematical property that all cells on a diagonal share the same r-c or r+c value makes this possible.

Alternative: Boolean Array Approach

While sets are intuitive, boolean arrays can be even faster due to better cache locality and no hash function overhead:

boolean-array.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
class NQueensArray {
    private n: number;
    private columns: boolean[];      // columns[c] = true if column c occupied
    private diag1: boolean[];        // diag1[r-c+n-1] = true if main diagonal occupied
    private diag2: boolean[];        // diag2[r+c] = true if anti-diagonal occupied
 
    constructor(n: number) {
        this.n = n;
        this.columns = new Array(n).fill(false);
        // 2n-1 possible values for each diagonal type
        this.diag1 = new Array(2 * n - 1).fill(false);
        this.diag2 = new Array(2 * n - 1).fill(false);
    }
 
    /**
     * Note: We offset r-c by (n-1) to handle negative values.
     * r-c ranges from -(n-1) to +(n-1), so r-c+(n-1) ranges from 0 to 2n-2.
     */
    private getDiag1Index(row: number, col: number): number {
        return row - col + this.n - 1;
    }
 
    private getDiag2Index(row: number, col: number): number {
        return row + col;  // Already ranges from 0 to 2n-2
    }
 
    isSafe(row: number, col: number): boolean {
        return !this.columns[col] &&
               !this.diag1[this.getDiag1Index(row, col)] &&
               !this.diag2[this.getDiag2Index(row, col)];
    }
 
    placeQueen(row: number, col: number): void {
        this.columns[col] = true;
        this.diag1[this.getDiag1Index(row, col)] = true;
        this.diag2[this.getDiag2Index(row, col)] = true;
    }
 
    removeQueen(row: number, col: number): void {
        this.columns[col] = false;
        this.diag1[this.getDiag1Index(row, col)] = false;
        this.diag2[this.getDiag2Index(row, col)] = false;
    }
}

Set vs Array Trade-offs
Aspect	Hash Set	Boolean Array
Lookup complexity	O(1) average	O(1) worst-case
Memory access	Scattered (hash collisions)	Sequential (cache-friendly)
Space	Dynamic, proportional to queens placed	Fixed 5N-2 bytes
Index handling	Negative values okay	Need offset for r-c
Typical speed	Good	Slightly faster for large N
Code clarity	More intuitive	Requires index math

Practical Advice

For interviews, use the Set-based approach—it's clearer and the performance difference is negligible. For competitive programming or when N is very large, the array approach can provide a measurable speedup.

The Bitwise Approach

For maximum performance, we can represent occupied columns and diagonals as bitmasks. This enables checking all three constraints in a single bitwise operation.

bitwise-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
/**
 * Bitwise N-Queens solver
 * Uses integer bitmasks for ultra-fast constraint checking
 * 
 * Limitation: N must be ≤ 32 (or 64 with BigInt)
 */
function solveNQueensBitwise(n: number): number[][] {
    const solutions: number[][] = [];
    const queens: number[] = [];
 
    /**
     * columns: bit i set means column i is occupied
     * diag1: main diagonals (shifts right each row)
     * diag2: anti-diagonals (shifts left each row)
     */
    function backtrack(
        row: number,
        columns: number,
        diag1: number,
        diag2: number
    ): void {
        if (row === n) {
            solutions.push([...queens]);
            return;
        }
 
        // All positions attacked by existing queens
        // Combine column and both diagonal constraints
        const allAttacked = columns | diag1 | diag2;
 
        // Available positions: bits that are 0 in allAttacked
        // Mask to only consider first n bits
        let availablePositions = ~allAttacked & ((1 << n) - 1);
 
        while (availablePositions > 0) {
            // Get rightmost available position
            const position = availablePositions & -availablePositions;
            
            // Convert bit position to column index
            const col = Math.log2(position);
            
            queens.push(col);
            
            backtrack(
                row + 1,
                columns | position,           // Mark column
                (diag1 | position) << 1,      // Shift main diagonal left
                (diag2 | position) >> 1       // Shift anti-diagonal right
            );
            
            queens.pop();
            
            // Remove this position from available
            availablePositions ^= position;
        }
    }
 
    backtrack(0, 0, 0, 0);
    return solutions;
}

How It Works:

Column tracking: columns has bit i set if column i is occupied
Diagonal shifting: The key insight is that as we move down rows:
- Main diagonal positions shift left (same r-c means position moves right relative to column bits)
- Anti-diagonal positions shift right (same r+c means position moves left)
Finding available positions:
- ~allAttacked gives positions NOT attacked
- & ((1 << n) - 1) masks to only valid columns
Extracting rightmost bit: x & -x isolates the lowest set bit (a clever bit manipulation trick)
Removing a bit: x ^= bit removes that bit from consideration

Complexity and Limitations

Limitations:

Requires N ≤ 32 (32-bit integer) or N ≤ 64 (64-bit)
More complex to understand and debug
Harder to extend for variants

When to use:

Competitive programming
Maximum performance requirements
Large-scale solution counting

Beyond Basic Pruning: Advanced Strategies

Basic constraint checking prunes branches that immediately violate constraints. Advanced pruning looks ahead to detect branches that will inevitably fail later.

Advanced Pruning Techniques

•Forward Checking — Before placing a queen, count remaining valid positions for future rows. If any row has zero valid positions, prune immediately.
•Arc Consistency — Propagate constraints to eliminate impossible positions from all future rows, not just the next one.
•Most Constrained Variable (MCV) — Instead of filling rows in order, fill the row with fewest remaining options first.
•Least Constraining Value (LCV) — When choosing a column, pick the one that eliminates the fewest options for future rows.
•Symmetry Breaking — Since solutions have rotational/reflective symmetry, only search for solutions where the first queen is in the left half of the first row.

forward-checking.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
/**
 * Forward Checking: Prune if any future row has no valid positions
 */
function solveWithForwardChecking(n: number): number[][] {
    const solutions: number[][] = [];
    const queens: number[] = [];
    const usedColumns = new Set<number>();
    const usedDiag1 = new Set<number>();
    const usedDiag2 = new Set<number>();
 
    // Count valid positions for a given row
    function countValidPositions(row: number): number {
        let count = 0;
        for (let col = 0; col < n; col++) {
            if (!usedColumns.has(col) &&
                !usedDiag1.has(row - col) &&
                !usedDiag2.has(row + col)) {
                count++;
            }
        }
        return count;
    }
 
    // Check if all future rows have at least one valid position
    function forwardCheck(currentRow: number): boolean {
        for (let row = currentRow + 1; row < n; row++) {
            if (countValidPositions(row) === 0) {
                return false;  // Guaranteed failure ahead
            }
        }
        return true;
    }
 
    function backtrack(row: number): void {
        if (row === n) {
            solutions.push([...queens]);
            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;
            }
 
            // Place queen
            queens.push(col);
            usedColumns.add(col);
            usedDiag1.add(d1);
            usedDiag2.add(d2);
 
            // Only recurse if forward check passes
            if (forwardCheck(row)) {
                backtrack(row + 1);
            }
 
            // Remove queen
            queens.pop();
            usedColumns.delete(col);
            usedDiag1.delete(d1);
            usedDiag2.delete(d2);
        }
    }
 
    backtrack(0);
    return solutions;
}

Trade-off Analysis:

Forward checking adds O(N²) work per node (checking all future rows). Is it worth it?

Metric	Basic Constraint Check	Forward Checking
Work per node	O(N)	O(N²)
Nodes visited	More	Fewer
Total work	Depends on N	Depends on N

For small N, the overhead isn't worth it. For large N, forward checking can dramatically reduce nodes visited, often resulting in net speedup. The crossover point is typically around N=12-15.

Best practice: Start with basic constraint checking. Add forward checking only if profiling shows it helps for your specific N values.

Symmetry Breaking

N-Queens solutions come in symmetric groups. A single solution, when rotated (90°, 180°, 270°) and reflected, can produce up to 8 equivalent solutions. By exploiting symmetry, we can reduce the search space significantly.

The 8 Symmetries of a Square:

Identity — The original solution
90° rotation — Rotate clockwise
180° rotation — Rotate twice
270° rotation — Rotate three times
Horizontal reflection — Mirror left-right
Vertical reflection — Mirror top-bottom
Main diagonal reflection — Mirror along main diagonal
Anti-diagonal reflection — Mirror along anti-diagonal

Symmetry Breaking Strategy:

To count distinct solutions, we can:

Only search for solutions where the first queen is in columns 0 to ⌊N/2⌋
For each solution found, divide by 8 (or account for solutions with fewer than 8 symmetric variants)

Alternatively, for finding ALL solutions including symmetric ones, no special handling is needed—just enumerate all of them.

symmetry-breaking.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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
/**
 * Count distinct N-Queens solutions (accounting for symmetry)
 * 
 * Strategy: Only search first queen positions in left half,
 * then carefully account for symmetric solutions.
 */
function countDistinctSolutions(n: number): number {
    // For simplicity, we find all solutions then deduplicate
    // A more efficient approach would avoid generating symmetric solutions
    
    const allSolutions = solveNQueens(n);  // Get all 92 solutions for n=8
    const uniqueSignatures = new Set<string>();
    
    for (const solution of allSolutions) {
        // Generate canonical form (smallest rotation/reflection)
        const canonical = getCanonicalForm(solution, n);
        uniqueSignatures.add(canonical);
    }
    
    return uniqueSignatures.size;
}
 
function getCanonicalForm(queens: number[], n: number): string {
    const transformations = [
        queens,
        rotate90(queens, n),
        rotate180(queens, n),
        rotate270(queens, n),
        reflectHorizontal(queens, n),
        reflectVertical(queens, n),
        reflectMainDiag(queens, n),
        reflectAntiDiag(queens, n),
    ];
    
    // Return lexicographically smallest representation
    return transformations
        .map(t => t.join(','))
        .sort()[0];
}
 
// Transformation functions
function rotate90(queens: number[], n: number): number[] {
    // (r, c) -> (c, n-1-r)
    const result: number[] = new Array(n);
    for (let r = 0; r < n; r++) {
        const c = queens[r];
        result[c] = n - 1 - r;
    }
    return result;
}
 
function rotate180(queens: number[], n: number): number[] {
    return queens.map((c, r) => n - 1 - queens[n - 1 - r]);
}
 
function rotate270(queens: number[], n: number): number[] {
    // (r, c) -> (n-1-c, r)
    const result: number[] = new Array(n);
    for (let r = 0; r < n; r++) {
        const c = queens[r];
        result[n - 1 - c] = r;
    }
    return result;
}
 
function reflectHorizontal(queens: number[], n: number): number[] {
    return queens.map(c => n - 1 - c);
}
 
function reflectVertical(queens: number[], n: number): number[] {
    return [...queens].reverse();
}
 
function reflectMainDiag(queens: number[], n: number): number[] {
    const result: number[] = new Array(n);
    for (let r = 0; r < n; r++) {
        result[queens[r]] = r;
    }
    return result;
}
 
function reflectAntiDiag(queens: number[], n: number): number[] {
    const result: number[] = new Array(n);
    for (let r = 0; r < n; r++) {
        result[n - 1 - queens[r]] = n - 1 - r;
    }
    return result;
}

Total vs Distinct Solutions
N	All Solutions	Distinct (Symmetry)	Ratio
4	2	1	2.0
5	10	2	5.0
6	4	1	4.0
7	40	6	6.67
8	92	12	7.67
9	352	46	7.65
10	724	92	7.87

When Ratio Isn't 8

Some solutions are symmetric to themselves (fixed points under rotation/reflection). For example, a solution with 180° rotational symmetry only generates 4 distinct variants, not 8. This is why the ratio varies.

Summary: Constraint Checking Mastery

We've covered the full spectrum of constraint checking for N-Queens:

Key Takeaways

•Three Constraints — Row (free by construction), column (simple check), diagonal (mathematical property).
•Diagonal Mathematics — Main diagonal: r-c constant. Anti-diagonal: r+c constant. These identifiers enable O(1) checking.
•O(1) Detection — Use hash sets or boolean arrays to check all constraints in constant time.
•Bitwise Approach — For maximum speed, use bitmasks to check all constraints in a single operation.
•Advanced Pruning — Forward checking, arc consistency, and heuristics can reduce nodes visited at the cost of per-node overhead.
•Symmetry Breaking — Exploit board symmetries to reduce search space or count distinct solutions.

What's Next:

With constraint checking mastered, the final page explores the difference between counting solutions and finding all solutions—including space-time tradeoffs, output formats, and when each approach is appropriate.

Page Complete

You now understand the mathematics behind diagonal detection, can implement O(1) conflict checking, and know when to apply advanced pruning strategies. You're ready to tackle N-Queens variants efficiently.

3 / 4

Loading learning content...

Data Structures & AlgorithmsN-Queens Problem

N-Queens Problem — The Classic Backtracking Challenge

LevelIntermediate

Duration75 mins

TopicN-Queens Problem

3 / 4

Constraint Checking

The Art of Efficient Constraint Checking

What You Will Master

The Three Constraints

A queen placement at (row, col) is valid if and only if no previously placed queen:

Shares the same row — Trivially satisfied by our row-by-row approach
Shares the same column — Must check column uniqueness
Shares a diagonal — Must check both diagonal directions

Since we place exactly one queen per row (by construction), we only need to check columns and diagonals. Let's examine each constraint in detail.

Column Constraint (Easy):

No two queens can occupy the same column. If we've placed queens in previous rows, we simply check if the new column has been used.

// Naive: O(row) - check all previous queens
function columnConflict(row: number, col: number, queens: number[]): boolean {
    for (let prevRow = 0; prevRow < row; prevRow++) {
        if (queens[prevRow] === col) return true;
    }
    return false;
}

// Optimized: O(1) - use a Set
const usedColumns = new Set<number>();
function hasColumnConflict(col: number): boolean {
    return usedColumns.has(col);
}

The Row Constraint 'For Free'

The Mathematics of Diagonals

Diagonal detection is where N-Queens gets mathematically interesting. A queen can attack along two diagonal directions—understanding their properties enables O(1) conflict checking.

The Naive Approach:

Two queens at (r1, c1) and (r2, c2) are on the same diagonal if and only if:

|r1 - r2| = |c1 - c2|

This checks if the vertical distance equals the horizontal distance, which is the definition of a diagonal line at 45°.

function onSameDiagonal(r1: number, c1: number, r2: number, c2: number): boolean {
    return Math.abs(r1 - r2) === Math.abs(c1 - c2);
}

This works, but requires O(row) comparisons since we must check against all previously placed queens.

The Key Insight

Diagonal Identification:

Consider an N×N board. There are two types of diagonals:

Main Diagonals (↘ direction):

Run from top-left to bottom-right
All cells (r, c) on the same main diagonal have the same value of r - c
There are 2N - 1 distinct main diagonals
Values range from -(N-1) to (N-1)

Anti-Diagonals (↗ direction):

Run from bottom-left to top-right
All cells (r, c) on the same anti-diagonal have the same value of r + c
There are 2N - 1 distinct anti-diagonals
Values range from 0 to 2(N-1)

Diagonal Identifiers for a 4×4 Board
Position (r,c)	r - c (Main Diag)	r + c (Anti-Diag)
(0,0)	0	0
(0,1)	-1	1
(0,2)	-2	2
(0,3)	-3	3
(1,0)	1	1
(1,1)	0	2
(1,2)	-1	3
(1,3)	-2	4
(2,0)	2	2
(2,1)	1	3
(2,2)	0	4
(2,3)	-1	5
(3,0)	3	3
(3,1)	2	4
(3,2)	1	5
(3,3)	0	6

Visual Representation:

Main Diagonals (r - c):        Anti-Diagonals (r + c):

     0   1   2   3               0   1   2   3
   ┌───┬───┬───┬───┐           ┌───┬───┬───┬───┐
 0 │ 0 │-1 │-2 │-3 │         0 │ 0 │ 1 │ 2 │ 3 │
   ├───┼───┼───┼───┤           ├───┼───┼───┼───┤
 1 │ 1 │ 0 │-1 │-2 │         1 │ 1 │ 2 │ 3 │ 4 │
   ├───┼───┼───┼───┤           ├───┼───┼───┼───┤
 2 │ 2 │ 1 │ 0 │-1 │         2 │ 2 │ 3 │ 4 │ 5 │
   ├───┼───┼───┼───┤           ├───┼───┼───┼───┤
 3 │ 3 │ 2 │ 1 │ 0 │         3 │ 3 │ 4 │ 5 │ 6 │
   └───┴───┴───┴───┘           └───┴───┴───┴───┘

Notice: Same values form diagonals!
- Main diagonal 0: (0,0), (1,1), (2,2), (3,3)
- Anti-diagonal 3: (0,3), (1,2), (2,1), (3,0)

O(1) Conflict Detection

Using diagonal identifiers, we can achieve O(1) conflict detection using sets:

o1-detection.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
class NQueensO1 {
    private n: number;
    private usedColumns = new Set<number>();
    private usedDiag1 = new Set<number>();   // r - c (main diagonal)
    private usedDiag2 = new Set<number>();   // r + c (anti-diagonal)
 
    /**
     * Check if placing a queen at (row, col) is safe.
     * Time: O(1)
     */
    isSafe(row: number, col: number): boolean {
        const d1 = row - col;   // Main diagonal identifier
        const d2 = row + col;   // Anti-diagonal identifier
 
        return !this.usedColumns.has(col) &&
               !this.usedDiag1.has(d1) &&
               !this.usedDiag2.has(d2);
    }
 
    /**
     * Place a queen at (row, col) and update constraints.
     * Time: O(1)
     */
    placeQueen(row: number, col: number): void {
        this.usedColumns.add(col);
        this.usedDiag1.add(row - col);
        this.usedDiag2.add(row + col);
    }
 
    /**
     * Remove a queen from (row, col) and revert constraints.
     * Time: O(1)
     */
    removeQueen(row: number, col: number): void {
        this.usedColumns.delete(col);
        this.usedDiag1.delete(row - col);
        this.usedDiag2.delete(row + col);
    }
}

Complexity Analysis:

Operation	Naive (check all queens)	Set-Based
`isSafe()`	O(row) ≈ O(N)	O(1)
`placeQueen()`	O(1)	O(1)
`removeQueen()`	O(1)	O(1)
Space	O(N) for queens array only	O(N) for 3 sets

For the full backtracking algorithm:

Naive: Each node visits O(N) children, each with O(N) safety check → O(N²) per node
Set-based: Same traversal but O(1) safety check → O(N) per node

This is a significant speedup, especially for larger N.

Why This Works

Alternative: Boolean Array Approach

While sets are intuitive, boolean arrays can be even faster due to better cache locality and no hash function overhead:

boolean-array.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
class NQueensArray {
    private n: number;
    private columns: boolean[];      // columns[c] = true if column c occupied
    private diag1: boolean[];        // diag1[r-c+n-1] = true if main diagonal occupied
    private diag2: boolean[];        // diag2[r+c] = true if anti-diagonal occupied
 
    constructor(n: number) {
        this.n = n;
        this.columns = new Array(n).fill(false);
        // 2n-1 possible values for each diagonal type
        this.diag1 = new Array(2 * n - 1).fill(false);
        this.diag2 = new Array(2 * n - 1).fill(false);
    }
 
    /**
     * Note: We offset r-c by (n-1) to handle negative values.
     * r-c ranges from -(n-1) to +(n-1), so r-c+(n-1) ranges from 0 to 2n-2.
     */
    private getDiag1Index(row: number, col: number): number {
        return row - col + this.n - 1;
    }
 
    private getDiag2Index(row: number, col: number): number {
        return row + col;  // Already ranges from 0 to 2n-2
    }
 
    isSafe(row: number, col: number): boolean {
        return !this.columns[col] &&
               !this.diag1[this.getDiag1Index(row, col)] &&
               !this.diag2[this.getDiag2Index(row, col)];
    }
 
    placeQueen(row: number, col: number): void {
        this.columns[col] = true;
        this.diag1[this.getDiag1Index(row, col)] = true;
        this.diag2[this.getDiag2Index(row, col)] = true;
    }
 
    removeQueen(row: number, col: number): void {
        this.columns[col] = false;
        this.diag1[this.getDiag1Index(row, col)] = false;
        this.diag2[this.getDiag2Index(row, col)] = false;
    }
}

Set vs Array Trade-offs
Aspect	Hash Set	Boolean Array
Lookup complexity	O(1) average	O(1) worst-case
Memory access	Scattered (hash collisions)	Sequential (cache-friendly)
Space	Dynamic, proportional to queens placed	Fixed 5N-2 bytes
Index handling	Negative values okay	Need offset for r-c
Typical speed	Good	Slightly faster for large N
Code clarity	More intuitive	Requires index math

Practical Advice

The Bitwise Approach

For maximum performance, we can represent occupied columns and diagonals as bitmasks. This enables checking all three constraints in a single bitwise operation.

bitwise-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
/**
 * Bitwise N-Queens solver
 * Uses integer bitmasks for ultra-fast constraint checking
 * 
 * Limitation: N must be ≤ 32 (or 64 with BigInt)
 */
function solveNQueensBitwise(n: number): number[][] {
    const solutions: number[][] = [];
    const queens: number[] = [];
 
    /**
     * columns: bit i set means column i is occupied
     * diag1: main diagonals (shifts right each row)
     * diag2: anti-diagonals (shifts left each row)
     */
    function backtrack(
        row: number,
        columns: number,
        diag1: number,
        diag2: number
    ): void {
        if (row === n) {
            solutions.push([...queens]);
            return;
        }
 
        // All positions attacked by existing queens
        // Combine column and both diagonal constraints
        const allAttacked = columns | diag1 | diag2;
 
        // Available positions: bits that are 0 in allAttacked
        // Mask to only consider first n bits
        let availablePositions = ~allAttacked & ((1 << n) - 1);
 
        while (availablePositions > 0) {
            // Get rightmost available position
            const position = availablePositions & -availablePositions;
            
            // Convert bit position to column index
            const col = Math.log2(position);
            
            queens.push(col);
            
            backtrack(
                row + 1,
                columns | position,           // Mark column
                (diag1 | position) << 1,      // Shift main diagonal left
                (diag2 | position) >> 1       // Shift anti-diagonal right
            );
            
            queens.pop();
            
            // Remove this position from available
            availablePositions ^= position;
        }
    }
 
    backtrack(0, 0, 0, 0);
    return solutions;
}

How It Works:

Column tracking: columns has bit i set if column i is occupied
Diagonal shifting: The key insight is that as we move down rows:
- Main diagonal positions shift left (same r-c means position moves right relative to column bits)
- Anti-diagonal positions shift right (same r+c means position moves left)
Finding available positions:
- ~allAttacked gives positions NOT attacked
- & ((1 << n) - 1) masks to only valid columns
Extracting rightmost bit: x & -x isolates the lowest set bit (a clever bit manipulation trick)
Removing a bit: x ^= bit removes that bit from consideration

Complexity and Limitations

Limitations:

Requires N ≤ 32 (32-bit integer) or N ≤ 64 (64-bit)
More complex to understand and debug
Harder to extend for variants

When to use:

Competitive programming
Maximum performance requirements
Large-scale solution counting

Beyond Basic Pruning: Advanced Strategies

Basic constraint checking prunes branches that immediately violate constraints. Advanced pruning looks ahead to detect branches that will inevitably fail later.

Advanced Pruning Techniques

•Forward Checking — Before placing a queen, count remaining valid positions for future rows. If any row has zero valid positions, prune immediately.
•Arc Consistency — Propagate constraints to eliminate impossible positions from all future rows, not just the next one.
•Most Constrained Variable (MCV) — Instead of filling rows in order, fill the row with fewest remaining options first.
•Least Constraining Value (LCV) — When choosing a column, pick the one that eliminates the fewest options for future rows.
•Symmetry Breaking — Since solutions have rotational/reflective symmetry, only search for solutions where the first queen is in the left half of the first row.

forward-checking.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
/**
 * Forward Checking: Prune if any future row has no valid positions
 */
function solveWithForwardChecking(n: number): number[][] {
    const solutions: number[][] = [];
    const queens: number[] = [];
    const usedColumns = new Set<number>();
    const usedDiag1 = new Set<number>();
    const usedDiag2 = new Set<number>();
 
    // Count valid positions for a given row
    function countValidPositions(row: number): number {
        let count = 0;
        for (let col = 0; col < n; col++) {
            if (!usedColumns.has(col) &&
                !usedDiag1.has(row - col) &&
                !usedDiag2.has(row + col)) {
                count++;
            }
        }
        return count;
    }
 
    // Check if all future rows have at least one valid position
    function forwardCheck(currentRow: number): boolean {
        for (let row = currentRow + 1; row < n; row++) {
            if (countValidPositions(row) === 0) {
                return false;  // Guaranteed failure ahead
            }
        }
        return true;
    }
 
    function backtrack(row: number): void {
        if (row === n) {
            solutions.push([...queens]);
            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;
            }
 
            // Place queen
            queens.push(col);
            usedColumns.add(col);
            usedDiag1.add(d1);
            usedDiag2.add(d2);
 
            // Only recurse if forward check passes
            if (forwardCheck(row)) {
                backtrack(row + 1);
            }
 
            // Remove queen
            queens.pop();
            usedColumns.delete(col);
            usedDiag1.delete(d1);
            usedDiag2.delete(d2);
        }
    }
 
    backtrack(0);
    return solutions;
}

Trade-off Analysis:

Forward checking adds O(N²) work per node (checking all future rows). Is it worth it?

Metric	Basic Constraint Check	Forward Checking
Work per node	O(N)	O(N²)
Nodes visited	More	Fewer
Total work	Depends on N	Depends on N

For small N, the overhead isn't worth it. For large N, forward checking can dramatically reduce nodes visited, often resulting in net speedup. The crossover point is typically around N=12-15.

Best practice: Start with basic constraint checking. Add forward checking only if profiling shows it helps for your specific N values.

Symmetry Breaking

The 8 Symmetries of a Square:

Identity — The original solution
90° rotation — Rotate clockwise
180° rotation — Rotate twice
270° rotation — Rotate three times
Horizontal reflection — Mirror left-right
Vertical reflection — Mirror top-bottom
Main diagonal reflection — Mirror along main diagonal
Anti-diagonal reflection — Mirror along anti-diagonal

Symmetry Breaking Strategy:

To count distinct solutions, we can:

Only search for solutions where the first queen is in columns 0 to ⌊N/2⌋
For each solution found, divide by 8 (or account for solutions with fewer than 8 symmetric variants)

Alternatively, for finding ALL solutions including symmetric ones, no special handling is needed—just enumerate all of them.

symmetry-breaking.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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
/**
 * Count distinct N-Queens solutions (accounting for symmetry)
 * 
 * Strategy: Only search first queen positions in left half,
 * then carefully account for symmetric solutions.
 */
function countDistinctSolutions(n: number): number {
    // For simplicity, we find all solutions then deduplicate
    // A more efficient approach would avoid generating symmetric solutions
    
    const allSolutions = solveNQueens(n);  // Get all 92 solutions for n=8
    const uniqueSignatures = new Set<string>();
    
    for (const solution of allSolutions) {
        // Generate canonical form (smallest rotation/reflection)
        const canonical = getCanonicalForm(solution, n);
        uniqueSignatures.add(canonical);
    }
    
    return uniqueSignatures.size;
}
 
function getCanonicalForm(queens: number[], n: number): string {
    const transformations = [
        queens,
        rotate90(queens, n),
        rotate180(queens, n),
        rotate270(queens, n),
        reflectHorizontal(queens, n),
        reflectVertical(queens, n),
        reflectMainDiag(queens, n),
        reflectAntiDiag(queens, n),
    ];
    
    // Return lexicographically smallest representation
    return transformations
        .map(t => t.join(','))
        .sort()[0];
}
 
// Transformation functions
function rotate90(queens: number[], n: number): number[] {
    // (r, c) -> (c, n-1-r)
    const result: number[] = new Array(n);
    for (let r = 0; r < n; r++) {
        const c = queens[r];
        result[c] = n - 1 - r;
    }
    return result;
}
 
function rotate180(queens: number[], n: number): number[] {
    return queens.map((c, r) => n - 1 - queens[n - 1 - r]);
}
 
function rotate270(queens: number[], n: number): number[] {
    // (r, c) -> (n-1-c, r)
    const result: number[] = new Array(n);
    for (let r = 0; r < n; r++) {
        const c = queens[r];
        result[n - 1 - c] = r;
    }
    return result;
}
 
function reflectHorizontal(queens: number[], n: number): number[] {
    return queens.map(c => n - 1 - c);
}
 
function reflectVertical(queens: number[], n: number): number[] {
    return [...queens].reverse();
}
 
function reflectMainDiag(queens: number[], n: number): number[] {
    const result: number[] = new Array(n);
    for (let r = 0; r < n; r++) {
        result[queens[r]] = r;
    }
    return result;
}
 
function reflectAntiDiag(queens: number[], n: number): number[] {
    const result: number[] = new Array(n);
    for (let r = 0; r < n; r++) {
        result[n - 1 - queens[r]] = n - 1 - r;
    }
    return result;
}

Total vs Distinct Solutions
N	All Solutions	Distinct (Symmetry)	Ratio
4	2	1	2.0
5	10	2	5.0
6	4	1	4.0
7	40	6	6.67
8	92	12	7.67
9	352	46	7.65
10	724	92	7.87

When Ratio Isn't 8

Summary: Constraint Checking Mastery

We've covered the full spectrum of constraint checking for N-Queens:

Key Takeaways

•Three Constraints — Row (free by construction), column (simple check), diagonal (mathematical property).
•Diagonal Mathematics — Main diagonal: r-c constant. Anti-diagonal: r+c constant. These identifiers enable O(1) checking.
•O(1) Detection — Use hash sets or boolean arrays to check all constraints in constant time.
•Bitwise Approach — For maximum speed, use bitmasks to check all constraints in a single operation.
•Advanced Pruning — Forward checking, arc consistency, and heuristics can reduce nodes visited at the cost of per-node overhead.
•Symmetry Breaking — Exploit board symmetries to reduce search space or count distinct solutions.

What's Next:

Page Complete

3 / 4