N-Queens Problem

Analogy categoryAnalogies

Introduction

The N-Queens problem asks: given an N x N chessboard, place N queens on it so that no two queens attack each other -- meaning no two queens share the same row, column, or diagonal. It is a canonical backtracking problem because it has a natural incremental structure (place one queen per row) and a clean constraint check (no shared column or diagonal), making it an ideal illustration of how pruning transforms an intractable brute-force search into a feasible one.

🏏

Cricket analogy: Placing N fielders on a grid-like field so no two cover the same row, column, or diagonal line of sight is like N-Queens; backtracking places one fielder per row and immediately rejects a spot that clashes with an earlier fielder's line.

Approach/Syntax

python

def solve_n_queens(n):
    solutions = []
    cols = set()
    diag1 = set()  # row - col is constant along a '/' diagonal
    diag2 = set()  # row + col is constant along a '\\' diagonal
    placement = []  # placement[row] = col of queen in that row

    def backtrack(row):
        if row == n:
            solutions.append(placement[:])
            return
        for col in range(n):
            if col in cols or (row - col) in diag1 or (row + col) in diag2:
                continue  # pruned: attacked
            cols.add(col); diag1.add(row - col); diag2.add(row + col)
            placement.append(col)

            backtrack(row + 1)

            placement.pop()
            cols.remove(col); diag1.remove(row - col); diag2.remove(row + col)

    backtrack(0)
    return solutions

Explanation

Because two queens in the same row always attack each other, we only ever need to place exactly one queen per row, which lets the recursion index by row and eliminates one whole dimension of the search. For each row, we try every column and reject it immediately (prune) if that column, or either diagonal passing through the cell, is already occupied by an earlier queen. Tracking occupied columns and diagonals with hash sets makes each validity check O(1): a column index col is unique, a '/' diagonal is identified by the constant row - col, and a '\\' diagonal by the constant row + col. Placing and removing a queen updates all three sets, which is the choose/un-choose mutation at the heart of the backtracking template.

🏏

Cricket analogy: Since no two queens can share a row, a captain assigns exactly one fielder per row of the grid and, using hash sets for occupied columns and diagonals (row-col and row+col constants), instantly checks and then undoes a placement if it later fails.

Example

python

def print_board(placement, n):
    for col in placement:
        row_str = '.' * col + 'Q' + '.' * (n - col - 1)
        print(row_str)
    print()


solutions = solve_n_queens(4)
print(f"Number of solutions for 4-Queens: {len(solutions)}")
for sol in solutions:
    print_board(sol, 4)

Complexity

In the worst case, without any pruning, placing N queens one per row with N choices per row would be O(N^N); restricting to one queen per column as well (a permutation of columns) tightens this to O(N!), which is the standard bound cited for N-Queens. In practice, diagonal pruning eliminates the vast majority of these branches long before they reach full depth, so the actual number of nodes visited is far smaller than N! for typical N. Space complexity is O(N) for the recursion stack, the placement array, and the three tracking sets.

🏏

Cricket analogy: Without any pruning, assigning N fielders to N positions with N choices each would explode to O(N^N) combinations; restricting to one fielder per column too narrows it to O(N!) permutations, and diagonal-clash pruning eliminates most of those long before a full lineup is tried.

Key Takeaways

One queen per row is enforced structurally by recursing row by row.
Column and diagonal conflicts are tracked with O(1) hash-set lookups: col, row-col, row+col.
Worst-case time complexity is O(N!), though diagonal pruning cuts actual runtime substantially.
The choose/explore/un-choose pattern updates and restores three sets plus the placement list.
N-Queens is a template for any 'place items under pairwise constraints' backtracking problem.

Practice what you learned

1. Why can the N-Queens backtracking solution place exactly one queen per row without loss of generality?

2. How are '/' diagonals identified in O(1) for conflict checking in the N-Queens solution?

3. What is the standard worst-case time complexity bound for the N-Queens backtracking algorithm?

4. What does the 'un-choose' step do after a recursive call returns in the N-Queens solver?

Was this page helpful?

The Backtracking Paradigm

Sudoku Solver

Topics covered

#Python#AlgorithmsStudyNotes#Algorithms#NQueensProblem#Queens#Problem#Approach#Syntax#StudyNotes#SkillVeris