Queens that never meet
Count the ways to place n queens on an n by n board so that no two attack each other, by placing one queen per row and tracking the columns and diagonals already taken. About 22 minutes.
One queen per row
A queen attacks along its row, its column and both diagonals. Two queens in the same row would attack, so a valid board has one queen in each row. Place them from the top row down. For each row, try each column.
A column is allowed if no earlier queen shares its column or either of its diagonals.
for c in range(n):
queens.append(c)
queens.pop()Row 0: put a queen in column 1.
Constant-time checks
Cells on one diagonal share the same value of row plus column. Cells on the other diagonal share the same value of row minus column. Keep three marker lists: columns used, sums used and differences used. A cell is attacked if any of its three markers is set.
Set the three markers when you place a queen and clear them after the recursive call returns. Add the counts from every column choice. When all n rows are filled, that is one valid board.
d1 = r + c # one diagonal d2 = r - c + n - 1 # the other
Two cells have the same row plus column. What do you know about them?
- AThey lie on the same diagonal, so queens there attack each other
- BThey are in the same row
- CThey are in the same column
Show the answer
They lie on the same diagonal, so queens there attack each other. Moving along that diagonal changes row and column by opposite amounts.
N-Queens count
The n-queens puzzle asks you 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. Given an integer n, return the number of distinct solutions.
n = 4 → 2
1 ≤ n ≤ 9