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

In the previous eight queens article we used the most classic backtracking form: recurse by row, and use arrays to record whether each column, main diagonal and anti-diagonal is occupied. That version is easy to follow and works well on a first encounter with backtracking.

But go a little deeper and one question arises naturally: since every level has to work out which positions are still available, is there a faster way to write it?

This article continues with an optimised implementation of the eight queens problem: compress the state with bitwise operations and keep the same backtracking approach, but make the search run faster.

We still use backtracking and the nature of the problem does not change; what changes is how the state is represented. Complete implementations in Python and C follow at the end.

If you have not seen the standard form yet, read the introductory article first: Getting Started with Backtracking: Solving Eight Queens in C and Python.

1. What the optimisation actually optimises

In the standard form we normally maintain three groups of state:

• which columns already hold a queen
• which main diagonals are occupied
• which anti-diagonals are occupied

Representing this state with boolean arrays is intuitive, but every check and update has to touch several arrays.

The core idea of the bitwise version is:

Compress the occupancy state into the binary digits of an integer, so that one bitwise operation performs a large number of checks at once.

This style is very common in N queens, bitmask DP and subset enumeration. For eight queens it noticeably reduces constant overhead and makes the search more compact.

2. Representing board state in binary

Assume we still recurse row by row. When handling a given row, all we need to know is which columns in that row can still take a queen.

For an 8 x 8 board, an 8-bit binary number can represent the column state:

• bit 0 set to 1 means column 0 is occupied
• bit 1 set to 1 means column 1 is occupied
• …
• bit 7 set to 1 means column 7 is occupied

So three integers can represent the search state:

• cols: columns already occupied
• main_diag: attacks projected into the current recursive row in the direction of increasing column indices
• anti_diag: attacks projected into the current recursive row in the direction of decreasing column indices

The key point is that incoming masks describe the current row; only after adding the chosen position and shifting do the outgoing masks describe the next row. They are not the fixed diagonal indices used by the array implementation.

With that, the available positions in the current row can all be computed from a single expression.

3. Which positions the current row can still use

First define a mask:

LIMIT = (1 << N) - 1

When N = 8:

LIMIT = 0b11111111

that is, the low 8 bits are all 1.

Every position in the current row that cannot take a queen is:

cols | main_diag | anti_diag

So every position that can still take one is:

available = LIMIT & ~(cols | main_diag | anti_diag)

This line is well worth memorising; it is essentially the core of the bitwise N queens solution.

It means:

• merge the column, main-diagonal and anti-diagonal conflicts together
• invert that to get the positions theoretically available
• AND with LIMIT to keep only the low N bits that lie on the board

4. Taking the available positions one at a time

When available holds several usable positions, we try them one at a time, as before.

There is a very common bitwise trick for this:

pick = available & -available

It extracts the rightmost 1 in the binary representation.

For example, if:

available = 0b10110000

then:

pick = 0b00010000

So pick represents “the column to try first this time round”.

After trying it, remove that position from the candidate set:

available -= pick

Then continue looping until every available position in the row has been tried.

5. Updating the diagonal state when recursing to the next row

If the current row places a queen, then for the next row:

• << 1 moves an attack at column index c to c+1
• >> 1 moves an attack at column index c to c-1

In bitwise terms that is exactly a shift:

The notation has two orientations: bit 0 is written at the right of a binary string, but column 0 is printed at the left of this board. A left bit shift therefore moves towards increasing column indices, visually rightward on this board. Do not equate bit-string direction with board direction.

(main_diag | pick) << 1
(anti_diag | pick) >> 1

So the recursive call becomes:

solve(row + 1,
      cols | pick,
      (main_diag | pick) << 1,
      (anti_diag | pick) >> 1)

Note that the nature of the backtracking has not changed at all:

• make a choice
• descend into the next level
• carry on trying other positions once it returns

The difference is that integers are passed by value, so there is no need to restore state manually as with boolean arrays. That is one reason the bitwise form looks shorter.

6. Python implementation

Here is the optimised Python code. It prints the first solution and counts them all.

N = 8
LIMIT = (1 << N) - 1
positions = [0] * N
solution_count = 0
first_solution = None


