N-Queens II

Q: 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. The diagonal checks prune far below that bound, to 856,189 partial boards for n = 12 . No polynomial method is known for counting the solutions, so a search like this is the standard answer. The space is O(n) .

Q: How do you tell which diagonal a square is on?

Moving one step along a / diagonal adds 1 to the row and subtracts 1 from the column, so row + col never changes. Moving along a \ diagonal adds 1 to both, so row - col never changes. Each sum names one diagonal, and adding n-1 to the difference turns it into an array index from 0 to 2n-2 .

HardBacktracking

+10

A queen on a chessboard attacks every square in its row, in its column and along both of its diagonals, however far away. You get 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.

Two ways are different when some square holds a queen in one and is empty in the other. So a board and its mirror image count as two ways, even though they look alike.

Function

totalNQueens(n: integer) → integer

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 = 12 is 14,200, so it fits in a 32-bit integer.

Examples

Input: n = 4
Output: 2
Explanation: Writing the column of each row's queen from top to bottom, the two boards are 1, 3, 0, 2 and 2, 0, 3, 1. Each is the mirror image of the other, and they count as two ways. Every other choice puts two queens on a shared column or diagonal.

+10 hidden tests on Submit

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.

0 of 3 opened

Solution

A placement is fixed by choosing one column for each row, since two queens in a row always attack each other. That is still n^n choices, about 8.9 × 10^12 for n = 12, so you cannot list them all. Two ideas crack it. Build the board row by row and abandon a partial board the moment a queen is attacked, which cuts the search to under a million partial boards for n = 12. And record which columns and diagonals are taken, so testing a square costs three lookups instead of a scan of every queen placed so far.

Try every placement with one queen per row

Correct, but does not finish on the largest tests

Intuition

Every row must hold exactly one queen, so a placement is a list cols where cols[r] is the column of the queen in row r. Each entry can be any of n columns, so there are n^n lists. Run through all of them the way an odometer counts: raise the last entry by one, and when it passes n-1, reset it to 0 and carry into the entry before.

For each list, compare every pair of rows i < j. The two queens attack each other when they share a column, cols[i] == cols[j], or a diagonal. On a diagonal, moving down one row moves you one column left or right, so two queens share a diagonal exactly when the column gap equals the row gap: |cols[i] - cols[j]| == j - i. A list that passes every pair is one valid board. Since every list is checked, none is missed and none is counted twice.

It is slow because it never stops early. Two queens on the same diagonal in the first two rows doom the board, yet the odometer still tries all n^(n-2) ways to fill the other rows. For n = 8 that is 16,777,216 lists to find 92 boards. For n = 12 it is about 8.9 × 10^12 lists. Even at one nanosecond a list, that is about 2.5 hours.

Algorithm

Start with cols all zeros: every queen in column 0.
Check every pair of rows i < j: the list is invalid if cols[i] == cols[j] or |cols[i] - cols[j]| == j - i.
If no pair clashes, add 1 to the count.
Advance cols like an odometer: from the last row upward, reset each entry that holds n-1 to 0, then add 1 to the first entry that does not.
When every entry was n-1, all n^n lists have been seen: return the count.

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] += 1

Backtracking with column and diagonal sets

Intuition

Place the queens row by row, from the top, and check each new queen the moment you place it. If it is attacked, no way of filling the rows below can fix that, so skip the square at once. If it is safe, recurse into the next row, and when that call returns, remove the queen and try the next column. A call that reaches row n has placed n safe queens and counts one board. This is backtracking, and it prunes hard: for n = 12 it visits 856,189 partial boards instead of 8.9 × 10^12 complete ones.

The other half is testing a square fast. The rows below are empty, and the new queen's own row has no other queen, so only three lines can attack square (row, c): its column, its / diagonal and its \ diagonal. Every square on one / diagonal has the same row + c, from 0 to 2n-2. Every square on one \ diagonal has the same row - c, from -(n-1) to n-1, so add n-1 to get an index from 0 to 2n-2. Keep three arrays of flags, cols of size n and diag and anti of size 2n-1. The square is safe exactly when all three flags are off: three lookups, O(1), where comparing against every queen placed so far would cost O(n).

A line can hold at most one queen, so placing a queen turns its three flags on and removing it turns them off again, leaving the arrays exactly as they were. On the 4 by 4 board, a queen at (0, 0) sets cols[0], diag[0] and anti[3]. In row 1, column 1 sits on anti[3], so it is skipped without looking at the queen itself.

