Count Queen Placements
Problem
On an n by n chessboard, place n queens so that no two of them share a row, a column or a diagonal. Return how many different placements exist. The board size n is at least 1.
Examples
Input: n = 4
Output: 2
Why: the two placements are mirror images of each otherInput: n = 1
Output: 1
Why: a single queen on a single square attacks nothingInput: n = 3
Output: 0
Why: edge case, small boards can have no valid placement at allHints
0 / 3
Choosing n squares out of n squared is hopeless. There is a constraint that tells you exactly how many queens each row must hold.
Since every row holds one queen, the only real choice per row is a column. Keep a record of which columns and which diagonals are already under attack; a diagonal can be named by the row minus the column in one direction and the row plus the column in the other.
Recurse row by row. For each column whose column and both diagonals are free, mark all three as taken, recurse into the next row and add up what it returns, then unmark them. Arriving at row n counts as one complete placement.
Solution
Placing one queen per row turns the search into a choice of column per row, and three sets make every attack check constant time: one for columns, one for the down diagonals keyed by row minus column, and one for the up diagonals keyed by row plus column. A column is tried only when all three keys are free, which prunes most of the tree long before the last row. Marking before the recursive call and unmarking after it is the choose-explore-un-choose rhythm. The search is bounded by n factorial but pruning keeps it far smaller in practice; the depth is O(n) and the sets hold O(n) keys.
def count_queens(n):
cols, down, up = set(), set(), set()
def place(row):
if row == n:
return 1 # every row holds a queen
total = 0
for c in range(n):
if c in cols or row - c in down or row + c in up:
continue # this square is under attack
cols.add(c); down.add(row - c); up.add(row + c)
total += place(row + 1)
cols.remove(c); down.remove(row - c); up.remove(row + c)
return total
return place(0)
print(count_queens(4)) # -> 2
print(count_queens(1)) # -> 1
print(count_queens(3)) # -> 0
print(count_queens(8)) # -> 92Stuck on the idea rather than the code? N-Queens covers it.