Getting Started with Backtracking: Solving Eight Queens in C and Python

Backtracking is a hurdle almost everyone meets when studying search problems systematically. On the surface it looks like brute-force enumeration, but the real point is not trying every case: it is spotting an invalid choice as early as possible during the search and retreating immediately.

The eight queens problem is the classic introduction to backtracking. The rules are simple, yet typical enough to make “make a choice, recurse, undo the choice” clear.

This article starts from zero and works through the eight queens problem step by step with the standard backtracking-plus-pruning approach, giving complete implementations in both C and Python.

1. What the eight queens problem is

The problem asks:

Place 8 queens on an 8 × 8 board so that no two queens can attack each other.

A queen attacks along:

• the same row
• the same column
• the same main diagonal
• the same anti-diagonal

So we need to find every arrangement that satisfies the constraints and count the total number of solutions.

The classic result for eight queens is that there are 92 solutions.

2. Why this problem suits backtracking

Enumerating brute force with no thought at all — every square either holds a queen or does not — gives an enormous search space.

But this problem has a natural way in:

Place the queens row by row.

That is:

• place one queen in row 0
• place one queen in row 1
• place one queen in row 2
• …
• continue through row 7

This has two benefits:

• each row holds exactly one queen, so row conflicts disappear automatically
• only column and diagonal conflicts still need checking

The problem then becomes:

In the current row, try placing the queen in some column; if it is legal, recurse into the next row; if it is not, move on and try another position.

That is the most typical backtracking structure there is.

3. The three steps of backtracking

The core of backtracking fits in three lines:

1. Make a choice
2. Recurse into the next level
3. Undo the choice

Mapped onto eight queens, the correspondence is direct:

• Make a choice: try placing this row’s queen in some column
• Recurse: move on to handle the next row
• Undo the choice: remove the queen just placed, restore the state, and try another column

Undoing the choice matters enormously here. Backtracking does not follow one path to the end; the moment the current branch turns out to be a dead end, it must step back and choose again.

4. Designing the state

To write the program clearly, first work out exactly what information has to be recorded.

1. Use board[row] = col for queen positions

For example:

board[0] = 0
board[1] = 4
board[2] = 7

means:

• the queen in row 0 sits in column 0
• the queen in row 1 sits in column 4
• the queen in row 2 sits in column 7

2. Use cols[col] to record whether a column is occupied

If a column already holds a queen, the current row cannot place one in that column.

3. Use main_diag[row - col + n - 1] for the main diagonal

A main diagonal is characterised by a constant row - col.

Since that value can be negative, an offset of n - 1 is normally added.

4. Use anti_diag[row + col] for the anti-diagonal

An anti-diagonal is characterised by a constant row + col.

5. Why there is no separate record of occupied rows

Because the recursion already proceeds row by row:

• recursion level 0 handles row 0
• recursion level 1 handles row 1
• recursion level 2 handles row 2

Each level therefore places exactly one queen in one row by construction, so no extra row state is needed.

5. What pruning actually removes

Pruning means discovering, before the search reaches the bottom, that a path cannot possibly succeed, and stopping there.

In eight queens, when about to place a queen at (row, col), any one of the following conditions is enough to skip it:

• the column already holds a queen
• the main diagonal already holds a queen
• the anti-diagonal already holds a queen

This is why eight queens is the classic backtracking-plus-pruning problem: it does not probe blindly, but rules out invalid branches as it goes.

6. How the search unfolds

The whole search can be understood as a tree:

• each level represents a row
• each branch represents choosing a column for that row
• if a position is illegal, that branch is not explored any deeper

A simple example:

• The left-to-right search reaches the prefix [0, 2, 4, 1, 3] for the first five rows.
• At row 5, columns 0 through 4 are occupied; columns 5, 6 and 7 are all attacked diagonally.
• Row 5 has no legal move, so return to row 4, undo column 3 and try its remaining columns.
• Retreat further only when that level exhausts its candidates, not all the way to row 0 after every conflict.

That is the “probe forward, retreat when blocked” behaviour of backtracking.

7. Python implementation

Here is the Python version first. It prints every solution and reports the total at the end.

N = 8
cols = [False] * N
main_diag = [False] * (2 * N - 1)
anti_diag = [False] * (2 * N - 1)
board = [-1] * N
solution_count = 0


def print_board():
    for row in range(N):
        line = ["."] * N
        line[board[row]] = "Q"
        print(" ".join(line))
    print()


