N-QueensN-queens

01Why it exists

Reach for it when you see:Nothing may clash, one per row and one per column, timetabling and rotas, constraint satisfaction, a check after each placement, going back a step when stuck, Sudoku.

02The core idea

N-Queens asks you to place n queens on an n×n board so that no two of them share a row, a column or a diagonal. The first insight is exactly one queen per row: since two queens cannot share a row and there are n of them, every row holds precisely one, so the only decision left is which column the queen in row r takes. The search space shrinks from "choose any n squares" to "choose one column per row", which is a very different size of problem.

The second insight is that the conflict check has to be O(1). Squares in the same column share the same c; squares on the same "\" diagonal share the same r−c; squares on the same "/" diagonal share the same r+c. Keep three sets holding the c, r−c and r+c of the queens already placed, and deciding whether a square is safe is three lookups. Placing a queen adds all three values, and taking it back has to remove all three — miss one and every later branch reads the board wrongly.

The search itself is backtracking's three steps: for each column c of row r, skip the square if it is attacked (pruning), otherwise make the choice, recurse into row r+1, and undo. If every column of row r+1 is attacked, the recursion simply returns, and that is the moment of backtracking: lift the queen off row r and move it to the next column. The whole thing is a DFS over a tree of depth n whose branching factor at each node is the number of columns in that row not yet under attack.

The cost is exponential, with a loose upper bound of O(n!), although pruning brings the real figure far below that: 8 queens has 92 solutions and the search visits roughly two thousand nodes. When you only need the count and not the boards themselves, bitmasks can replace the sets: bit c of each of three integers says whether column c is attacked, and moving to the next row shifts the whole "\" mask one place left and the "/" mask one place right. This is the fastest way to write N-Queens, and it is the textbook example of using an integer as a set.

03The algorithm

1. 1Set up queens (the column used by each row) and three sets: cols, diag1 (r−c) and diag2 (r+c). dfs(r) means "currently filling row r".
2. 2Base case: r == n means all n rows are filled, so turn queens into a board and add it to the answers.
3. 3For each column c: if c in cols or r-c in diag1 or r+c in diag2, the square is attacked, so skip it.
4. 4Make the choice: queens.append(c), add one value to each of the three sets, and recurse with dfs(r + 1).
5. 5Undo the choice: queens.pop() and remove one value from each of the three sets. When every column of this row has been tried without success, the call simply returns to the previous row — and that is backtracking.

04Interactive demo

Four queens, filled one row at a time. A pale yellow square is attacked by a queen already on the board, and every time the search lands on an attacked square it says which constraint was violated. When every column of a row is attacked, the queen on the row above is lifted and moved to its next column, and so on until the first solution appears.

05Code

The set-based version that lists every solution, and the bitmask version that only counts them.

# N-Queens (LeetCode 51): one row at a time, three sets tracking the attacked columns and diagonals
def solve_n_queens(n):
    ans = []
    queens = []                  # queens[r] = the column of the queen in row r
    cols = set()                 # columns already taken
    diag1 = set()                # cells with the same r - c lie on the same "\" diagonal
    diag2 = set()                # cells with the same r + c lie on the same "/" diagonal

    def dfs(r):
        if r == n:               # every row has its queen
            ans.append(["." * c + "Q" + "." * (n - c - 1) for c in queens])
            return
        for c in range(n):
            if c in cols or (r - c) in diag1 or (r + c) in diag2:
                continue         # attacked, so prune it
            queens.append(c)     # make the choice
            cols.add(c); diag1.add(r - c); diag2.add(r + c)
            dfs(r + 1)
            queens.pop()         # undo the choice: all three sets must be restored
            cols.remove(c); diag1.remove(r - c); diag2.remove(r + c)

    dfs(0)
    return ans


# Counting solutions only (LeetCode 52): bitmasks instead of sets
# cols / d1 / d2 are n-bit integers; bit c set means column c of this row is attacked
def total_n_queens(n):
    full = (1 << n) - 1

    def dfs(cols, d1, d2):
        if cols == full:                     # every column holds a queen
            return 1
        count = 0
        free = full & ~(cols | d1 | d2)      # the squares still open in this row
        while free:
            bit = free & -free               # take the lowest set bit
            free ^= bit
            # next row: the \ diagonals move one column right (<< 1), the / diagonals one column left (>> 1)
            count += dfs(cols | bit, ((d1 | bit) << 1) & full, (d2 | bit) >> 1)
        return count

    return dfs(0, 0, 0)


if __name__ == "__main__":
    for row in solve_n_queens(4)[0]:
        print(row)                           # .Q.. / ...Q / Q... / ..Q.
    print(total_n_queens(8))                 # 92

06Practice

• LeetCode 36Valid Sudoku (practise the conflict check first)Medium
• LeetCode 473Matchsticks to Square (every matchstick joins one of four sides; sort, then prune)Medium
• LeetCode 51N-QueensHard
• LeetCode 52N-Queens II (bitmasks)Hard
• LeetCode 37Sudoku Solver (three sets: rows, columns and boxes)Hard
• LeetCode 1655Distribute Repeating Integers (constraint satisfaction plus pruning)Hard