The first row offers n columns, the second at most n-1 and so on, so the search is bounded by O(n!), and the diagonals cut it far below that. For n = 12 the loops test 10,103,868 squares in total. The recursion is n calls deep and the arrays hold about 5n flags, so the space is O(n).

Algorithm

Make three arrays of flags, all off: cols with n entries, diag and anti with 2n-1 each.
Write place(row). If row == n, return 1: every row holds a safe queen.
Otherwise, for each column c, skip it if cols[c], diag[row + c] or anti[row - c + n - 1] is on.
For a safe column, turn the three flags on, add place(row + 1) to the total, then 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 sets search is fast, but in every row it still tests all n columns, most of them attacked. A bitmask lets you jump straight to the free ones. Let bit c of an integer stand for column c of the row you are about to fill, and keep three masks: cols, the columns already taken, left, the squares of this row hit along one diagonal direction, and right, those hit along the other.

The free squares are then one expression: free = ~(cols | left | right) & full, where full has the low n bits set. free & -free isolates the lowest free square, and subtracting it moves on to the next. When you place a queen at bit and go down one row, its column stays taken, while each diagonal attack moves one column over. So the next row gets cols | bit, ((left | bit) << 1) & full and (right | bit) >> 1. There is nothing to undo: each call gets its own three integers. When cols == full, all n queens are placed.

Take n = 4 and a first queen in column 1, bit = 0010, writing column 0 as the rightmost bit. Row 1 gets cols = 0010, left = 0100 and right = 0001, so free = 1000: column 3 is the only choice, found without testing columns 0, 1 or 2.

The search visits the same partial boards as the sets version, but every loop step now places a queen. For n = 12 that is 856,188 steps instead of 10,103,868 square tests, with a few integer operations each. The time is still bounded by O(n!), and the recursion is n calls deep. The R code runs the same masks without recursion: it keeps every partial board of a row in a vector and grows them all one row at a time, so it holds a whole level of boards in memory instead of n calls.

Algorithm

Set full = (1 << n) - 1, the mask of all n columns.
Write count(cols, left, right). If cols == full, return 1.
Compute free = ~(cols | left | right) & full.
While free is not 0, take bit = free & -free, remove it from free, and add count(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

The search itself is short. Most bugs are in the diagonal arithmetic and in the undo step.

Using row - c as an index without adding n-1. In Java that throws, in C it reads memory outside the array, and in Python anti[-2] quietly reads another diagonal's flag, so the count comes out wrong with no error.
Sizing the diagonal arrays with n entries. An n × n board has 2n-1 diagonals in each direction.
Checking only one diagonal direction, or only the columns. Both diagonal directions attack.
Forgetting to turn the flags off after the recursive call returns. Every later branch then sees queens that are no longer on the board, and the count drops.
Leaving out & full when computing free. ~x also sets every bit above column n-1, so the loop picks squares off the board, and in Python or Ruby, whose integers have no fixed width, free becomes negative and the loop never ends.
Treating mirror images as one board. The problem counts them apart: n = 4 has 2 boards, and they are mirror images of each other.
Special-casing small boards wrongly. n = 1 has 1 board, while n = 2 and n = 3 have none. The search gets all three right with no special case.

Frequently asked questions4

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. The diagonal checks prune far below that bound, to 856,189 partial boards for n = 12. No polynomial method is known for counting the solutions, so a search like this is the standard answer. The space is O(n).

How do you tell which diagonal a square is on?

Moving one step along a / diagonal adds 1 to the row and subtracts 1 from the column, so row + col never changes. Moving along a \ diagonal adds 1 to both, so row - col never changes. Each sum names one diagonal, and adding n-1 to the difference turns it into an array index from 0 to 2n-2.

What is the difference between N-Queens and N-Queens II?

N-Queens asks for every board, drawn as rows of text. N-Queens II asks only how many there are. The search is the same backtracking, but counting needs no board in memory, only the column and diagonal sets, so it is faster and lighter. That is also what makes the bitmask version natural here.

Can you use symmetry to speed up N-Queens II?

Yes. Mirroring a board left to right gives another valid board, so the boards with the first queen in the left half match those with it in the right half. Count the boards whose first queen is in columns 0 to n/2 - 1 and double that. When n is odd, add the boards with the first queen in the middle column once. That halves the search.

Python

def totalNQueens(n):
    # Write code here

Test cases

Case 1

Case 2

Input

n = 4

Expected

N-Queens II

Function

Constraints

Examples

Hints

Solution

Try every placement with one queen per row

Backtracking with column and diagonal sets

Backtracking with bitmasks

Pitfalls and edge cases

Frequently asked questions4

Similar problems