N-Queens II
A queen attacks every square in its row, its column and both of its diagonals, however far away. Given an integer n, return the number of ways to place n queens on an n × n board so that no two queens attack each other.
Boards that differ in any square count separately, mirror images included.
Function
- ninteger
- the size of the board and the number of queens
- Returnsinteger
- the number of ways to place the queens so that none attacks another
Constraints
1 ≤ n ≤ 12- The answer for
n = 12is 14,200, so it fits in a 32-bit integer.
Examples
- Input
- n = 4
- Output
- 2
- Explanation
- Writing each row's queen column from top to bottom, the boards are
1, 3, 0, 2and2, 0, 3, 1: mirror images, counted as two. Every other choice puts two queens on a shared column or diagonal.
- Input
- n = 3
- Output
- 0
- Explanation
- A queen in a top corner leaves one safe square in the middle row, and then the bottom row has none. A queen in the top middle attacks the whole middle row.
Follow-up
Can you count only the boards that stay different after rotating and mirroring the board? For n = 8, the 92 boards fall into 12 such groups.
Hints
Open them one at a time. Each one gives away a little more.
Two queens in the same row attack each other, so every row holds exactly one queen. What is left to choose once you know that?
Fill the board one row at a time, from the top. As soon as the new queen is attacked, abandon that partial board, since nothing you add below can repair it. To test a square without looking at the whole board, remember which columns and which diagonals already hold a queen. Along one diagonal direction
row + colis the same for every square, and along the otherrow - colis.Write
place(row), which returns how many complete boards can be finished from here. It returns 1 whenrow == n. Otherwise it tries every columncwhose column,row + cdiagonal androw - cdiagonal are all free: mark the three, addplace(row + 1)to a running total, then unmark them. The answer isplace(0).
Solution
Two queens in one row always attack, so a board is one column per row: n^n lists, about 8.9 × 10^12 for n = 12. Build it row by row instead, drop a partial board as soon as a queen is attacked, and flag the taken columns and diagonals so testing a square costs three lookups.
Try every placement with one queen per row
Correct, but does not finish on the largest tests
Intuition
Write a placement as a list cols, the column of each row's queen, and run through all n^n lists like an odometer. Queens in rows i < j attack when cols[i] == cols[j] or |cols[i] - cols[j]| == j - i, since a diagonal moves one column per row. Each list is checked once, so no board is missed or counted twice.
Nothing stops early: a clash in the first two rows still leaves n^(n-2) lists. For n = 8 that is 16,777,216 lists for 92 boards; for n = 12, 8.9 × 10^12, about 2.5 hours at a nanosecond each.
Algorithm
- Start with
colsall zeros. - Add 1 to the count if no pair of rows
i < jhascols[i] == cols[j]or|cols[i] - cols[j]| == j - i. - Advance like an odometer: from the last row up, reset each entry at
n-1to 0, then add 1 to the first entry belown-1. - Stop and return the count when every entry was
n-1.
def totalNQueens(n):
def is_valid(cols):
# cols[r] is the column of the queen in row r, so rows never clash.
for i in range(n):
for j in range(i + 1, n):
if cols[i] == cols[j] or abs(cols[i] - cols[j]) == j - i:
return False
return True
cols = [0] * n
count = 0
while True:
if is_valid(cols):
count += 1
# Move to the next placement, like an odometer with n digits in base n.
row = n - 1
while row >= 0 and cols[row] == n - 1:
cols[row] = 0
row -= 1
if row < 0:
return count
cols[row] += 1Backtracking with column and diagonal sets
Intuition
Place queens row by row and test each one as you place it. No filling of the rows below can save an attacked queen, so skip that square. A safe queen recurses into the next row and is removed when the call returns; reaching row n counts one board.
Only three lines can attack square (row, c): its column, its / diagonal, where row + c is constant, and its \ diagonal, where row - c is constant (add n-1 to index it from 0). Flag arrays cols, diag and anti turn the safety test into three lookups. Each line holds at most one queen, so clearing the flags on return restores the arrays exactly.
Row k offers at most n - k columns, so the search is bounded by O(n!), with O(n) space.
Algorithm
- Make flag arrays
colsof sizenanddiagandantiof size2n-1, all off. place(row): ifrow == n, return 1.- For each column
c, skip it ifcols[c],diag[row + c]oranti[row - c + n - 1]is on. - Otherwise turn the three flags on, add
place(row + 1)to the total, and turn them off. - Return the total. The answer is
place(0).
def totalNQueens(n):
cols = [False] * n # cols[c]: column c holds a queen
diag = [False] * (2 * n - 1) # diag[r + c]: that / diagonal holds a queen
anti = [False] * (2 * n - 1) # anti[r - c + n - 1]: that \ diagonal holds a queen
def place(row):
if row == n:
return 1 # a queen in every row: one complete board
count = 0
for c in range(n):
if cols[c] or diag[row + c] or anti[row - c + n - 1]:
continue # attacked: three lookups, no scan of the board
cols[c] = diag[row + c] = anti[row - c + n - 1] = True
count += place(row + 1)
cols[c] = diag[row + c] = anti[row - c + n - 1] = False # take it back
return count
return place(0)Backtracking with bitmasks
Intuition
The flag search still tests all n columns of each row; bitmasks jump straight to the free ones. Bit c is column c of the row being filled: cols holds the taken columns, and left and right the squares hit along each diagonal. Then free = ~(cols | left | right) & full, with full the low n bits, and free & -free is the lowest free square. One row down, a column stays taken and each diagonal attack shifts one column.
With n = 4 and a first queen at bit = 0010, row 1 gets free = 1000: column 3, found without testing the others. For n = 12, 856,188 loop steps replace 10,103,868 square tests. The R code grows a whole row of partial boards at once instead of recursing.
Algorithm
- Set
full = (1 << n) - 1. count(cols, left, right): ifcols == full, return 1.- Compute
free = ~(cols | left | right) & full. - While
freeis not 0, takebit = free & -free, remove it fromfree, and addcount(cols | bit, ((left | bit) << 1) & full, (right | bit) >> 1)to the total. - Return the total. The answer is
count(0, 0, 0).
def totalNQueens(n):
full = (1 << n) - 1 # bit c stands for column c of the current row
def count(cols, left, right):
# cols: columns taken. left, right: squares of this row hit along a diagonal.
if cols == full:
return 1 # every column used: n queens placed
total = 0
free = full & ~(cols | left | right)
while free:
bit = free & -free # the lowest free square
free -= bit
# Moving down a row shifts each diagonal attack one column over.
total += count(cols | bit, ((left | bit) << 1) & full, (right | bit) >> 1)
return total
return count(0, 0, 0)
Pitfalls and edge cases
- Indexing
antiwithrow - cwithout addingn-1. Java throws, C reads outside the array, and Python'santi[-2]quietly reads another diagonal's flag. - Sizing the diagonal arrays
ninstead of2n-1.row + creaches2n-2. - Not clearing the flags after the recursive call. Later branches see queens that are gone, and the count drops.
- Leaving
& fullout offree.~xsets the bits above columnn-1, so the loop picks squares off the board; in Python or Rubyfreegoes negative and the loop never ends.
Frequently asked questions3
What is the time complexity of N-Queens II?
Backtracking is bounded by O(n!): the first row has n choices, the next at most n-1, and so on. Pruning cuts the real work far lower, to 856,189 partial boards for n = 12. The space is O(n).
What is the difference between N-Queens and N-Queens II?
N-Queens returns every board, drawn as rows of text; N-Queens II returns only how many there are. The search is the same, but counting stores no boards, which suits the bitmask version.
Can you use symmetry to speed up N-Queens II?
Mirroring a board left to right gives another valid board, so count the boards whose first queen is in columns 0 to n/2 - 1 and double that. For odd n, add the boards with the first queen in the middle column once.
Similar problems
Problems that use the same ideas. Solving two or three of them is what makes a pattern stick.
def totalNQueens(n):
# Write code hereTest #1
Test #2
Argument
n = 4
Expected Output
2