Abstract flowing gradient in deep indigo and blue tones, smooth and luminous, evoking a modern digital learning atmosphere

Computer Science and programming articles. We do not sell courses.

Implementing a Solution to the N-Queens Problem

The N-Queens problem asks us to place N chess queens on an N × N chessboard so that no two queens can attack each other. A queen attacks across a row, a column, and either diagonal. The task is usually to find every valid arrangement, although some applications only need one solution or the number of possible solutions.

This is a classic backtracking problem because each placement creates a smaller decision problem. We place one queen at a time, test whether the partial board remains valid, and undo the placement when no legal continuation exists. The pattern appears in constraint satisfaction, scheduling, route planning, and many LeetCode-style search problems.

For a learner in Australia, this is a useful exercise whether you are studying computer science at the University of Melbourne, preparing for a software interview in Sydney, or practising Python during a rainy afternoon in Hobart. It demonstrates how a brute-force search can become practical when invalid branches are rejected early.

The most important implementation choice is how the board state is represented. A two-dimensional character grid is easy to display, while sets of occupied columns and diagonals make conflict checks constant time. The comparison below shows the trade-off between common approaches.

Approach Conflict check Typical purpose Main drawback
Full board scan O(N) First implementation Repeats work frequently
Boolean arrays O(1) Fast backtracking Requires careful indexing
Sets of columns and diagonals O(1) average Clear Python solution Hash-set overhead
Bit masks O(1) bit operations High-performance search Less intuitive

Understanding The Constraints

A board contains N rows and N columns, but placing at most one queen in each row is sufficient. If two queens occupied the same row, the arrangement would already be invalid. Therefore, the recursive algorithm can process rows from top to bottom and choose a column for the queen in each row.

For a queen at coordinates (row, column), the occupied column is identified by column. The two diagonal directions can be represented with simple arithmetic:

Two squares lie on the same descending diagonal when their row - column values match. They lie on the same ascending diagonal when their row + column values match. This turns a geometric attack rule into three set-membership checks.

The search stops successfully when row == N, because every row has received a valid queen. If no column is safe in the current row, the function returns to its caller and removes the previous queen. This return-and-remove step is the defining action of backtracking.

Designing The Backtracking Search

A useful state description is simply the current row plus three collections: occupied columns, occupied descending diagonals, and occupied ascending diagonals. The board itself can be stored as a list of lists so that completed arrangements can be copied into the result list.

The pseudocode is short:

search(row):
    if row == N:
        save the current board
        return

    for each column:
        diagonal_one = row - column
        diagonal_two = row + column

        if column or either diagonal is occupied:
            continue

        place a queen
        mark the column and diagonals
        search(row + 1)
        remove the queen
        unmark the column and diagonals

The order of these operations matters. A queen must be marked before the recursive call so deeper rows can detect it. It must be unmarked after the call so that the next candidate column sees the board state from before the attempted placement.

This technique is the same general pattern used when solving a maze, generating permutations, or assigning tasks under constraints. A partial solution is extended while it remains legal; once it becomes impossible, the algorithm abandons that branch rather than continuing to build a known-invalid answer.

Writing The Python Implementation

The following implementation returns every solution in the familiar list-of-strings format. A . represents an empty square and Q represents a queen.

def solve_n_queens(n: int) -> list[list[str]]:
    board = [["."] * n for _ in range(n)]
    columns = set()
    diagonals_down = set()  # row - column
    diagonals_up = set()    # row + column
    solutions = []

    def search(row: int) -> None:
        if row == n:
            solutions.append(["".join(line) for line in board])
            return

        for column in range(n):
            diagonal_down = row - column
            diagonal_up = row + column

            if (
                column in columns
                or diagonal_down in diagonals_down
                or diagonal_up in diagonals_up
            ):
                continue

            board[row][column] = "Q"
            columns.add(column)
            diagonals_down.add(diagonal_down)
            diagonals_up.add(diagonal_up)

            search(row + 1)

            board[row][column] = "."
            columns.remove(column)
            diagonals_down.remove(diagonal_down)
            diagonals_up.remove(diagonal_up)

    search(0)
    return solutions

For n = 4, the function produces two arrangements:

