Solving the 8-Queens Problem Using Backtracking

Verified Sources

Sep 11, 2026

The 8-Queens problem asks us to place eight chess queens on an $8 \times 8$ chessboard so that no two queens attack one another. Because a queen attacks horizontally, vertically, and diagonally, a valid arrangement must contain no pair of queens in the same row, column, or diagonal.

The problem is a classic example of Backtracking and Constraint Satisfaction.

The generalized form is the N-Queens problem: place $N$ queens on an $N \times N$ board under the same restrictions. The 8-Queens problem has 92 distinct solutions, or 12 fundamental solutions when rotations and reflections are considered equivalent.

Learning objectives

By the end of this section, you should be able to:

State the constraints of the 8-Queens problem.
Explain why backtracking is appropriate.
Design a recursive solution.
Detect column and diagonal conflicts efficiently.
Trace an example involving placement and backtracking.
Analyze the algorithm’s time and space requirements.

Eight queens puzzle - Defines the puzzle and reports 92 distinct and 12 fundamental solutions. ↩ ↩²

1. Modeling the Problem

A convenient representation places exactly one queen in each row. The algorithm processes rows from top to bottom and chooses a column for the queen in each row.

Let

x_r = \text{the column containing the queen in row } r

where $r \in \{0,1,\ldots,7\}$ and $x_r \in \{0,1,\ldots,7\}$ .

A complete solution must satisfy:

Constraint 1: Different columns

For every pair of rows $r_1$ and $r_2$ :

x_{r_1} \ne x_{r_2}

This prevents two queens from sharing a column.

Constraint 2: Different diagonals

Two squares $(r_1,x_{r_1})$ and $(r_2,x_{r_2})$ share a diagonal when:

|r_1-r_2| = |x_{r_1}-x_{r_2}|

Therefore, valid placements must satisfy:

|r_1-r_2| \ne |x_{r_1}-x_{r_2}|

Placing one queen per row automatically prevents row conflicts. Thus, the algorithm only needs to test columns and diagonals.

Key Modeling Insight

Place queens row by row. This guarantees that no two queens occupy the same row, reducing the problem to column and diagonal checks.

2. Why Backtracking Works

A naïve method could try every possible column assignment for eight rows. Since each row has eight choices, this produces at most

8^8 = 16{,}777{,}216

possible assignments, many of which immediately violate constraints.

Backtracking improves the search by rejecting a partial arrangement as soon as it becomes impossible to complete. This is called Pruning.

The method follows a depth-first search pattern:

Choose the next row.
Try each column in that row.
If the position is safe, place a queen.
Recursively solve the remaining rows.
If the recursive attempt fails, remove the queen.
Try another column.

A recursive call represents a partial board configuration. For example:

[0,4,7]

means:

Row $0$ has a queen in column $0$ .
Row $1$ has a queen in column $4$ .
Row $2$ has a queen in column $7$ .

The next recursive call attempts to place the queen in row $3$ .

Backtracking Procedure

1
Step 1
No queens have been placed. Begin at row 0.
2
Step 2
Process rows from top to bottom. Because there is one queen per row, row conflicts cannot occur.
3
Step 3
For the current row, examine columns from left to right.
4
Step 4
Reject a position if its column or either diagonal already contains a queen.
5
Step 5
Mark the selected column and diagonals as occupied.
6
Step 6
Move to the next row and repeat the same process.
7
Step 7
If no column is safe, remove the queen from the previous row and continue with the next available column there.
8
Step 8
When the algorithm reaches row 8, all eight queens have been placed safely. Store the board or column representation.

3. Efficient Safety Checking

For a queen at row $r$ and column $c$ , identify its diagonals using two indices:

Main diagonal: $r-c$
Anti-diagonal: $r+c$

Since $r-c$ can be negative, an array implementation commonly stores it using an offset of $N-1$ :

\text{mainIndex} = r-c+(N-1)

\text{antiIndex} = r+c

For an $8 \times 8$ board:

Columns require $8$ markers.
Main diagonals require $15$ markers.
Anti-diagonals require $15$ markers.

A position is safe exactly when:

\text{column}[c] = 0

and

\text{mainDiagonal}[r-c+(N-1)] = 0

and

\text{antiDiagonal}[r+c] = 0

This makes each safety check $O(1)$ instead of scanning previously placed queens.

N Queen Problem - Describes row-by-row backtracking, safety checks, and commonly cited complexity bounds. ↩

Search Representation for the 8-Queens Problem

The board has 8 columns and 15 diagonals in each diagonal direction.

4. Pseudocode

The following pseudocode finds all solutions:

1procedure solve(row):
2    if row == 8:
3        record the current board
4        return
5
6    for column from 0 to 7:
7        if column is unused
8           and main diagonal is unused
9           and anti-diagonal is unused:
10
11            place queen at (row, column)
12            mark column and both diagonals as used
13
14            solve(row + 1)
15
16            remove queen from (row, column)
17            unmark column and both diagonals

The most important operation is the final cleanup:

1remove queen
2unmark column
3unmark main diagonal
4unmark anti-diagonal

Without this restoration step, later branches would incorrectly treat old trial placements as permanent.