def backtrack(row: int) -> None:
    global solution_count

    if row == N:
        solution_count += 1
        print(f"Solution {solution_count}:")
        print_board()
        return

    for col in range(N):
        d1 = row - col + N - 1
        d2 = row + col

        if cols[col] or main_diag[d1] or anti_diag[d2]:
            continue

        board[row] = col
        cols[col] = True
        main_diag[d1] = True
        anti_diag[d2] = True

        backtrack(row + 1)

        cols[col] = False
        main_diag[d1] = False
        anti_diag[d2] = False
        board[row] = -1


def solve_eight_queens() -> None:
    global solution_count
    solution_count = 0
    cols[:] = [False] * N
    main_diag[:] = [False] * (2 * N - 1)
    anti_diag[:] = [False] * (2 * N - 1)
    board[:] = [-1] * N
    backtrack(0)
    print(f"Total solutions: {solution_count}")


if __name__ == "__main__":
    solve_eight_queens()

The key parts of this code

• row == N means all 8 rows hold a queen, so a complete solution has been found
• if cols[col] or main_diag[d1] or anti_diag[d2] performs the legality check
• state is marked as occupied before recursing and restored afterwards

This is the most typical form of the standard backtracking template.

The entry function also resets the counter and arrays. Undoing a recursive branch restores occupancy, but does not reset solution_count. The old version returned totals of 92 and 184 when called twice in one process; both calls now report 92. Global state remains useful for this sequential demonstration, but this is not a thread-safe solver interface.

8. C implementation

Now the C version. The algorithm is identical to the Python one; only the style is lower level.

#include <stdbool.h>
#include <stdio.h>

#define N 8

_Static_assert(N >= 1 && N <= 12, "Teaching example: N must be 1..12");

static bool cols[N];
static bool main_diag[2 * N - 1];
static bool anti_diag[2 * N - 1];
static int board[N];
static int solution_count = 0;

void print_board(void) {
    for (int row = 0; row < N; row++) {
        for (int col = 0; col < N; col++) {
            if (board[row] == col) {
                printf("Q ");
            } else {
                printf(". ");
            }
        }
        printf("\n");
    }
    printf("\n");
}

void backtrack(int row) {
    if (row == N) {
        solution_count++;
        printf("Solution %d:\n", solution_count);
        print_board();
        return;
    }

    for (int col = 0; col < N; col++) {
        int d1 = row - col + N - 1;
        int d2 = row + col;

        if (cols[col] || main_diag[d1] || anti_diag[d2]) {
            continue;
        }

        board[row] = col;
        cols[col] = true;
        main_diag[d1] = true;
        anti_diag[d2] = true;

        backtrack(row + 1);

        cols[col] = false;
        main_diag[d1] = false;
        anti_diag[d2] = false;
        board[row] = -1;
    }
}

void solve_eight_queens(void) {
    solution_count = 0;
    for (int i = 0; i < N; i++) {
        cols[i] = false;
        board[i] = -1;
    }
    for (int i = 0; i < 2 * N - 1; i++) {
        main_diag[i] = false;
        anti_diag[i] = false;
    }
    backtrack(0);
    printf("Total solutions: %d\n", solution_count);
}

int main(void) {
    solve_eight_queens();
    return 0;
}

The languages differ but the reasoning is the same:

• handle row row at the current level
• enumerate every possible column in that row
• recurse when the position is legal
• undo the state once the recursion returns

9. Example output

Trying columns from left to right, the column indices of the first solution the program finds are:

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

The corresponding board is:

Q . . . . . . .
. . . . Q . . .
. . . . . . . Q
. . . . . Q . .
. . Q . . . . .
. . . . . . Q .
. Q . . . . . .
. . . Q . . . .

The program finishes by printing:

Total solutions: 92

10. Time and space complexity

Time complexity

Distinguish the legal search tree from the candidate checks in the code. Level r contains at most N!/(N-r)! legal column prefixes; summing the levels gives an O(N!) upper bound on nodes. Diagonal pruning reduces the actual count.

The reasoning is:

• row 0 tries at most N positions
• row 1 tries at most N - 1 positions
• row 2 tries at most N - 2 positions
• and so on downward

The N, N-1, N-2 sequence above counts unoccupied columns, not iterations of this implementation’s for col in range(N). Each nonterminal node still checks N columns. Ignoring printing, O(N × N!) is a clearer loose time bound for this array implementation. Printing S whole boards additionally writes about S × N² cells; that cost is not free in a timing comparison.

