Python Program to Solve the N-Queens Problem

Places N queens on an N×N chessboard so that no two attack each other, trying each column row by row and backing up from dead ends.

A chess queen attacks every square along its row, its column and both of its diagonals, so in the N-Queens puzzle no two queens may share any of them. A 4×4 board has 2 solutions; the classic 8×8 version, the eight queens puzzle, has 92.

It's the classic backtracking problem: put a queen on the first safe square of a row, move on to the next row, and when a row has no safe square left, go back and move the queen in the row above.

Program

def is_safe(queens, row, col):
    """True if no queen in queens attacks the square (row, col)."""
    for r, c in enumerate(queens):
        # Same column, or on a diagonal: as far across as down
        if c == col or abs(c - col) == row - r:
            return False
    return True


def n_queens(n):
    """Every safe placement of n queens, as lists of columns."""
    solutions = []
    queens = []  # queens[r] is the column of the queen in row r

    def place(row):
        if row == n:
            solutions.append(queens.copy())
            return
        for col in range(n):
            if is_safe(queens, row, col):
                queens.append(col)  # choose this square
                place(row + 1)      # fill the rows below
                queens.pop()        # undo, to try the next column

    place(0)
    return solutions


size = 4
solutions = n_queens(size)
print(f"{len(solutions)} solutions for {size} queens. The first:")
for col in solutions[0]:
    print(" ".join("Q" if c == col else "." for c in range(size)))

Open in the editor Download n_queens.py

Output

2 solutions for 4 queens. The first:
. Q . .
. . . Q
Q . . .
. . Q .

How it works

Visualize Step through the program line by line: each step below shows up as its line runs.

1. is_safe checks a square against every queen already placed, one in each row above it. Two queens share a diagonal when they are as many columns apart as rows apart, which abs(c - col) == row - r tests. Rows need no check, because each row gets only one queen.
2. solutions collects the finished boards. queens is the board being built, as one number per row: the column of that row's queen. [1, 3, 0, 2] means row 0 has its queen in column 1, row 1 in column 3, and so on.
3. place(row) fills row and the rows below it. It's a function inside n_queens, so it can use n, solutions and queens (scope). When row reaches n, every row has a queen, and a copy of the board goes into solutions.
4. Otherwise it tries each column of the row in turn, and puts a queen on each safe square it finds. That's the choice.
5. place(row + 1) fills the rows below, finding every solution that starts this way.
6. Then it takes the queen back, to try the next column. When no column of a row is safe, the loop ends without placing anything and the call returns to the row above, which moves its queen on: that's the backtracking.
7. The search starts at row 0 with an empty board, and returns every solution it finds.
8. The program solves the 4×4 board and prints how many solutions there are.
9. It draws the first solution a row at a time: Q in the queen's column and . in the others, with spaces between them.

The search on the 4×4 board, up to the first solution:

The search then carries on and finds the second solution, [2, 0, 3, 1], the first one's mirror image. In all it places a queen 16 times and checks 60 squares.

Time and space complexity

The first queen has n columns to choose from, the second at most n − 1 outside the first one's column, the third at most n − 2, and so on: at most n! ways to fill the rows, which is why the time is given as O(n!). The diagonals cut that down a great deal: for 8 queens the program places a queen 2,056 times to find all 92 solutions, where 8! is 40,320. Each is_safe call also reads up to n queens; the version below checks a square in one step. The space is O(n): queens and the chain of place calls are never more than n long, not counting the solutions it keeps.

Other ways to write it

With sets for the columns and diagonals

Squares on the same diagonal going down to the right share row - col, and squares on the same diagonal going up to the right share row + col. Keeping the used columns and diagonals in sets makes each check one lookup instead of a loop. This version only counts the solutions.

def count_n_queens(n):
    cols, diagonals, anti_diagonals = set(), set(), set()

    def place(row):
        if row == n:
            return 1
        count = 0
        for col in range(n):
            if (col in cols or row - col in diagonals
                    or row + col in anti_diagonals):
                continue
            cols.add(col)                    # choose
            diagonals.add(row - col)
            anti_diagonals.add(row + col)
            count += place(row + 1)          # explore
            cols.remove(col)                 # undo
            diagonals.remove(row - col)
            anti_diagonals.remove(row + col)
        return count

    return place(0)

print(count_n_queens(4), count_n_queens(8))

Try it yourself

• Change size to 5, 6 and 8: they have 10, 4 and 92 solutions.
• Print every solution as a list of columns, not only the first as a board.
• Try a size of 2 or 3: there are no solutions, so solutions[0] fails with an IndexError. Check that the list isn't empty before drawing the board.
• Count how many times place puts a queen down, and compare it with n!: 16 against 24 for 4 queens.

More backtracking programs

• Python Program to Print All Permutations Intermediate
• Python Program to Find All Subsets of a Set Intermediate