N-Queens

The problem

Place n queens on an n × n chessboard so that no two queens attack each other (no two share a row, column or diagonal). Return every distinct solution, each drawn as a list of strings with Q for a queen and . for an empty square.

The key insight

Every row must hold exactly one queen, so place them one row at a time. For each row try each column, but only if that column and both diagonals are free. Cells on the same "\" diagonal share row - col; cells on the same "/" diagonal share row + col. Three sets make each safety check O(1), and a dead end immediately undoes the last queen.

Step-by-step approach

1. Keep sets cols, diag (row - col) and anti (row + col), plus queens, the column chosen in each row.
2. Define dfs(row): if row == n, convert queens into a board and record it.
3. For each column c, skip it if c, row - c or row + c is already taken.
4. Otherwise add all three, append c, recurse on row + 1, then remove them (backtrack).
5. Call dfs(0).

Python solution

def solve_n_queens(n):
    out, queens = [], []                    # queens[r] = column in row r
    cols, diag, anti = set(), set(), set()

    def dfs(row):
        if row == n:
            out.append(["." * c + "Q" + "." * (n - c - 1) for c in queens])
            return
        for c in range(n):
            if c in cols or row - c in diag or row + c in anti:
                continue                    # attacked: prune
            cols.add(c); diag.add(row - c); anti.add(row + c)
            queens.append(c)
            dfs(row + 1)
            queens.pop()
            cols.remove(c); diag.remove(row - c); anti.remove(row + c)

    dfs(0)
    return out

Complexity

Row r has at most n - r free columns, so the search is bounded by n!, and pruning on diagonals makes it far smaller. The sets and recursion hold O(n) entries (plus O(n²) per stored board).

Common mistakes

• Checking only columns and forgetting one of the two diagonals.
• Using row + col for both diagonals; the other one needs row - col.
• Forgetting to remove a queen's entries from all three sets when backtracking.

Frequently asked questions

Related problems