N-Queens

Problem

Return how many distinct N-queens solutions exist for an n×n board.

Constraints

• 1 ≤ n ≤ 9

Approach — Backtracking

This is a Backtracking problem. The idea: build candidates one choice at a time and abandon a branch the moment it can't lead to a valid answer. Work through the reference code below line by line, then re-derive it yourself in the editor — that's how the pattern sticks.

Complexity: exponential worst case.

Solution code

Python

class Solution:
    def totalNQueens(self, n):
        cols = set()
        diag = set()
        anti = set()
        def place(r):
            if r == n:
                return 1
            total = 0
            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)
                total += place(r + 1)
                cols.remove(c); diag.remove(r - c); anti.remove(r + c)
            return total
        return place(0)

Java

class Solution {
    int count = 0;
    public int totalNQueens(int n) {
        bt(0, n, 0, 0, 0);
        return count;
    }
    private void bt(int row, int n, int cols, int diag1, int diag2) {
        if (row == n) { count++; return; }
        int available = ((1 << n) - 1) & ~(cols | diag1 | diag2);
        while (available != 0) {
            int p = available & -available;
            available ^= p;
            bt(row + 1, n, cols | p, (diag1 | p) << 1, (diag2 | p) >> 1);
        }
    }
}

Practice it

Reading a solution isn't the same as being able to write it under pressure. Open this problem in the in-browser editor, hide the solution, and solve it from scratch — your code runs against real test cases instantly.