def bit_to_col(bit: int) -> int:
    return bit.bit_length() - 1


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


def solve(row: int, cols: int, main_diag: int, anti_diag: int) -> None:
    global solution_count, first_solution

    if row == N:
        solution_count += 1
        if first_solution is None:
            first_solution = positions[:]
        return

    available = LIMIT & ~(cols | main_diag | anti_diag)

    while available:
        pick = available & -available
        available -= pick

        positions[row] = pick

        solve(
            row + 1,
            cols | pick,
            (main_diag | pick) << 1,
            (anti_diag | pick) >> 1,
        )

        positions[row] = 0


def solve_eight_queens():
    global solution_count, first_solution
    solution_count = 0
    first_solution = None
    positions[:] = [0] * N
    solve(0, 0, 0, 0)
    if first_solution is not None:
        print("First solution:")
        print_board(first_solution)
    else:
        print("No solution")
    print(f"Total solutions: {solution_count}")


if __name__ == "__main__":
    solve_eight_queens()

Key points for reading the code

• LIMIT truncates to the low 8 bits
• available holds every usable position in the current row
• pick extracts one usable position at a time
• positions[row] records the bit chosen for this row, which makes reconstructing the board easy later

There are no column or diagonal arrays here; all three constraints are compressed into integers.

The entry function resets the count, first solution and position array, so sequential calls do not accumulate results. A no-solution case no longer sends None into the board printer. Global state still makes concurrent calls inappropriate; a reusable library should keep state inside each invocation’s object or closure.

7. C implementation

Now the C version. The structure matches the Python one; only the language details differ.

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

#define N 8

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

static const uint32_t LIMIT = (UINT32_C(1) << N) - 1;
static uint32_t positions[N];
static uint32_t first_solution[N];
static int solution_count = 0;
static bool has_first_solution = false;

int bit_to_col(uint32_t bit) {
    int col = 0;
    while ((bit >>= 1) != 0) {
        col++;
    }
    return col;
}

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

void solve(int row, uint32_t cols, uint32_t main_diag, uint32_t anti_diag) {
    if (row == N) {
        solution_count++;
        if (!has_first_solution) {
            for (int i = 0; i < N; i++) {
                first_solution[i] = positions[i];
            }
            has_first_solution = true;
        }
        return;
    }

    uint32_t available = LIMIT & ~(cols | main_diag | anti_diag);

    while (available) {
        uint32_t pick = available & (UINT32_C(0) - available);
        available -= pick;

        positions[row] = pick;

        solve(
            row + 1,
            cols | pick,
            (main_diag | pick) << 1,
            (anti_diag | pick) >> 1
        );

        positions[row] = 0;
    }
}

void solve_eight_queens(void) {
    solution_count = 0;
    has_first_solution = false;
    for (int i = 0; i < N; i++) {
        positions[i] = 0;
        first_solution[i] = 0;
    }
    solve(0, 0, 0, 0);
    if (has_first_solution) {
        printf("First solution:\n");
        print_board(first_solution);
    } else {
        printf("No solution\n");
    }
    printf("Total solutions: %d\n", solution_count);
}

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

The things to watch in this code are:

The C masks now use uint32_t; UINT32_C(0) - available deliberately uses unsigned arithmetic to extract the low bit. The previous fixed N=8 did not hit signed overflow, but merely increasing N can move a signed result into its sign bit or make a shift reach the operand width. This demonstration uses a compile-time assertion to restrict N to 1 through 12, not a promise of arbitrary-size solving. See SEI CERT INT34-C for shift boundaries.

• pick = available & -available still extracts the lowest set bit
• integers are passed by value, so recursion needs no manual restore of cols or the diagonal state
• the first solution is stored separately purely to demonstrate board output

8. Example output

With this search order, the board for the first solution the program finds is:

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

Both programs finish by printing:

Total solutions: 92

9. Why this optimisation is faster

The conclusion first: bitwise optimisation does not change the exponential nature of the problem. What it optimises is constant overhead.

In the array-based form, every step has to:

• check several arrays
• update several arrays
• restore those arrays when backtracking

In the bitwise version:

• state is compressed into integers
• the available positions come from a single bitwise expression
• the recursion parameters form the new state naturally, with no complex structure to undo

