DSA N-Queens

The problem

N-Queens asks for every placement of n queens on an n by n board where no queen attacks another. Two queens attack each other when they share a row, a column, or a diagonal.

The answer in this article is the list of boards. Each board is written as the column of the queen in each row, in row order. One queen sits in each row, so a row never needs to be checked.

expected = [(1, 1), (2, 0), (3, 0), (4, 2), (8, 92)]
for n, count in expected:
    print('n =', n, 'expected solutions:', count)

The counts for these sizes appear in the optimal section. Sizes 2 and 3 have no placement at all. Size 8 is the classic board, and its count is 92.

Intuition: take the first safe column in each row

The first idea fills one row at a time. In each row it takes the first column that no earlier queen attacks. The idea is fast, and it never looks ahead.

That greed is the trap. A safe choice in an early row can leave a later row with no safe column at all. The search then has to undo an earlier choice, which the greedy walk cannot do.

def greedy(n):
    placed = []
    for row in range(n):
        chosen = None
        for col in range(n):
            ok = True
            for r, c in enumerate(placed):
                if c == col or abs(r - row) == abs(c - col):
                    ok = False
            if ok:
                chosen = col
                break
        if chosen is None:
            return placed, row
        placed.append(chosen)
    return placed, None
placed, stuck = greedy(4)
print('queens placed:', placed)
print('stuck at row:', stuck)

The walk places two queens and stalls in row 2. A full placement does exist for this board. The early choices were each safe, and they were still wrong together.

Brute force: test every column choice in every row

The brute force tries every column in every row. It builds a full board first. Only then does it test every pair of queens for an attack.

Most boards it builds are invalid. The pair test finds the attack only after the whole board exists. A counter records how many boards were built.

import itertools
def brute(n):
    built = [0]
    good = []
    for board in itertools.product(range(n), repeat=n):
        built[0] += 1
        ok = True
        for i in range(n):
            for j in range(i + 1, n):
                if board[i] == board[j] or abs(i - j) == abs(board[i] - board[j]):
                    ok = False
        if ok:
            good.append(list(board))
    return good, built[0]
for n in [3, 4]:
    good, built = brute(n)
    print('n =', n, 'boards built:', built, 'valid:', len(good))
    for board in good:
        print('valid board columns:', board)

A four by four board builds 256 boards to find 2 valid ones. Each added row multiplies the board count by n. The optimal search avoids building invalid boards at all.

The optimal solution: guard each row with three sets

Three sets record the lines already under attack, and a column is safe when its column key and both diagonal keys are absent from those sets. That one sentence is the whole method.

A down diagonal holds the cells where row minus column stays equal. An up diagonal holds the cells where row plus column stays equal. Placing a queen adds its three keys, and removing them after the branch is the unchoose step.

def solve(n):
    cols = set()
    diag_down = set()
    diag_up = set()
    path = []
    boards = []
    calls = [0]
    def search(row):
        calls[0] += 1
        if row == n:
            boards.append(list(path))
            return
        for col in range(n):
            if col in cols or (row - col) in diag_down or (row + col) in diag_up:
                continue
            cols.add(col)
            diag_down.add(row - col)
            diag_up.add(row + col)
            path.append(col)
            search(row + 1)
            path.pop()
            cols.remove(col)
            diag_down.remove(row - col)
            diag_up.remove(row + col)
    search(0)
    return boards, calls[0]
for n in [1, 2, 3, 4, 8]:
    boards, calls = solve(n)
    print('n =', n, 'solutions:', len(boards), 'calls:', calls)
boards, calls = solve(4)
for board in boards:
    print('board columns:', board)

Every case from the start of the article is answered. Sizes 2 and 3 return no boards. Size 8 returns 92 boards in 2057 calls, far below the board count a brute force would build.

Walkthrough: the first board for n equals 4

The walk fills rows in order. The state is the path of chosen columns and the three guard sets. Each step shows the path after one queen is placed.

n = 4
path = [1, 3, 0, 2]
cols = set()
diag_down = set()
diag_up = set()
for row, col in enumerate(path):
    cols.add(col)
    diag_down.add(row - col)
    diag_up.add(row + col)
    print('row', row, 'queen at column', col, 'path:', list(path[:row + 1]))
    print('  columns used:', sorted(cols), 'down:', sorted(diag_down), 'up:', sorted(diag_up))
for col in path:
    print('.' * col + 'Q' + '.' * (n - col - 1))

The last queen lands in row 3, column 2. The path holds four queens at that point, so the board is complete. The printed board shows no two queens on one line.

Complexity

The guarded search visits only partial boards that have no attack so far, so its time is far below n to the power n boards of the brute force, though it still grows fast with n. Its space is O(n), for the path and the three sets, each holding at most n keys.

def count_calls(n):
    cols = set()
    down = set()
    up = set()
    calls = [0]
    def search(row):
        calls[0] += 1
        if row == n:
            return
        for col in range(n):
            if col in cols or (row - col) in down or (row + col) in up:
                continue
            cols.add(col)
            down.add(row - col)
            up.add(row + col)
            search(row + 1)
            cols.remove(col)
            down.remove(row - col)
            up.remove(row + col)
    search(0)
    return calls[0]
for n in [4, 6, 8]:
    print('n =', n, 'search calls:', count_calls(n), 'brute boards:', n ** n)

At n equal to 8 the search makes 2057 calls. The brute force would build 16777216 boards. Pruning a branch at the first attack is where the saving comes from.

Edge cases and pitfalls

Boards of size 2 and 3 have no solution. A correct search returns an empty list for them, not an error. A board of size 1 has one trivial placement.

Forgetting the unchoose step is the classic bug. The guard sets then keep keys from a dead branch. Later rows look blocked by queens that are no longer placed.

def count_solutions(n):
    cols = set()
    down = set()
    up = set()
    count = [0]
    def search(row):
        if row == n:
            count[0] += 1
            return
        for col in range(n):
            if col in cols or (row - col) in down or (row + col) in up:
                continue
            cols.add(col)
            down.add(row - col)
            up.add(row + col)
            search(row + 1)
            cols.remove(col)
            down.remove(row - col)
            up.remove(row + col)
    search(0)
    return count[0]
for n in [1, 2, 3, 5]:
    print('n =', n, 'solutions:', count_solutions(n))

The counts match the known values for these sizes. Each branch removes its three keys before the next column is tried. That removal is what makes the counts exact.