How many ways the queens fit

Place n queens on an n by n board so that no two attack each other. A queen attacks along its row, its column, and both diagonals. Report how many arrangements there are.

Worked example#

For n = 4 there are 2:

. Q . .        . . Q .
. . . Q        Q . . .
Q . . .        . . . Q
. . Q .        . Q . .

For n = 1 there is 1, and for n = 2 and n = 3 there are none at all: the board is too cramped.

The idea#

Two queens can never share a row, so place exactly one queen per row and the rows take care of themselves. That leaves three things to check for each candidate square.

Now the trick that makes this fast to write and fast to run. Instead of scanning the board for conflicts, keep three sets of what is already taken:

• the columns in use;
• the down-right diagonals, where every square has the same row + col;
• the down-left diagonals, where every square has the same row - col.

Check those and you have checked the whole board in three lookups. That both diagonals can be named by a single number is the observation worth taking away: it turns a scan into an index.

place(row):
    if row == n: count += 1, return
    for col in 0..n-1:
        if col, row+col or row-col is taken: skip
        mark all three taken          # choose
        place(row + 1)                # explore
        unmark all three              # un-choose

Where the saving is#

There are n to the power of n ways to put one queen in each row. For n = 8 that is nearly seventeen million, and only 92 work.

Backtracking never builds most of them. The moment a partial board has a conflict, every arrangement below it is abandoned, and that is millions of boards never considered. Pruning is not an optimisation here: without it, nothing finishes.

The un-choose, three times over#

Three sets are changed on the way down, so three must be changed back on the way up. Forgetting one is the classic bug, and it shows as too few answers rather than a crash, which makes it hard to spot. If your count comes out low, this is where to look.

Constraints#

• 1 <= n <= 11