def solve_n_queens(n):
    board = [["." for _ in range(n)] for _ in range(n)]
    columns = [False] * n
    main_diagonals = [False] * (2 * n - 1)
    anti_diagonals = [False] * (2 * n - 1)
    solutions = []

    def backtrack(row):
        if row == n:
            solutions.append(
                ["".join(board_row) for board_row in board]
            )
            return

        for col in range(n):
            main_index = row - col + (n - 1)
            anti_index = row + col

            if (columns[col] or
                    main_diagonals[main_index] or
                    anti_diagonals[anti_index]):
                continue

            board[row][col] = "Q"
            columns[col] = True
            main_diagonals[main_index] = True
            anti_diagonals[anti_index] = True

            backtrack(row + 1)

            board[row][col] = "."
            columns[col] = False
            main_diagonals[main_index] = False
            anti_diagonals[anti_index] = False

    backtrack(0)
    return solutions

solutions = solve_n_queens(8)
print(len(solutions))
# 92

5. Worked Example: One Successful 8-Queens Arrangement

One valid solution can be represented by the column vector:

[0,4,7,5,2,6,1,3]

This means:

Row	Column	Board row
0	0	`Q.......`
1	4	`....Q...`
2	7	`.......Q`
3	5	`.....Q..`
4	2	`..Q.....`
5	6	`......Q.`
6	1	`.Q......`
7	3	`...Q....`

The complete board is:

1Q.......
2....Q...
3.......Q
4.....Q..
5..Q.....
6......Q.
7.Q......
8...Q....

Verifying the arrangement

The column values are:

0,4,7,5,2,6,1,3

All are distinct, so no two queens share a column.

For the main diagonals, calculate $r-c$ :

0,-3,-5,-2,2,-1,5,4

All values are distinct.

For the anti-diagonals, calculate $r+c$ :

0,5,9,8,6,11,7,10

All values are distinct.

Therefore, no two queens share a row, column, or diagonal.

Tracing a Backtracking Branch

1
Step 1
Try row 0, column 0. The partial representation is [0].
2
Step 2
Column 0 is blocked, and columns 1 and 2 are diagonally attacked. A later safe choice may be column 4, giving [0,4].
3
Step 3
The algorithm tries safe columns for rows 2, 3, and beyond. Every placement updates the column and diagonal markers.
4
Step 4
Suppose the current partial arrangement has no safe column for the next row. This means the current choices cannot lead to a complete solution.
5
Step 5
Remove the queen from the previous row and clear its three markers. This is the backtracking operation.
6
Step 6
Continue scanning columns in the previous row. A different choice may open a valid continuation.
7
Step 7
When the recursive call reaches row 8, the arrangement is a valid solution and is recorded.

6. A Smaller Trace That Clearly Shows Failure

Tracing all branches of the 8-Queens search is lengthy, so a 4-Queens branch illustrates the same mechanism more clearly.

Consider this partial placement:

1Q...
2..Q.
3....
4....

The queens are at $(0,0)$ and $(1,2)$ .

For row $2$ :

Column $0$ is occupied.
Column $1$ is attacked diagonally by the queen at $(0,0)$ .
Column $2$ is occupied.
Column $3$ is attacked diagonally by the queen at $(1,2)$ .

Therefore, row $2$ has no safe position.

The algorithm backtracks:

Remove the queen at $(1,2)$ .
Try another column in row $1$ .
Continue searching from the new partial arrangement.

This demonstrates the central principle:

A failed partial arrangement is discarded immediately rather than extended further.

Common Implementation Error

Do not forget to unmark the column and both diagonals after the recursive call. Failing to restore state causes false conflicts in later branches.

7. Correctness Argument

The algorithm is correct for two reasons.

Soundness

Every recorded arrangement is valid.

A queen is placed only when its column is unused.
A queen is placed only when its main diagonal is unused.
A queen is placed only when its anti-diagonal is unused.
Exactly one queen is placed in each processed row.

Therefore, when the algorithm records a board after processing all $8$ rows, no two queens attack one another.

Completeness

Every valid arrangement is eventually considered.

At each row, the algorithm tries every column that is not immediately invalid. If a partial placement can be extended to a solution, the algorithm explores that branch. If a branch cannot be extended, backtracking returns to the most recent decision and tries another possibility.

Thus, no valid arrangement is skipped. When configured to record every completed board, the algorithm finds all 92 solutions.

Eight queens puzzle - Defines the puzzle and reports 92 distinct and 12 fundamental solutions. ↩

8. Complexity Analysis

For the general $N$ -Queens problem, a common upper-bound description for straightforward backtracking is:

O(N!)

because placing one queen per row and rejecting used columns reduces the number of possible column permutations. A less-pruned formulation can be described by the looser bound $O(N^N)$ .

With column and diagonal arrays:

Safety checking: $O(1)$ per candidate position.
Recursion depth: $O(N)$ .
Auxiliary marker space: $O(N)$ .
Board storage for explicit solutions: $O(N^2)$ per stored board.
Output space for all solutions: proportional to the number of solutions returned.

