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:

• row 0 first tries column 0
• move into row 1 and probe from left to right
• if row 1 has no legal position at all, then row 0 in column 0 is a dead end
• so return to row 0 and try column 1 instead

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:
    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.

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 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) {
    backtrack(0);
    printf("Total solutions: %dn", solution_count);
}

int main(void) {
    for (int i = 0; i < N; i++) {
        board[i] = -1;
    }

    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

Eight queens remains a search problem at heart, and its exact time complexity is not easy to write as a single precise formula, but in order of magnitude it can be understood as close to O(N!).

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 real search volume is smaller, because pruning cuts away a large number of invalid branches early.

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.

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)