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: positions in the next row attacked along a main diagonal
• anti_diag: positions in the next row attacked along an anti-diagonal

The key point here is that diagonal state is no longer recorded by diagonal index, but converted directly into “which columns the next row cannot use”.

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:

• the main-diagonal attack range shifts one square to the left
• the anti-diagonal attack range shifts one square to the right

In bitwise terms that is exactly a shift:

(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():
    solve(0, 0, 0, 0)
    print("First solution:")
    print_board(first_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.

7. C implementation

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

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

#define N 8

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

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

void print_board(const int 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, int cols, int main_diag, int 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;
    }

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

    while (available) {
        int pick = available & -available;
        available -= pick;

        positions[row] = pick;

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

        positions[row] = 0;
    }
}

int main(void) {
    solve(0, 0, 0, 0);
    printf("First solution:n");
    print_board(first_solution);
    printf("Total solutions: %dn", solution_count);
    return 0;
}

The things to watch in this code are:

• 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

At the scale of eight queens, the value of the optimisation lies more in the more advanced, more compact style. But extend the idea to larger N queens and the bitwise version is usually markedly faster than the array version.

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 main diagonal shifts left and the anti-diagonal shifts right to express the attack range on the next row

12. Bitmask trace table

The bitwise version looks short, but it also makes it easier for a beginner to lose track of the state. The partial trace below separates out the core variables. Assume N = 8, the low 8 bits represent board columns, and 1 marks a position that is occupied or currently selected.

Variable	Meaning	Example value	What to check
LIMIT	Valid column range of the board	11111111	Every inverted result must be ANDed with LIMIT again to stop high bits leaking in.
cols	Columns that already hold a queen	00010001	A set bit means that column can take no further queen.
main_diag	Positions in the next row attacked along a main diagonal	00100010	Shift left before recursing to the next row, moving the attack range to the adjacent column.
anti_diag	Positions in the next row attacked along an anti-diagonal	00001000	Shift right before recursing to the next row; the direction must match the column numbering.
available	Every position the current row can try	11000100	Computed in one step by LIMIT & ~(cols | main_diag | anti_diag).
pick	The lowest available position tried this round	00000100	available & -available takes a single candidate, which available -= pick then removes.

13. Summary

If the standard eight queens teaches you what backtracking is, the bitwise eight queens teaches you this: within the same backtracking framework, optimising the state representation makes the code shorter and the search faster.