Constraint puzzles (N-Queens, Sudoku)

A constraint puzzle asks you to fill positions so that every rule holds. In N-Queens you place n queens on an n x n board so that no two share a row, column or diagonal. In Sudoku you fill a 9 x 9 grid so each row, column and 3 x 3 box contains 1 to 9 exactly once.

Backtracking solves both: place one piece, check that the rules still hold, recurse to the next position, and undo if no option works further down. The art is checking rules in O(1) with sets or arrays instead of rescanning the board.

Real solvers add two ideas on top: constraint propagation (after a placement, remove options that are now impossible elsewhere) and ordering heuristics (fill the most constrained cell first).

1. 1N-Queens: there is exactly one queen per row, so recurse row by row and choose a column for each.
2. 2Keep three sets: used columns, used diagonals keyed by row - col, and used anti-diagonals keyed by row + col. Cells on the same diagonal share row - col; cells on the same anti-diagonal share row + col.
3. 3A column c in row r is safe if c, r - c and r + c are all unused. Place, add to all three sets, recurse to r + 1, then remove from all three.
4. 4Sudoku: keep a set for each row, column and box, with box index (r // 3) * 3 + c // 3. Fill empty cells one by one with digits that are in none of the three sets.
5. 5For Sudoku you only need one solution, so return True as soon as the board is full and stop searching.
6. 6Speed-up: choose the empty cell with the fewest legal digits next (minimum remaining values). This makes most real puzzles solve with very little backtracking.

def solve_n_queens(n):
    solutions, queens = [], []          # queens[r] = column in row r
    cols, diag, anti = set(), set(), set()

    def place(row):
        if row == n:
            solutions.append(queens[:])
            return
        for c in range(n):
            if c in cols or row - c in diag or row + c in anti:
                continue                # attacked: prune this branch
            queens.append(c)
            cols.add(c); diag.add(row - c); anti.add(row + c)
            place(row + 1)
            queens.pop()
            cols.remove(c); diag.remove(row - c); anti.remove(row + c)

    place(0)
    return solutions

print(solve_n_queens(4))  # [[1, 3, 0, 2], [2, 0, 3, 1]]

Three sets make each safety check O(1). Every placement adds to all three sets and every undo removes from all three, so the state is always consistent. Each solution lists the queen's column for rows 0 to n - 1.

Cost: N-Queens with row-by-row placement explores at most O(n!) placements, and real counts are far smaller because of diagonal pruning; extra space is O(n). Sudoku worst case is 9^(number of empty cells), but with good checks typical puzzles finish in milliseconds.