Count the ways to place n queens with no attacks: one queen per row, three sets for columns and diagonals, undo and try the next.
▼The problem
LeetCode 52 (Hard). Given n, return the number of distinct ways to place n queens on an n × n board so that no two queens attack each other (same row, column or diagonal). Only the count is returned, no boards.
Examples (LeetCode's): n = 4 → 2 and n = 1 → 1.
The solution
def totalNQueens(n):
cols, diag, anti = set(), set(), set()
def place(r):
if r == n:
return 1 # every row filled
count = 0
for c in range(n):
if c in cols or r - c in diag or r + c in anti:
continue
cols.add(c); diag.add(r - c); anti.add(r + c)
count += place(r + 1)
cols.remove(c); diag.remove(r - c); anti.remove(r + c)
return count
return place(0)Transcript
N-Queens Two. Place n queens on an n by n board so no two attack each other. This time, don't build the boards. Just count how many ways there are.
With four queens there are two ways. With one queen, there's exactly one. The counts jump around: zero for two and three, ten for five, and ninety-two for eight.
The naive way puts one queen in each row, in every possible column: n to the n boards, each checked at the end. Four gives two hundred fifty-six boards. Eight gives over sixteen million.
Better: go row by row and check as you place. Keep three sets: used columns, diagonals named by row minus column, and anti-diagonals named by row plus column. Each square costs three constant-time lookups. If a row has no safe column, back up right away. Fill every row, and the count goes up by one.
In code, each call returns its count. For every safe column, add it to the sets, add up the deeper count, then remove it. For speed, the sets can be bitmasks: one AND finds every free column.
Let's count four. Starting in the corner, both tries dead-end, so back up. Column two works all the way down: count one. Column three mirrors it: count two. Column four dead-ends. Total: two.
Each row has fewer safe columns than the last, so time grows roughly like n factorial. The sets and the recursion hold n entries: order n space.
One queen per row, three sets, add one at the bottom. That's N-Queens Two.