Backtracking

Suppose you must seat six queens on a 6x6 chessboard so that none can attack another. Brute force says "try every arrangement" - but there are nearly two million ways to drop six queens on thirty-six squares, and almost all of them are junk. Backtracking is the disciplined way to search that haystack: build a solution one choice at a time, and the moment a partial arrangement is already doomed, throw the whole branch away instead of finishing it. It is brute force with the good sense to give up early - and that single idea makes an impossible search tractable.

The search space is a tree of choices

Any problem you solve by making a sequence of decisions has a hidden shape: a decision tree. The root is "nothing decided yet." Each level is one decision, each branch a possible value for it, and each leaf a complete candidate. For N-Queens, level $k$ decides which row the queen in column $k$ sits on, so the tree is $N$ levels deep and $N$-way branching - a giant of $N^N$ leaves.

Choose, explore, un-choose - and prune

Every backtracking algorithm is the same three-beat rhythm, wrapped in a loop over the options at the current step:

• Choose - commit to one option and record it in the partial solution.
• Explore - recurse to decide the next step, assuming this choice sticks.
• Un-choose - if exploring failed, undo the choice so the state is clean, and try the next option.

The magic ingredient is a constraint check before you choose. If an option already violates a rule - two queens sharing a row or diagonal - you prune: skip it without exploring, cutting off the entire subtree beneath it. And you need a base case that says "the partial solution is now complete - stop and report success." Swap the constraint and the same three lines enumerate every permutation of a list, or every subset of a set; N-Queens just adds "no two on a diagonal."

def solve_n_queens(n):
    rows, diag, anti = set(), set(), set()   # rows & the two diagonal families in use
    board = [-1] * n                          # board[col] = chosen row for that column

    def backtrack(col):                       # one queen per column, left to right
        if col == n:                          # BASE CASE: every column filled
            return True                       # a complete, conflict-free board
        for row in range(n):                  # try each row from the top
            if row in rows or (col - row) in diag or (col + row) in anti:
                continue                     # PRUNE: some queen already attacks here
            rows.add(row); diag.add(col - row); anti.add(col + row)      # CHOOSE
            board[col] = row
            if backtrack(col + 1):             # EXPLORE the next column
                return True
            rows.discard(row); diag.discard(col - row); anti.discard(col + row)  # UN-CHOOSE
        return False                         # dead end - let the caller backtrack

    return board if backtrack(0) else None

Watch it: N-Queens

Here is that code running as a movie. The board fills column by column. When a candidate square is attacked by a queen already on the board, it flashes red with the line of attack drawn in - that branch is pruned. When a whole column runs out of safe rows, the search backtracks: it lifts the last committed queen (an ✕) and tries her next row. Press Play to auto-run to a full solution, drag Speed, or single-step. Switch to 4x4 to hand-walk every choice, or 8x8 to watch the counters explode.

Check yourself