N-Queens

#How does it work?

Backtracking builds a solution step by step and, as soon as a step can't lead to a solution, undoes it and tries another option. Instead of blindly trying every possibility, it prunes hopeless branches early.

The N-Queens problem is the classic example: place n queens on an n × n chessboard so that none attacks another. A queen attacks every piece on its row, column and diagonals.

Since every row needs exactly one queen, we go row by row. In each row we put a queen on the first column no queen above attacks and move to the next row. If a row has no safe column left, the queen in the row above is removed and its next column is tried.

An 8 × 8 board has 92 solutions. There are over 4 billion ways to drop 8 queens on 64 squares, yet backtracking tries only a few thousand squares.

#Try it yourself

#Step by step

1. 01Start at the first row.
2. 02For each column in the row: skip it if a queen above attacks the square.
3. 03If it is safe, place a queen and move to the next row; if the last row is filled, a solution is found.
4. 04If a row has no safe square, go back: remove the queen in the row above and try its next column.

#Example code

The same algorithm in 8 languages. Every program is compiled, run and checked to print the same output.

def solve(n: int):
    """First solution as a list of columns (one per row), or None."""
    queens = []  # queens[row] = column

    def safe(row: int, col: int) -> bool:
        return all(c != col and abs(c - col) != row - r for r, c in enumerate(queens))

    def place(row: int) -> bool:
        if row == n:
            return True
        for col in range(n):
            if safe(row, col):
                queens.append(col)
                if place(row + 1):
                    return True
                queens.pop()  # dead end: backtrack
        return False

    return queens if place(0) else None


def count(n: int) -> int:
    """All solutions, with sets of used columns and diagonals for O(1) checks."""
    cols, diag1, diag2 = set(), set(), set()

    def place(row: int) -> int:
        if row == n:
            return 1
        total = 0
        for col in range(n):
            if col in cols or row - col in diag1 or row + col in diag2:
                continue
            cols.add(col)
            diag1.add(row - col)
            diag2.add(row + col)
            total += place(row + 1)
            cols.remove(col)
            diag1.remove(row - col)
            diag2.remove(row + col)
        return total

    return place(0)


print(" ".join(str(c + 1) for c in solve(4)))  # 1-based columns by row
print(count(8))

#Complexity

One queen per row shrinks the search from nⁿ to n!, and pruning with the attack check cuts it far further. With three boolean arrays for columns and both diagonal directions, each check is O(1). With bit masks, all solutions can be counted quickly up to about n = 15.

#When to use it?

Backtracking is the general pattern for "find a placement that satisfies the constraints" problems: Sudoku, puzzles, maze solving, constraint satisfaction (timetables, exam schedules), graph colouring and generating combinations.

#Practice

Log in to answer questions and save your progress.

#Up next

Lessons that build on this one:

• Sudoku Solver