Constraint Satisfaction: N-Queens and Sudoku

Place eight queens on a chessboard so that no two queens attack each other. This puzzle, first posed in 1848, is the poster child for a family of problems called constraint satisfaction: you must assign values to a set of variables while obeying a collection of rules that restrict which combinations are allowed. The N-Queens problem generalizes it to an n×n board with n queens. Sudoku is another classic member of the same family. Both yield beautifully to backtracking once you organize the constraints properly.

Why N-Queens Is a Constraint Satisfaction Problem

LeetCode 51 presents the full version: a queen attacks along its row, its column, and both diagonals. So the constraints are:

• No two queens share a row.
• No two queens share a column.
• No two queens share a diagonal (either direction).

You need to place exactly n queens on an n×n board satisfying all three constraints simultaneously. A brute-force approach would consider all ways to place n queens among n² cells, but that is astronomically large. The trick is to eliminate one constraint by construction, then track the remaining constraints efficiently.

The Row-by-Row Approach

Since you must place exactly n queens and no two can share a row, place exactly one queen in each row. This eliminates row conflicts entirely by construction. The problem reduces to choosing, for each row, which column to place the queen in, subject to the column and diagonal constraints.

You process rows in order: row 0, row 1, row 2, and so on. For each row, you try every column from 0 to n-1. If the column is free and both diagonals are free, you place the queen and move on to the next row. If you reach a row where no column works, you backtrack to the previous row and try its next available column.

Tracking Constraints with Sets

You need to check column and diagonal conflicts in $O(1)$ time. Three sets accomplish this.

The cols set tracks which columns already have a queen. If column c is in cols, you cannot place another queen in column c.

The diagonal constraint is trickier. On a diagonal going from top-left to bottom-right, every cell shares the same value of r - c. On a diagonal going from top-right to bottom-left, every cell shares the same value of r + c. So you maintain a diag set holding r - c values for placed queens, and an anti_diag set holding r + c values.

When you try to place a queen at (r, c), you check three conditions: c not in cols, r - c not in diag, and r + c not in anti_diag. If all three pass, you add the values to the respective sets, recurse, and then remove them on backtrack.

Walking Through a 4×4 Board

Let us trace through N-Queens on a 4×4 board to see backtracking in action.

Row 0: try column 0. No conflicts. Place queen at (0, 0). cols = {0}, diag = {0}, anti = {0}.

Row 1: try column 0 — blocked by cols. Try column 1 — r - c = 0, blocked by diag. Try column 2. c = 2 not in cols, r - c = -1 not in diag, r + c = 3 not in anti. Place queen at (1, 2). cols = {0, 2}, diag = {0, -1}, anti = {0, 3}.

Row 2: try column 0 — blocked by cols. Try column 1 — r + c = 3, blocked by anti. Try column 2 — blocked by cols. Try column 3 — r - c = -1, blocked by diag. All columns fail. Backtrack.

Back at row 1: remove (1, 2). Try column 3. c = 3 not in cols, r - c = -2 not in diag, r + c = 4 not in anti. Place queen at (1, 3). cols = {0, 3}, diag = {0, -2}, anti = {0, 4}.

Row 2: try column 0 — blocked by cols. Try column 1. c = 1 not in cols, r - c = 1 not in diag, r + c = 3 not in anti. Place queen at (2, 1). cols = {0, 1, 3}, diag = {0, -2, 1}, anti = {0, 4, 3}.

Row 3: try column 0 — blocked by cols. Try column 1 — blocked by cols. Try column 2. c = 2 not in cols, r - c = 1 — blocked by diag. Try column 3 — blocked by cols. All fail. Backtrack.

Back at row 2: remove (2, 1). Try column 2. r - c = 0, blocked by diag. Try column 3 — blocked by cols. All fail. Backtrack again.

Back at row 1: remove (1, 3). All columns tried. Backtrack to row 0.

Back at row 0: remove (0, 0). Try column 1. Place queen at (0, 1). cols = {1}, diag = {-1}, anti = {1}.

Row 1: try column 0 — r + c = 1, blocked by anti. Try column 1 — blocked by cols. Try column 2 — r - c = -1, blocked by diag. Try column 3. c = 3 not in cols, r - c = -2 not in diag, r + c = 4 not in anti. Place (1, 3). cols = {1, 3}, diag = {-1, -2}, anti = {1, 4}.

Row 2: try column 0. c = 0 clear, r - c = 2 clear, r + c = 2 clear. Place (2, 0). cols = {0, 1, 3}, diag = {-1, -2, 2}, anti = {1, 4, 2}.

Row 3: try column 0 — blocked by cols. Try column 1 — blocked by cols. Try column 2. c = 2 clear, r - c = 1 — not in diag, r + c = 5 — not in anti. Place (3, 2). We have filled all 4 rows. This is a valid solution: queens at (0,1), (1,3), (2,0), (3,2).

The board looks like:

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

Code: N-Queens

def solve_n_queens(n):
    cols, diag, anti = set(), set(), set()
    board = [["."] * n for _ in range(n)]
    results = []

    def backtrack(r):
        if r == n:
            results.append(["".join(row) for row in board])
            return
        for c in range(n):
            if c in cols or (r - c) in diag or (r + c) in anti:
                continue
            cols.add(c)
            diag.add(r - c)
            anti.add(r + c)
            board[r][c] = "Q"
            backtrack(r + 1)
            board[r][c] = "."
            cols.discard(c)
            diag.discard(r - c)
            anti.discard(r + c)

    backtrack(0)
    return results

The structure follows a clean pattern: try a candidate, add its constraints, recurse, then undo everything on the way back. That undo step — restoring the board cell to "." and removing values from the sets — is the backtracking.

