Count the ways to place queens that cannot attack

Place one queen per row. Keep sets of used columns and used diagonals (row - col and row + col identify them). In each row, try only free columns, recurse to the next row, then remove the queen. O(n · n!) is a loose worst-case bound, and the search is far below it in practice because the sets prune early. The sets and the recursion take O(n) space.

One queen per row removes the row check entirely.

row - col is constant along one diagonal direction and row + col along the other.

Bitmasks instead of sets make this one of the fastest classic searches.

def count_boards(n: int) -> int:
    cols: set[int] = set()
    falling: set[int] = set()  # row - col
    rising: set[int] = set()  # row + col

    def place(row: int) -> int:
        if row == n:
            return 1
        total = 0
        for c in range(n):
            if c in cols or row - c in falling or row + c in rising:
                continue
            cols.add(c)
            falling.add(row - c)
            rising.add(row + c)
            total += place(row + 1)
            cols.remove(c)
            falling.remove(row - c)
            rising.remove(row + c)
        return total

    return place(0)

Common mistakes

• Checking all earlier queens on every placement, which is O(n) per check instead of O(1).
• Forgetting to remove the queen's column and diagonals when backtracking.

Explain the diagonal keys; it is the trick that makes the checks O(1).

Follow-up questions

Think of your answer first, then open the hint.

1. How many solutions for n = 8?

   Show hint

   92.

2. How do you list the boards instead of counting?

   Show hint

   Keep the chosen column for each row and record a copy when the last row is filled.