N-Queens

Place N queens on an N×N chessboard so no two queens attack each other. The classic backtracking solution places one queen per row, tries each column, and uses constraint pruning to skip illegal placements. This lesson covers the algorithm, isSafe checks, LeetCode 51/52, and implementations in C, Java, and Python with trace tables.

Overview

A queen attacks any square in the same row, column, or diagonal. With one queen per row, we only need to pick a column for each row and verify no conflict with previous queens.

N = 4 — Solution 1 (cols per row: 1, 3, 0, 2)

  0 1 2 3
0 . Q . .
1 . . . Q
2 Q . . .
3 . . Q .

Backtrack row-by-row; prune when column/diagonal conflicts

Problem Statement

Input: Integer n (board size n×n).

Output:

• All solutions (LeetCode 51): Every valid board configuration.
• Count only (LeetCode 52): Number of distinct solutions.

Constraints: Exactly one queen per row and column; no shared diagonals.

Known counts: n=1 → 1, n=2 → 0, n=3 → 0, n=4 → 2, n=8 → 92.

Backtracking Algorithm

1. Process rows 0 … n-1 one at a time.
2. For current row, try each column 0 … n-1.
3. If isSafe(row, col), place queen and recurse to next row.
4. When row == n, record solution; backtrack and try next column.
5. Remove queen (implicitly by overwriting on return) — classic choose/explore/unchoose.

The isSafe Check

Store queen columns in cols[row]. For candidate (row, col), reject if:

• Same column: cols[r] == col for any r < row
• Same diagonal: |cols[r] - col| == row - r

O(1) sets variant: Track used columns, positive diagonals row - col, and negative diagonals row + col in hash sets for faster checks on large n.

Code (C, Java, Python)

Python

def solve_n_queens(n):
    """All N-Queens boards — row-by-row backtracking with isSafe prune."""
    cols = [-1] * n
    result = []

    def is_safe(row, col):
        for r in range(row):
            if cols[r] == col:
                return False
            if abs(cols[r] - col) == row - r:
                return False
        return True

    def backtrack(row):
        if row == n:
            board = []
            for c in cols:
                board.append("." * c + "Q" + "." * (n - c - 1))
            result.append(board)
            return
        for col in range(n):
            if not is_safe(row, col):
                continue
            cols[row] = col
            backtrack(row + 1)
            cols[row] = -1

    backtrack(0)
    return result


if __name__ == "__main__":
    sols = solve_n_queens(4)
    print(len(sols))  # 2

Java

import java.util.ArrayList;
import java.util.List;

public class NQueens {

    /** Constraint pruning before placing queen at (row, col). */
    private static boolean isSafe(int[] cols, int row, int col) {
        for (int r = 0; r < row; r++) {
            if (cols[r] == col) return false;
            if (Math.abs(cols[r] - col) == row - r) return false;
        }
        return true;
    }

    public static void solve(int n, int row, int[] cols, List<int[]> result) {
        if (row == n) {
            result.add(cols.clone());
            return;
        }
        for (int col = 0; col < n; col++) {
            if (!isSafe(cols, row, col)) continue;
            cols[row] = col;
            solve(n, row + 1, cols, result);
        }
    }

    public static void main(String[] args) {
        List<int[]> result = new ArrayList<>();
        solve(4, 0, new int[4], result);
        System.out.println(result.size()); // 2
    }
}

C

#include <stdio.h>
#include <stdlib.h>

int is_safe(int cols[], int row, int col) {
    int r;
    for (r = 0; r < row; r++) {
        if (cols[r] == col) return 0;
        if (abs(cols[r] - col) == row - r) return 0;
    }
    return 1;
}

void n_queens(int n, int row, int cols[], int *count) {
    int col;
    if (row == n) { (*count)++; return; }
    for (col = 0; col < n; col++) {
        if (!is_safe(cols, row, col)) continue;
        cols[row] = col;
        n_queens(n, row + 1, cols, count);
    }
}

int main(void) {
    int n = 4, cols[4], count = 0;
    n_queens(n, 0, cols, &count);
    printf("%d\n", count); /* 2 */
    return 0;
}

Output & Trace

Solutions for n = 4

Partial trace — row-by-row for n = 4

Solution counts by n

LeetCode 51 & 52

Optimizations

• Column/diagonal sets: O(1) conflict check instead of scanning all previous rows.
• Bitmask DP: Advanced counting for large n (beyond interview scope).
• Symmetry breaking: Fix first queen column and mirror to avoid duplicate work in counting problems.

Approach Comparison

Real-Life Applications

Interview Tips

1. State: one queen per row → only choose column per row.
2. Write isSafe clearly: column equality + diagonal |cols[r]-col| == row-r.
3. For LC 52, say you only increment a counter — skip building boards.
4. Mention set-based O(1) checks if asked to optimize.
5. Walk through n=4 on the whiteboard — 2 solutions is easy to verify.
6. Connect to pruning techniques and Sudoku.