Peaceful queens
Count the ways to place queens on a board so none attacks another, placing one row at a time and rejecting clashes as soon as they appear. About 20 minutes.
One queen per row
A queen attacks along its row, its column and both diagonals. To put n queens on an n by n board with none attacking another, each row must hold exactly one queen. So decide the queen for row 0, then row 1, and so on.
For each row, try every column. If the square is attacked by a queen already placed, skip it. Otherwise place a queen there and recurse to the next row. When all rows are filled, you've found one arrangement.
for col in range(n):
if col in cols:
continue # taken
cols.add(col)
cols.remove(col) # undoRow 0: try column 0 first. It leads to a dead end, so the search comes back and tries column 1. Place a queen at column 1.
Name the diagonals
Squares on one diagonal share the value row minus column, and squares on the other diagonal share row plus column. So keep three sets: the columns used, the row-minus-column values used, and the row-plus-column values used. A square is safe if its column and both numbers are new.
After trying a column, undo it: remove the queen from the three sets so the next column starts from a clean state. This is the same place, recurse, undo rhythm as other searches that build a choice step by step.
r, c = 2, 3 d1 = r - c # -1: one diagonal d2 = r + c # 5: the other
Why do we need exactly one queen in each row?
- ATwo queens in a row would attack each other, and n rows need n queens
- BIt's only a speed-up and not required
- CBecause each column must be empty
Show the answer
Two queens in a row would attack each other, and n rows need n queens. With n queens on n rows and no row shared, there is exactly one in each row.
Peaceful queens
Return the number of ways to place n queens on an n by n chessboard so that no two queens attack each other (no two share a row, a column or a diagonal).
n = 4 → 2
1 ≤ n ≤ 9