N-Queens Visualization for Coding Interviews

Backtracking with row/diagonal constraint sets; solution enumeration.

Concept

The N-Queens problem asks you to place N queens on an N by N chessboard so that no two queens attack each other — no two share a row, column, or diagonal. It is the canonical backtracking problem used to teach constraint satisfaction, search tree pruning, and recursion. The solution count grows roughly like n! / exp(n) and is unknown in closed form; for n = 8 there are 92 solutions, for n = 20 there are 39 billion. Efficient solvers rely on three sets or bitmasks to track attacked columns and diagonals, enabling O(1) conflict checks per placement. N-Queens also demonstrates symmetry exploitation — reflecting along the vertical axis halves the work — and shows why pure DFS with pruning is the right tool for enumeration problems over structured combinatorial spaces.

How it works

Place queens one row at a time, so the row constraint is satisfied by construction. For each row, try every column: if placing a queen at (row, col) does not conflict with any already-placed queen, recurse to the next row; otherwise skip. Conflict detection uses three sets: cols tracks used columns, diag1 tracks the 'top-left to bottom-right' diagonals (indexed by row - col, which is constant along such a diagonal), and diag2 tracks 'top-right to bottom-left' diagonals (indexed by row + col). When placing at (row, col), check that col is not in cols, row - col not in diag1, and row + col not in diag2. If clear, add all three markers, recurse, and remove them when backtracking (the restoration step is why backtracking is called backtracking). When row equals n, you have a full solution — record the board layout. A significantly faster variant uses three integers as bitmasks and finds legal placements via bit tricks: at each level, the bitmask of available columns is ~(cols | diag1 | diag2) & mask, and you iterate over its set bits. This drops the enumeration constant so that n = 15 finishes in a fraction of a second.

Implementation

import java.util.*;

public final class NQueens {
    private NQueens() {}

    public static List<List<String>> solveNQueens(int n) {
        List<List<String>> results = new ArrayList<>();
        int[] queens = new int[n];
        Set<Integer> cols = new HashSet<>();
        Set<Integer> diag1 = new HashSet<>();
        Set<Integer> diag2 = new HashSet<>();
        backtrack(0, n, queens, cols, diag1, diag2, results);
        return results;
    }

    private static void backtrack(int row, int n, int[] queens,
                                  Set<Integer> cols, Set<Integer> diag1, Set<Integer> diag2,
                                  List<List<String>> results) {
        if (row == n) {
            results.add(toBoard(queens, n));
            return;
        }
        for (int col = 0; col < n; col++) {
            int d1 = row - col, d2 = row + col;
            if (cols.contains(col) || diag1.contains(d1) || diag2.contains(d2)) continue;
            queens[row] = col;
            cols.add(col); diag1.add(d1); diag2.add(d2);
            backtrack(row + 1, n, queens, cols, diag1, diag2, results);
            cols.remove(col); diag1.remove(d1); diag2.remove(d2);
        }
    }

    private static List<String> toBoard(int[] queens, int n) {
        List<String> board = new ArrayList<>(n);
        for (int r = 0; r < n; r++) {
            char[] row = new char[n];
            Arrays.fill(row, '.');
            row[queens[r]] = 'Q';
            board.add(new String(row));
        }
        return board;
    }

    public static int countSolutions(int n) {
        int[] count = new int[1];
        countHelper(0, 0, 0, 0, n, (1 << n) - 1, count);
        return count[0];
    }

    private static void countHelper(int row, int cols, int d1, int d2, int n, int mask, int[] count) {
        if (row == n) { count[0]++; return; }
        int available = mask & ~(cols | d1 | d2);
        while (available != 0) {
            int bit = available & -available;
            available ^= bit;
            countHelper(row + 1, cols | bit, (d1 | bit) << 1, (d2 | bit) >> 1, n, mask, count);
        }
    }
}

Complexity

• Time: Exponential (bounded by n!)
• Space: O(n) recursion + O(n) conflict sets
• Solutions count (n=8): 92

Common pitfalls

• Forgetting to remove markers on backtrack — future branches see ghost conflicts.
• Using row + col and row - col without normalization — both are fine in sets but d1 can be negative.
• Rebuilding the board string on every recursion — defer stringification to solution time.
• Recomputing conflict checks with O(n) scans per placement instead of O(1) set lookups.
• Counting solutions by collecting them all and taking size — use a counter for speed.

Key design decisions & trade-offs

• Sets vs bitmasks — Chosen: Bitmasks for large n. Shifted masks let you enumerate legal columns in O(popcount) with no hashing overhead.
• All solutions vs count only — Chosen: Count-only when you don't need boards. Avoids allocating strings and lists; 5-10x faster.
• Symmetry exploitation — Chosen: Fix first-row column to left half. Solutions come in mirror pairs; exploring half cuts work roughly in half.

Practice problems

• N-Queens

Interview follow-ups

• Rewrite the solver using the bitmask variant and benchmark against the set version.
• Exploit vertical-axis symmetry to halve search time.
• Solve N-Queens via a SAT or ILP formulation and compare.
• Extend to the N-Rooks or N-Bishops variants.

Why it matters

N-Queens is a core part of the Greedy & Backtracking toolkit. If you are preparing for a technical interview at a top-tier company or teaching a course, a working visualization is the fastest path from "I read about it" to "I understand it".

Related

• Sudoku Solver
• DFS
• Bit Manipulation