Space complexity

The space cost comes mainly from:

• recursion depth O(N)
• the column and diagonal state arrays O(N)

So overall space complexity can be treated as O(N).

11. What is genuinely worth learning here

The most important thing about eight queens is not solving one problem, but absorbing these backtracking ideas:

1. Define the search levels first, such as recursing by row here
2. Be explicit about which state must be recorded
3. Prune invalid branches as early as possible
4. Undo the previous choice when the recursion returns

Once these genuinely make sense, permutations, combinations, subsets, sudoku and parenthesis generation all turn out to share very similar underlying structure.

12. Backtracking state and verification table

Judging whether a piece of eight queens backtracking code is reliable takes more than seeing it print one board. It is better to check the search state, the pruning conditions and the final count separately. The table below works as a minimum audit record when reproducing the experiment.

Checkpoint	Where it lives in the code	What to verify
Search levels	backtrack(row)	Each level handles exactly one row, and recursion depth never exceeds N.
Column conflicts	cols[col]	No column holds two queens, and the flag must return to false on undo.
Diagonal conflicts	row + col and row - col + N - 1	Both diagonal indices stay in range and match the board’s attack directions.
Backtrack restore	State undo after the recursive call	board, the column array and both diagonal arrays all return to their pre-recursion state.
Result check	solution_count	With N = 8 the output should be Total solutions: 92.

Check all 92 boards, not just the final counter

A final count of 92 is insufficient: an implementation could emit duplicates or compensate for missing boards with invalid ones. The 2026-09-07 check therefore retained every column sequence, checked uniqueness and row/column/diagonal constraints, and compared the whole set against an enumeration of all 8! column permutations. These are all coordinate-distinct boards; rotations and reflections are not merged.

Download the code and verification package, extract it and run python3 audit_queens.py. It needs only the Python standard library and a C compiler supporting C11, AddressSanitizer and UndefinedBehaviorSanitizer. The 92-board reference CSV was generated by execution, not copied by hand. After running the package, independently check it with:

import csv
from itertools import permutations

with open("results/solutions-8.csv", newline="") as f:
    reader = csv.reader(f)
    next(reader)
    boards = [tuple(map(int, row)) for row in reader]

expected = {
    p for p in permutations(range(8))
    if all(abs(p[i] - p[j]) != i - j
           for i in range(8) for j in range(i))
}
assert len(boards) == len(set(boards)) == 92
assert set(boards) == expected
print("all 92 boards match the permutation check")

This checker reuses neither the solver’s occupancy arrays nor its masks. If an assertion fails, distinguish duplicate, invalid and missing boards instead of changing the printed count to 92. For another formulation, see the Google OR-Tools N-queens constraint model.

Observed Python array-search record, N=8

Observation	Result
Entries by depth, including root and terminal level	1, 8, 42, 140, 344, 568, 550, 312, 92
Total recursive entries	2057
Candidate loop iterations	8 × (2057 - 92) = 15720
Another call in the same process	92 again, not an accumulated 184

The package also tests N=1 through 12, yielding 1, 0, 0, 2, 10, 4, 40, 92, 352, 724, 2680, 14200 solutions. Both languages and state representations agree on the complete solution sequence. Only N≤8 is checked against exhaustive permutations; for N=9 through 12, agreement between implementations is not claimed as equally strong independent validation. Both C versions passed the two sanitizer checks at N=8. Compiler information, source hashes and outputs are in the execution record.

To run the tutorial sources separately:

python3 queens_array.py
cc -std=c11 -O2 -Wall -Wextra -pedantic queens_array.c -o queens_array
./queens_array

The C demonstration explicitly permits N=1 through 12; it is not an arbitrary-size solver. Start with the default N=8. The verifier changes N in temporary test copies and calls each implementation twice in one process without changing the downloaded sources. The C newline escapes in this English article have also been restored, so board output matches the Chinese version.

13. Summary

The eight queens problem is an excellent starting point for understanding backtracking, because it combines:

• a clear search structure
• typical pruning conditions
• intuitive state design
• the standard “make a choice → recurse → undo the choice” flow

If you are new to backtracking, type this standard version out yourself first. Once the framework is second nature, the bitwise-optimised version makes it far easier to see what state compression is actually optimising.

To keep going, read the follow-up article:

Backtracking, Advanced: Optimising Eight Queens with Bitwise Operations (C / Python)