For $N=8$ , the search is small enough to run quickly. For larger $N$ , performance can be improved using bit masks, symmetry breaking, variable ordering, and constraint propagation.

N Queen Problem - Describes row-by-row backtracking, safety checks, and commonly cited complexity bounds. ↩

Evolution of a Backtracking Search

Empty board

Depth 0

No queens have been assigned."

First row

Depth 1

Choose one of eight columns."

Extend a partial solution

Depth 2–7

Try safe positions while maintaining column and diagonal constraints."

Dead end

Failure point

No legal position exists in the current row."

Backtrack

Return step

Remove the most recently placed queen and try the next alternative."

Complete solution

Depth 8

All rows contain safe queens; record the arrangement."

9. Important Variations

Find one solution versus all solutions

To find only one solution, return immediately after the first complete arrangement:

1if row == N:
2    return true

To find every solution, record the board and continue searching after a solution is found.

Board representation

A board can be represented as:

A two-dimensional array of characters.
A one-dimensional array where board[row] stores the column.
Bit masks for columns and diagonals.

The one-dimensional representation is often sufficient because the row is implied by the array index.

Symmetry reduction

Rotating or reflecting a solution produces another solution. The 8-Queens problem has 92 distinct arrangements but only 12 fundamental arrangements under these symmetries. A solver can reduce duplicate work by restricting the first queen to part of the first row and generating symmetric variants afterward.

Bit-mask optimization

For larger values of $N$ , occupied columns and diagonals can be encoded as bits. A bitwise operation can then identify all available positions in a row at once. This preserves the backtracking idea while reducing constant-time overhead.

Eight queens puzzle - Defines the puzzle and reports 92 distinct and 12 fundamental solutions. ↩

Frequently Asked Questions

8-Queens Backtracking Review

1 / 7

Question · Term

What is the goal of the 8-Queens problem?

Click to reveal

Answer · Definition

Place eight queens on an 8 × 8 board so that no two share a row, column, or diagonal.

Exam Strategy

When explaining this algorithm, always state the choice, constraint check, recursive call, base case, and undo operation. These five parts capture the complete backtracking pattern.

Knowledge Check

Question 1 of 5

Q1Single choice

Which condition identifies a diagonal conflict between queens at (r1, c1) and (r2, c2)?

r1 = r2

c1 = c2

|r1 - r2| = |c1 - c2|

r1 + c1 = 0

Explore Related Topics

Semaphore and the Dining-Philosophers Solution Using Monitors

The content contrasts low‑level semaphores with high‑level monitors and shows how a monitor‑based solution avoids deadlock in the Dining Philosophers problem.

A semaphore offers atomic $wait$ / $signal$ on a counter, but misordered calls can cause deadlock or race conditions.
A monitor bundles shared state with procedures and uses condition variables ( $x.wait()$ , $x.signal()$ ) to wait for logical predicates rather than resource counts.
The monitor algorithm maintains an array $state[i]\in\{THINKING, HUNGRY, EATING\}$ and a condition variable $self[i]$ per philosopher; $test(i)$ grants $EATING$ only if both neighbors are not eating.
Because monitor entry is mutually exclusive and $test$ is invoked on neighbours after $putdown(i)$ , the solution guarantees safety (no adjacent eaters) and deadlock freedom, while starvation freedom depends on fairness of signaling.

FIFO Branch-and-Bound Uses a Queue

FIFO Branch-and-Bound expands live nodes in the exact order they are generated, so it is implemented with a queue.

A queue enforces first‑in‑first‑out, giving the algorithm a BFS‑like, level‑order traversal.
LIFO Branch‑and‑Bound uses a stack and least‑cost Branch‑and‑Bound uses a priority queue.
Bounding prunes unpromising nodes independently of the FIFO selection rule.
Pseudocode: initialize $Q$ , enqueue root, while $Q\neq\emptyset$ dequeue front, generate children, enqueue survivors.
The abstract answer is “queue,” not an array or other structure, even if an array may implement a queue.

Designing a Turing Machine for the 2’s Complement of a Binary String

Browse all research articles

Solving the 8-Queens Problem Using Backtracking

Learning objectives

Footnotes

1. Modeling the Problem

Constraint 1: Different columns

Constraint 2: Different diagonals

Key Modeling Insight

2. Why Backtracking Works

Backtracking Procedure

3. Efficient Safety Checking

Footnotes

Search Representation for the 8-Queens Problem

4. Pseudocode

5. Worked Example: One Successful 8-Queens Arrangement

Verifying the arrangement

Tracing a Backtracking Branch

6. A Smaller Trace That Clearly Shows Failure

Common Implementation Error

7. Correctness Argument

Soundness

Completeness

Footnotes

8. Complexity Analysis

Footnotes

Evolution of a Backtracking Search

Empty board

First row

Extend a partial solution

Dead end

Backtrack

Complete solution

9. Important Variations

Find one solution versus all solutions

Board representation

Symmetry reduction

Bit-mask optimization

Footnotes

Frequently Asked Questions

8-Queens Backtracking Review

What is the goal of the 8-Queens problem?

Exam Strategy

Knowledge Check

Explore Related Topics