N Queens

HARD✓ CHIP-TIMEDLC #51 — FULL STATEMENT ↗

The drill: Place n queens on an n×n board so no two attack each other — no shared row, column, or diagonal — and return every arrangement as a board of dots and queens.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

A board size n arrives, and the drill is to place n queens on an n×n board so that no two ever attack each other — no shared row, no shared column, and no shared diagonal in either direction.

Every valid arrangement should be returned as a full board: one queen character marking each occupied square and a filler character everywhere else, one board string per row.

There can be many valid arrangements for a given n, or none at all for small boards — every distinct arrangement found should be included, and no partial or attacking arrangement should ever appear.

EX 01

n = 1

→ [["Q"]]

MINIMUM SIZE, ONE QUEEN ALONE

EX 02

n = 2

→ []

NO PLACEMENT ESCAPES ATTACK ON A 2X2 BOARD

EX 03

n = 3

→ []

STILL NO VALID PLACEMENT ON A 3X3 BOARD

n is small, typically under ten, since arrangements grow combinatorially
exactly one queen sits in each of the n rows and n columns overall
no two queens may share a row, column, or either diagonal
every valid full board is returned, in any order

THE HINTS — TAKE ONLY WHAT YOU NEED

HINT 1 THE NUDGE

Every row can hold exactly one queen without instantly conflicting with itself, so the placement is really a choice of one column per row. What does that turn the search into?

HINT 2 THE STRUCTURE

Track which columns and which of the two diagonal directions are already covered — one diagonal direction is constant along row−col, the other along row+col. A square is safe only when none of those three sets already contains it.

HINT 3 ONE STEP FROM THE ANSWER

Backtrack row by row: try every open column in the current row, mark its column and both diagonals used, recurse to the next row, then undo the marks before trying the next column. Reaching row n with no conflicts is a finished board.

COACH'S BOARD — THE PATTERN, STEP BY STEP

THE DIAGONAL WATCHPATTERN · BACKTRACKING — COLUMN & DIAGONAL SETSn = 4 · one queen per row

STEP 1

n = 4. Place one queen per row, testing column and both diagonal sets before ever committing a square.

STEP 1 / 11 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

grind/n-queens.py — RACE PACE

LANG ▸

PACE ▸

class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        results = []
        cols_used = set()
        diag1_used = set()  # constant along row - col
        diag2_used = set()  # constant along row + col
        placement = [0] * n

        def backtrack(row: int) -> None:
            if row == n:
                results.append(["." * c + "Q" + "." * (n - c - 1) for c in placement])
                return
            for col in range(n):
                if col in cols_used or (row - col) in diag1_used or (row + col) in diag2_used:
                    continue
                cols_used.add(col)
                diag1_used.add(row - col)
                diag2_used.add(row + col)
                placement[row] = col
                backtrack(row + 1)
                cols_used.remove(col)
                diag1_used.remove(row - col)
                diag2_used.remove(row + col)

        backtrack(0)
        return results

TIME O(N!)SPACE O(N)PYTHON · RACE PACE · 26 LN

class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        results = []

        def is_safe(cols: List[int]) -> bool:
            for r1 in range(len(cols)):
                for r2 in range(r1 + 1, len(cols)):
                    if abs(cols[r1] - cols[r2]) == abs(r1 - r2):
                        return False
            return True

        def to_board(cols: List[int]) -> List[str]:
            return ["." * c + "Q" + "." * (n - c - 1) for c in cols]

        def permute(chosen: List[int], remaining: List[int]) -> None:
            if not remaining:
                if is_safe(chosen):
                    results.append(to_board(chosen))
                return
            for i in range(len(remaining)):
                permute(chosen + [remaining[i]], remaining[:i] + remaining[i + 1:])

        permute([], list(range(n)))
        return results

TIME O(N! · N²)SPACE O(N)PYTHON · TRAINING PACE · 24 LN

class Solution {
    private int n;
    private final Set<Integer> colsUsed = new HashSet<>();
    private final Set<Integer> diag1Used = new HashSet<>(); // row - col
    private final Set<Integer> diag2Used = new HashSet<>(); // row + col
    private int[] placement;
    private List<List<String>> results;

    public List<List<String>> solveNQueens(int n) {
        this.n = n;
        this.placement = new int[n];
        this.results = new ArrayList<>();
        backtrack(0);
        return results;
    }

    private void backtrack(int row) {
        if (row == n) {
            List<String> board = new ArrayList<>();
            for (int c : placement) {
                StringBuilder sb = new StringBuilder();
                for (int i = 0; i < n; i++) {
                    sb.append(i == c ? 'Q' : '.');
                }
                board.add(sb.toString());
            }
            results.add(board);
            return;
        }
        for (int col = 0; col < n; col++) {
            if (colsUsed.contains(col) || diag1Used.contains(row - col) || diag2Used.contains(row + col)) {
                continue;
            }
            colsUsed.add(col);
            diag1Used.add(row - col);
            diag2Used.add(row + col);
            placement[row] = col;
            backtrack(row + 1);
            colsUsed.remove(col);
            diag1Used.remove(row - col);
            diag2Used.remove(row + col);
        }
    }
}

TIME O(N!)SPACE O(N)JAVA · RACE PACE · 44 LN

class Solution {
    public List<List<String>> solveNQueens(int n) {
        List<List<String>> results = new ArrayList<>();
        List<Integer> remaining = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            remaining.add(i);
        }
        permute(n, new ArrayList<>(), remaining, results);
        return results;
    }

    private void permute(int n, List<Integer> chosen, List<Integer> remaining, List<List<String>> results) {
        if (remaining.isEmpty()) {
            if (isSafe(chosen)) {
                results.add(toBoard(n, chosen));
            }
            return;
        }
        for (int i = 0; i < remaining.size(); i++) {
            List<Integer> nextChosen = new ArrayList<>(chosen);
            nextChosen.add(remaining.get(i));
            List<Integer> nextRemaining = new ArrayList<>(remaining);
            nextRemaining.remove(i);
            permute(n, nextChosen, nextRemaining, results);
        }
    }

    private boolean isSafe(List<Integer> cols) {
        for (int r1 = 0; r1 < cols.size(); r1++) {
            for (int r2 = r1 + 1; r2 < cols.size(); r2++) {
                if (Math.abs(cols.get(r1) - cols.get(r2)) == r2 - r1) {
                    return false;
                }
            }
        }
        return true;
    }

    private List<String> toBoard(int n, List<Integer> cols) {
        List<String> rows = new ArrayList<>();
        for (int c : cols) {
            StringBuilder row = new StringBuilder();
            for (int i = 0; i < n; i++) {
                row.append(i == c ? 'Q' : '.');
            }
            rows.add(row.toString());
        }
        return rows;
    }
}

TIME O(N! · N²)SPACE O(N)JAVA · TRAINING PACE · 50 LN

✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED