Non-Attacking Queens

Tags

Non-Attacking Queens

Category

Recursion

Difficulty

Very Hard

Problem Statement

Given a positive integer n, find the number of ways to place n queens on an n x n chessboard such that no two queens attack each other. Two queens attack each other if they share the same row, column, or diagonal. This is the classic N-Queens counting problem.

Intuition

Since each row must contain exactly one queen (otherwise two queens would share a row), we can build solutions row by row. For each row, we try placing a queen in each column and check if it conflicts with previously placed queens. The constraints to check are: no two queens in the same column, no two queens on the same diagonal (row - col), and no two queens on the same anti-diagonal (row + col). By using sets to track occupied columns and diagonals, each placement check is O(1).

Approach

  1. Process one row at a time, starting from row 0.
  2. Maintain three sets: columns (occupied columns), diagonals (occupied row - col values), and antiDiagonals (occupied row + col values).
  3. For each row, try placing a queen in each column 0 to n-1:
    • If the column, diagonal, and anti-diagonal are all free, place the queen.
    • Add the column, diagonal, and anti-diagonal to their respective sets.
    • Recurse to the next row.
    • Backtrack: remove the column, diagonal, and anti-diagonal from their sets.
  4. When row equals n, a valid arrangement has been found; increment the count.
  5. Return the total count.

Pseudocode

function nonAttackingQueens(n):
    return solve(0, n, set(), set(), set())

function solve(row, n, columns, diagonals, antiDiagonals):
    if row == n:
        return 1

    count = 0
    for col from 0 to n - 1:
        diag = row - col
        antiDiag = row + col

        if col in columns or diag in diagonals or antiDiag in antiDiagonals:
            continue

        columns.add(col)
        diagonals.add(diag)
        antiDiagonals.add(antiDiag)

        count += solve(row + 1, n, columns, diagonals, antiDiagonals)

        columns.remove(col)
        diagonals.remove(diag)
        antiDiagonals.remove(antiDiag)

    return count

Optimized with bitmask:

function nonAttackingQueens(n):
    return solve(0, n, 0, 0, 0)

function solve(row, n, colMask, diagMask, antiDiagMask):
    if row == n:
        return 1

    count = 0
    availableMask = ((1 << n) - 1) & ~(colMask | diagMask | antiDiagMask)

    while availableMask > 0:
        bit = availableMask & (-availableMask)  # lowest set bit
        availableMask -= bit

        count += solve(row + 1, n,
                       colMask | bit,
                       (diagMask | bit) << 1,
                       (antiDiagMask | bit) >> 1)

    return count

Time & Space Complexity

  • Time: O(n!) in the upper bound. The first row has n choices, the second has at most n-1, and so on. The actual number of valid placements explored is much less due to diagonal constraints pruning branches early. No polynomial-time algorithm is known.
  • Space: O(n) for the recursion stack and the constraint sets/bitmasks.

Key Insights

  • Row-by-row placement inherently prevents row conflicts, reducing the problem to checking columns and diagonals only.
  • The diagonal identity row - col is constant along every top-left to bottom-right diagonal; row + col is constant along every top-right to bottom-left diagonal.
  • Bitmask representation replaces hash set lookups with bitwise operations, providing a significant constant-factor speedup.
  • The problem exhibits no polynomial structure; backtracking with pruning is the standard approach.
  • Known solutions for small n: n=1:1, n=2:0, n=3:0, n=4:2, n=5:10, n=6:4, n=7:40, n=8:92.
  • Symmetry optimizations (reflecting/rotating the board) can cut the search space roughly by a factor of 8, but the implementation becomes more complex.

Edge Cases

  • n = 1: exactly 1 solution (the single queen on the single cell).
  • n = 2 or n = 3: no valid arrangement exists, return 0.
  • n = 0: typically return 1 (the empty board is a valid arrangement with 0 queens).
  • Large n (e.g., n > 15): runtime grows very fast; bitmask optimization and symmetry breaking become important for practical computation.

Linked mentions