Speeding Up the N-Queens Backtracking Solver with O(1) Diagonal Checks and Boolean Occupancy

Why two similar N-Queens backtracking solvers differ: replace O(n) diagonal scans with O(1) boolean occupancy lookups for faster, scalable search in Python.

Two N-Queens solvers can look almost identical and yet behave very differently at scale. The subtlety often hides in how conflicts are detected during the search. Here’s a clear look at where the real cost lies and how a tiny change in representation turns a seemingly similar backtracking routine into a meaningfully faster one.

Example that triggers the confusion

The following solver places queens column by column, backtracks on conflicts, and checks diagonal clashes by scanning already placed queens. It does the job, but the diagonal check costs extra work on every step.

# Basic N-Queens search with linear-time diagonal checks
def safe_cell(state, try_r, try_c):
    for idx in range(len(state)):
        prev_r = state[idx]
        prev_c = idx + 1
        if abs(prev_r - try_r) == abs(prev_c - try_c):
            return False
    return True
def place(col_idx, size, state, outputs, row_taken):
    if col_idx > size:
        outputs.append(state.copy())
        return
    for r in range(1, size + 1):
        if not row_taken[r]:
            if safe_cell(state, r, col_idx):
                row_taken[r] = True
                state.append(r)
                place(col_idx + 1, size, state, outputs, row_taken)
                state.pop()
                row_taken[r] = False
def solve_basic(size):
    out = []
    st = []
    used = [False] * (size + 1)
    place(1, size, st, out, used)
    return out
if __name__ == "__main__":
    n = 4
    sols = solve_basic(n)
    for s in sols:
        print(s)

What’s really different

Both implementations perform backtracking and prune as soon as a conflict appears. The distinction is not in the recursion scheme but in the cost of detecting a diagonal conflict. In the basic version, diagonal clashes are discovered by iterating over all previously placed queens. Each check examines up to O(n) items, which means every candidate square incurs a linear-time check before the algorithm can proceed or backtrack.

The faster approach replaces this scan with constant-time lookups. It maintains two boolean containers for diagonals so that a single array access answers whether a diagonal is already occupied. That single change removes the per-check linear cost and shifts the dominant complexity from O(n! * n) down to O(n!), aligning with the idea that the search tree size drives the runtime, not the conflict detection overhead.

Backtracking with O(1) diagonal checks

Here is an equivalent solver that uses precomputed occupancy for rows and both diagonal families. The indices used to map diagonals are the same as in the example above: row + col for one direction and row - col + n for the other, and the storage is sized accordingly.

# N-Queens with constant-time diagonal checks (pruning by occupancy)
def dfs(col_idx, size, state, row_busy, diag_a, diag_b, out):
    if col_idx > size:
        out.append(state[:])
        return
    for r in range(1, size + 1):
        if not row_busy[r] and not diag_a[r + col_idx] and not diag_b[r - col_idx + size]:
            row_busy[r] = True
            diag_a[r + col_idx] = True
            diag_b[r - col_idx + size] = True
            state.append(r)
            dfs(col_idx + 1, size, state, row_busy, diag_a, diag_b, out)
            state.pop()
            diag_b[r - col_idx + size] = False
            diag_a[r + col_idx] = False
            row_busy[r] = False
def solve_fast(size):
    out = []
    state = []
    row_busy = [False] * (size + 1)
    diag_a = [False] * (2 * size + 1)
    diag_b = [False] * (2 * size + 1)
    dfs(1, size, state, row_busy, diag_a, diag_b, out)
    return out
if __name__ == "__main__":
    n = 4
    sols = solve_fast(n)
    for s in sols:
        print(s)

Why this matters

When the search explores a factorial number of placements, any extra factor inside the inner loop multiplies dramatically. Replacing a per-candidate O(n) scan with an O(1) lookup is the difference between O(n! * n) and O(n!) in practice. Both versions prune, both backtrack early on conflicts, and both build solutions incrementally; the speedup comes from eliminating the repeated diagonal scans.

Takeaways

The core lesson is to keep constraint checks constant-time whenever the structure allows it. In this case, tracking occupied rows and diagonals with simple boolean storage turns conflict detection into a few array accesses. The search strategy doesn’t need to change; minimizing validation cost per step is enough to move the runtime to a more favorable bound.