The 2026-09-07 execution record for these Python implementations shows 2057 recursive entries in both versions, with 92 solutions. The array version checks 8 columns at each of 1965 nonterminal nodes: 15720 candidate-loop iterations. Each bitwise loop iteration creates one recursion edge: 2056 iterations. It does not prune additional legal search nodes; it avoids individually looping over conflicting columns.

These counts come from observed recursive entries and the loop structure. They are not CPU instruction counts, and 15720/2056 is not a runtime speedup. The array demonstration prints all 92 boards while the bitwise demonstration prints only the first. Timing them unchanged mixes in unequal output costs. A fair timing exercise first makes both count-only, then uses the same language, compiler flags and N over repeated measurements. No numerical runtime speedup is claimed here.

Complexity also needs assumptions: with a mask fitting in one machine word, the legal-candidate search tree has a loose O(N!) bound. Python arbitrary-precision integer operations are not constant cost for unbounded N. State compression does not eliminate combinatorial growth, and C mask width and counter range need separate checks.

10. When to use the standard form and when to use the optimised one

If this is your first time learning backtracking, I would still recommend mastering the standard form first, because it makes the structure of the problem easiest to see.

Once you understand these concepts:

• recursing by row
• column conflicts
• diagonal conflicts
• make a choice, recurse, undo the choice

then it is worth moving on to the bitwise version. It brings home the point that:

For many search problems, being able to write the recursion is not the whole story; how the state is represented determines performance and code quality just as much.

11. The core formulas, revisited

The heart of the optimised eight queens is not a different algorithm, but a more efficient state compression applied to the same backtracking process.

The three lines most worth remembering from this article are:

1. available = LIMIT & ~(cols | main_diag | anti_diag) gives the usable positions in the current row
2. pick = available & -available extracts the lowest set bit
3. the shifted masks describe the next row: left bit shift means column index +1, right bit shift means column index -1

12. Read masks from actual recursive entries

The table now contains two real entries from the execution, not unrelated illustrative numbers. Prefix [0,4] means the first two rows chose columns 0 and 4; row 2 is next. Only the low 8 bits are shown. The raw left-shifted mask can retain off-board high bits, which LIMIT removes when computing available.

Entry snapshots from one N=8 search

Variable	Prefix [0], row=1	Prefix [0,4], row=2
cols	00000001	00010001
main_diag	00000010	00100100
anti_diag	00000000	00001000
available	11111100	11000010
First candidate pick	00000100	00000010

Choosing column 4 between these states gives (00000010 | 00010000) << 1 = 00100100, and 00001000 on the right-shifted side. Available columns are therefore 1, 6 and 7, with column 1 tried first. That differs from column 7 on the first completed solution: lower candidates are explored and rejected first. These are selected-prefix snapshots, not a claim that they are consecutive calls in the full execution log.

Another observed entry has prefix [0,2,4,1,3]. At row=5, the union of the three low-bit masks is 11111111, so available=0. The loop never starts and the function returns to its parent; it must not recurse with pick=0.

Download the verification package and run python3 audit_queens.py to generate the snapshots in results/audit.json. At every Python recursive entry, the verifier independently projects attacks from the placed queens’ coordinates and compares them with the incoming masks. That checks the meaning of state, not just the final count.

import json
from pathlib import Path

record = json.loads(Path("results/audit.json").read_text())
snapshot = record["n8"]["bits"]["snapshots"]["[0, 4]"]
assert snapshot["main_diag_low_n"] == "00100100"
assert snapshot["available"] == "11000010"
assert snapshot["lowest_candidate"] == "00000010"
print(snapshot)

The package’s Python and C sources are extracted directly from this article and the introductory article; Chinese and English code blocks are checked byte for byte. The C bitwise test copy additionally prints boards at terminal nodes so that every solution can be checked without changing choices or state. Each implementation is called twice, with the complete-set checks described in the introductory article. The reference record contains source and verifier hashes, compiler details and sanitizer results. An animation is not used as a substitute for solver validation.

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

13. Summary

The array version explains backtracking; the bitwise version shows how to reduce candidate-checking overhead. Compare solution sets, state semantics and performance under equal conditions. Shorter code is not automatically more correct or faster in every environment.