N-Queens

def solveNQueens(n):
    out, board = [], []
    cols, diag, anti = set(), set(), set()
    def place(r):
        if r == n:                      # past the last row
            out.append(['.'*c + 'Q' + '.'*(n-c-1) for c in board])
            return
        for c in range(n):
            if c in cols or r - c in diag or r + c in anti:
                continue                # attacked: skip
            cols.add(c); diag.add(r - c); anti.add(r + c)
            board.append(c)
            place(r + 1)
            cols.remove(c); diag.remove(r - c); anti.remove(r + c)
            board.pop()                 # backtrack
    place(0)
    return out

N-Queens. Place n queens on an n by n chessboard so no two attack each other, and return every board that works.

A queen attacks along its row, its column and both diagonals. Four queens on a four by four board have exactly two solutions; eight queens have ninety-two.

The naive way tries every placement: four squares out of sixteen is eighteen hundred and twenty boards, and eight queens give over four billion.

The key: each row holds exactly one queen. So go row by row, with three sets: used columns, diagonals named by row minus column, and anti-diagonals named by row plus column. Checking a square is three quick lookups.

In code, place takes a row. Past the last row, save the board. Otherwise try each column, skipping any a set holds. Add it to all three sets, recurse on the next row, then remove it. That removal is the backtrack.

Let's run four. A queen takes the corner. In row two, columns one and two are attacked, so it takes column three. Row three is all blocked: dead end. Back up and slide that queen to column four. Row three takes column two, but row four is blocked. Back up all the way and move the first queen to column two. Now everything fits: column four, column one, column three. First solution.

Each row has fewer safe columns than the last, so the time grows roughly like n factorial, far less than every board. The sets hold only n entries, so the space is order n.

One queen per row, three sets, undo on the way back. That's N-Queens.