If you only need the count of solutions rather than the actual board configurations, you can replace the results list with a counter. The backtracking logic is identical; you just increment the counter at the base case instead of saving the board.

Sudoku Solver: Same Framework, Different Constraints

LeetCode 37 shows that Sudoku fits the same template perfectly. You have a 9×9 grid partially filled with digits 1 through 9. Each row, each column, and each 3×3 box must contain every digit exactly once. The backtracking approach finds the next empty cell, tries each digit from 1 to 9, checks the constraints, and recurses.

The constraints are analogous to N-Queens. Where N-Queens has cols, diag, and anti_diag, Sudoku has row_sets, col_sets, and box_sets. For a cell at position (r, c), the box index is computed as (r // 3) * 3 + (c // 3). This formula maps each of the nine 3×3 regions to a unique index from 0 to 8.

def solve_sudoku(board):
    rows = [set() for _ in range(9)]
    cols = [set() for _ in range(9)]
    boxes = [set() for _ in range(9)]

    # Initialize constraint sets from the given board
    for r in range(9):
        for c in range(9):
            if board[r][c] != ".":
                d = board[r][c]
                rows[r].add(d)
                cols[c].add(d)
                boxes[(r // 3) * 3 + (c // 3)].add(d)

    def backtrack(pos):
        # Find the next empty cell starting from pos
        while pos < 81:
            r, c = divmod(pos, 9)
            if board[r][c] == ".":
                break
            pos += 1
        if pos == 81:
            return True  # all cells filled

        r, c = divmod(pos, 9)
        box_id = (r // 3) * 3 + (c // 3)
        for d in "123456789":
            if d in rows[r] or d in cols[c] or d in boxes[box_id]:
                continue
            board[r][c] = d
            rows[r].add(d)
            cols[c].add(d)
            boxes[box_id].add(d)
            if backtrack(pos + 1):
                return True
            board[r][c] = "."
            rows[r].discard(d)
            cols[c].discard(d)
            boxes[box_id].discard(d)
        return False

    backtrack(0)

The structure mirrors N-Queens almost exactly. The main differences are the shape of the search (iterating over cells rather than rows) and the number of constraint sets (three families of nine sets each, rather than three single sets).

Bit Masks as an Alternative to Sets

For competitive programming or performance-critical implementations, you can replace the sets with integer bit masks. Each bit position represents a digit (for Sudoku) or a column/diagonal index (for N-Queens). Checking whether a value is used becomes a bitwise AND, and adding or removing a value becomes a bitwise OR or XOR.

For Sudoku, you might keep row_mask[r], col_mask[c], and box_mask[b] as 9-bit integers. To find which digits are available for cell (r, c), compute ~(row_mask[r] | col_mask[c] | box_mask[b]) & 0x1FF. Each set bit in the result is a candidate digit. You can iterate over set bits efficiently, and the constraint check is a single bitwise operation rather than three hash lookups.

For N-Queens, bit masks are especially elegant. You can encode which columns and diagonals are attacked and use bit tricks to enumerate available positions, but the set-based approach is already plenty fast for the typical n <= 15 range seen in interviews.

The General Constraint Satisfaction Pattern

Both N-Queens and Sudoku follow the same skeleton:

Find the next empty slot. For N-Queens, it is the next row. For Sudoku, it is the next cell with a dot. Generate candidate values for that slot. For N-Queens, candidates are columns 0 through n-1. For Sudoku, candidates are digits 1 through 9. For each candidate, check it against all constraints. If it passes, place it, update the constraint data structures, and recurse to the next slot. If the recursion returns failure, undo the placement and try the next candidate. If no candidate works, return failure to trigger backtracking in the caller.

This template generalizes to any constraint satisfaction problem: crossword construction, graph coloring, register allocation, and more. The art lies in choosing a good variable ordering (which slot to fill next) and good constraint representations (how to check validity quickly). N-Queens and Sudoku are the clearest examples because the constraints have clean mathematical structure.

Complexity Analysis

For N-Queens, the time complexity is $O(n!)$. In row 0 you have n column choices. In row 1, at most n-1 columns are available (one is blocked by the column constraint, and diagonal constraints may block more). In row 2, at most n-2, and so on. The total work is bounded by n × (n-1) × (n-2) × ... = n!. In practice, diagonal constraints prune aggressively, so the actual search tree is much smaller.

For Sudoku, the theoretical worst case is exponential — up to 9^(number of empty cells) — but real Sudoku puzzles are designed to have a unique solution, and the constraint checking prunes the vast majority of branches. Well-structured solvers finish near-instantly on any valid Sudoku puzzle.

Space complexity for both problems is $O(n²)$ for the board representation. The constraint sets and recursion stack add $O(n)$ for N-Queens and $O(81)$ = $O(1)$ for Sudoku since the board size is fixed.

Recognizing this pattern

You're probably looking at constraint satisfaction backtracking when:

• You need to fill a grid subject to row, column, diagonal, or region constraints.
• The board is small and fixed-size — 9x9 Sudoku, n-by-n with n ≤ 15 for N-Queens.
• Each cell or slot has a small finite set of candidate values to try.
• Phrases like "valid configuration", "place k items", "no two share a row/column/diagonal" appear.

Common templates:

• Row-by-row queen placement — recurse per row, try each column, track column and diagonal sets. Example: N-Queens.
• Count-only search — same recursion but return an integer count instead of building boards. Example: N-Queens II.
• Next-empty-cell solver — find next ., try digits 1-9, check row/col/box, recurse. Example: Sudoku Solver.
• Constraint-set validation — use bitmasks or hash sets per row/col/region for O(1) feasibility checks. Example: Valid Sudoku.