N Queens¶

Problem¶

Place n queens on an n x n chessboard such that no two queens threaten each other (no shared row, column, or diagonal). Return all distinct solutions.

Approach¶

Backtracking row by row. Track occupied columns, positive diagonals (r + c), and negative diagonals (r - c) with sets. Only valid placements are explored.

When to Use¶

Constraint placement — "place N items with mutual exclusion constraints", "non-attacking queens", "conflict-free assignment". Row-by-row backtracking with column/diagonal conflict sets. See also: CSP solver.

Complexity¶


Time	`O(n!) (with pruning)`
Space	`O(n)`

Implementation¶

SolutionTestsChallenge

n_queens ¶

N-Queens — place n queens on n x n board with no attacks.

Problem

Place n queens on an n x n chessboard such that no two queens threaten each other (no shared row, column, or diagonal). Return all distinct solutions.

Approach

Backtracking row by row. Track occupied columns, positive diagonals (r + c), and negative diagonals (r - c) with sets. Only valid placements are explored.

When to use

Constraint placement — "place N items with mutual exclusion constraints", "non-attacking queens", "conflict-free assignment". Row-by-row backtracking with column/diagonal conflict sets. See also: CSP solver.

Complexity

Time: O(n!) (with pruning) Space: O(n)

solve_n_queens ¶

solve_n_queens(n: int) -> list[list[str]]

Return all solutions as lists of strings ('.' and 'Q').

len(solve_n_queens(4)) 2 solve_n_queens(1) [['Q']]

Source code in src/algo/backtracking/n_queens.py

def solve_n_queens(n: int) -> list[list[str]]:
    """Return all solutions as lists of strings ('.' and 'Q').

    >>> len(solve_n_queens(4))
    2
    >>> solve_n_queens(1)
    [['Q']]
    """
    result: list[list[str]] = []
    cols: set[int] = set()
    pos_diag: set[int] = set()  # r + c constant on / diagonals
    neg_diag: set[int] = set()  # r - c constant on \\ diagonals
    queens: list[int] = []  # queens[row] = col

    def backtrack(r: int) -> None:
        if r == n:
            board = ["." * c + "Q" + "." * (n - c - 1) for c in queens]
            result.append(board)
            return
        for c in range(n):
            if c in cols or (r + c) in pos_diag or (r - c) in neg_diag:
                continue
            cols.add(c)
            pos_diag.add(r + c)
            neg_diag.add(r - c)
            queens.append(c)
            backtrack(r + 1)
            queens.pop()
            cols.remove(c)
            pos_diag.remove(r + c)
            neg_diag.remove(r - c)

    backtrack(0)
    return result

tests/backtracking/test_n_queens.py

"""Tests for N-Queens."""

from algo.backtracking.n_queens import solve_n_queens


class TestNQueens:
    def test_one_queen(self) -> None:
        assert solve_n_queens(1) == [["Q"]]

    def test_four_queens(self) -> None:
        result = solve_n_queens(4)
        assert len(result) == 2

    def test_eight_queens(self) -> None:
        result = solve_n_queens(8)
        assert len(result) == 92

    def test_no_solution_for_two(self) -> None:
        assert solve_n_queens(2) == []

    def test_no_solution_for_three(self) -> None:
        assert solve_n_queens(3) == []

    def test_board_validity(self) -> None:
        """Check that no two queens attack each other in any 4-queens solution."""
        for board in solve_n_queens(4):
            queens = [(r, row.index("Q")) for r, row in enumerate(board)]
            # No shared column
            cols = [c for _, c in queens]
            assert len(cols) == len(set(cols))
            # No shared diagonal
            for i in range(len(queens)):
                for j in range(i + 1, len(queens)):
                    r1, c1 = queens[i]
                    r2, c2 = queens[j]
                    assert abs(r1 - r2) != abs(c1 - c2)

Implement it yourself

Run: just challenge backtracking n_queens

Then implement the functions to make all tests pass. Use just study backtracking for watch mode.

Reveal Solution

n_queens ¶

N-Queens — place n queens on n x n board with no attacks.

Problem

Place n queens on an n x n chessboard such that no two queens threaten each other (no shared row, column, or diagonal). Return all distinct solutions.

Approach

Backtracking row by row. Track occupied columns, positive diagonals (r + c), and negative diagonals (r - c) with sets. Only valid placements are explored.

When to use

Constraint placement — "place N items with mutual exclusion constraints", "non-attacking queens", "conflict-free assignment". Row-by-row backtracking with column/diagonal conflict sets. See also: CSP solver.

Complexity

Time: O(n!) (with pruning) Space: O(n)

solve_n_queens ¶

solve_n_queens(n: int) -> list[list[str]]

Return all solutions as lists of strings ('.' and 'Q').

len(solve_n_queens(4)) 2 solve_n_queens(1) [['Q']]

Source code in src/algo/backtracking/n_queens.py

def solve_n_queens(n: int) -> list[list[str]]:
    """Return all solutions as lists of strings ('.' and 'Q').

    >>> len(solve_n_queens(4))
    2
    >>> solve_n_queens(1)
    [['Q']]
    """
    result: list[list[str]] = []
    cols: set[int] = set()
    pos_diag: set[int] = set()  # r + c constant on / diagonals
    neg_diag: set[int] = set()  # r - c constant on \\ diagonals
    queens: list[int] = []  # queens[row] = col

    def backtrack(r: int) -> None:
        if r == n:
            board = ["." * c + "Q" + "." * (n - c - 1) for c in queens]
            result.append(board)
            return
        for c in range(n):
            if c in cols or (r + c) in pos_diag or (r - c) in neg_diag:
                continue
            cols.add(c)
            pos_diag.add(r + c)
            neg_diag.add(r - c)
            queens.append(c)
            backtrack(r + 1)
            queens.pop()
            cols.remove(c)
            pos_diag.remove(r + c)
            neg_diag.remove(r - c)

    backtrack(0)
    return result