[
    [".Q..", "...Q", "Q...", "..Q."],
    ["..Q.", "Q...", "...Q", ".Q.."]
]

The board is mutated during the search, but each result is converted into new strings before the next branch changes it. Without that copy, every entry in solutions could end up referring to the final state of the same mutable board.

The function also needs a defined policy for small inputs. There are no solutions for n = 2 or n = 3, while n = 1 has one solution. The implementation handles these cases naturally. For n = 0, you may choose to return an empty list or treat the empty board as one mathematical solution; the right choice depends on the calling program’s specification.

Analysing Performance And Memory

A simple upper bound for the search is O(N!), because the first row has N choices, the second has roughly N − 1 choices, and so on. The diagonal constraints eliminate many branches, so real execution is usually much faster than this loose bound. Still, generating every solution has an unavoidable output cost because the program must construct each arrangement.

With sets, each conflict check and update takes O(1) average time. The board requires O(N²) space, and the three tracking sets require O(N) space. The recursion depth is O(N). If the function stores all solutions, the result itself can require substantial additional memory.

It is useful to distinguish this search from numerical optimisation. A model such as ridge regression changes continuous parameters using a regularisation objective, whereas N-Queens explores discrete placements and rejects states that violate hard constraints. Both problems reward careful state representation, but their algorithms and complexity analyses are different.

When only one arrangement is needed, the function can return immediately after finding the first complete board. That avoids storing every solution and may make the program suitable for an interactive checker or a coding interview. A solver for counting arrangements can increment a counter instead of copying each board, reducing output-related memory use.

Improving The Solver With Bit Masks

Sets make the implementation readable, but bit masks can reduce allocation and membership overhead. An integer uses one bit for each column or diagonal. A set bit means that the position is already occupied. The available positions for a row can then be computed with bitwise operations.

A compact version is:

def count_n_queens(n: int) -> int:
    full = (1 << n) - 1

    def search(columns: int, down: int, up: int) -> int:
        if columns == full:
            return 1

        available = full & ~(columns | down | up)
        total = 0

        while available:
            bit = available & -available
            available -= bit

            total += search(
                columns | bit,
                ((down | bit) << 1) & full,
                (up | bit) >> 1,
            )

        return total

    return search(0, 0, 0)

Here, available & -available isolates the lowest available bit. After selecting it, available -= bit removes it from consideration. The diagonal masks shift as the search moves to the next row: one direction shifts left and the other shifts right.

Bit operations are especially useful when the requirement is to count solutions rather than display them. They also demonstrate a common systems-programming idea: representing a collection of boolean values inside an integer. For a first implementation, however, sets are usually easier to debug and explain.

A Fibonacci heap is designed for a different workload, where operations such as decrease-key are central; its behaviour is discussed in Fibonacci heap operations. It is not a natural replacement for the N-Queens state sets because this search repeatedly tests membership and performs backtracking removals rather than extracting minimum-priority items.

Testing And Extending The Program

Testing should cover both the answer and the structure of each answer. For n = 1, expect one board. For n = 2 and n = 3, expect no boards. For n = 4, expect two. Larger known counts can expose errors in diagonal indexing, cleanup, or result copying.

A validator makes tests independent from the solver’s internal logic:

def is_valid(board: list[str]) -> bool:
    n = len(board)
    queens = [
        (row, column)
        for row in range(n)
        for column in range(n)
        if board[row][column] == "Q"
    ]

    if len(queens) != n:
        return False

    for index, (row_a, column_a) in enumerate(queens):
        for row_b, column_b in queens[index + 1:]:
            same_row = row_a == row_b
            same_column = column_a == column_b
            same_diagonal = abs(row_a - row_b) == abs(column_a - column_b)

            if same_row or same_column or same_diagonal:
                return False

    return True

For every generated board, assert that is_valid(board) is true and that each row contains exactly one Q. Property-based testing can generate several board sizes and check these rules automatically. This is valuable in university assignments and take-home interview tasks, where a solution that works for n = 4 may still fail for edge cases.

The same solver can be adapted to return one solution, count all solutions, or display a board in a terminal. On an Australian laptop using a standard Python installation, the set-based approach is generally fast enough for learning and moderate values of N. Larger inputs call for symmetry breaking, bit masks, or a counting-only design rather than storing every board.