N-Queens: What Clicked After I Stopped Brute-Forcing It

N-Queens is a classic backtracking problem. The goal is simple: place N queens on an N×N chessboard such that no two queens attack each other. In this post, we'll be counting the number of valid arrangements rather than printing the boards themselves.

When first trying to solve this problem, my intuition, like many others at first, was that iterating over ALL cells to decide the initial position was a good idea. Even worse, I went over ALL positions that each queen invalidates and added them to a list...

After suffering with that naive O(n · n!) approach, I discovered that the optimal solution uses "three sets": columns (cols), left diagonal (diag1), and the right diagonal (diag2).

And I was mind-blown at how such a simple approach was hidden in plain sight, since a queen can only move in 4 directions: horizontally, vertically, and diagonally (left or right).

Why exactly is this approach better runtime-wise? Because, instead of having to find ALL the positions that EVERY queen on the board invalidates, we store only:

1. Column index
2. Diagonal index (row - col)
3. Anti-diagonal index (row + col) (I'll explain where the equations come from later)

Some might wonder why we're using sets instead of lists. List membership checks are O(n) since we'd have to iterate over every element to find a match. However, sets hash each element, so lookup is O(1) on average. Hash collisions can degrade this to O(n) in the worst case, but for integer keys like ours this is practically never an issue.

The Diagonals

The two equations row - col and row + col looked like math magic to me at first, frankly. However, it's frighteningly simple to understand!

Let's return to basic algebra! Now I'm sure most of you know what the slope-intercept form of a line is, no?
Well, it's y = mx + b. In case you don't remember, m is the slope of the line (how steep it is), x and y are the coordinates of a point on the line, while b is the y-intercept (where the line crosses the y-axis).

Now, here's the thing: each diagonal and anti-diagonal has the SAME slope, which are m = 1 and m = -1.

So each diagonal/anti-diagonal is basically the same line visually, just with a different starting point.

Using this information, we can see that b is what makes each diagonal/anti-diagonal unique, so we find it by rearranging the equations into:

b1 = y - x   and   b2 = y + x

Looks familiar? That's where row - col and row + col came from!

Here's a visual of exactly that happening on a real board:

The Code!

cols = set()
diag1 = set()  
diag2 = set()   
count = 0

def backtrack(row: int, n: int) -> None:
    global count
    if row == n:
        count += 1
        return
    for col in range(n):
        if col in cols or (row - col) in diag1 or (row + col) in diag2:
            continue
        cols.add(col)
        diag1.add(row - col)
        diag2.add(row + col)
        backtrack(row + 1, n)
        cols.remove(col)
        diag1.remove(row - col)
        diag2.remove(row + col)

(Yes, it's that short)

We place queens row by row. Before placing a queen at (row, col), we check whether that column, diagonal, or anti-diagonal is already occupied. If any of the three sets contain the corresponding index, we skip that column and try the next one.

The three add and remove calls are the backtracking step. We mark the current position as occupied before recursing, then unmark it when we return, so the next iteration starts in a clean state.
We reach row == n when a queen has been placed in every row from 0 to n-1, which is our base case.

Remember to write global count, or else you won't be able to increment count!

Wrapping Up

The three sets approach is one of those insights that feels obvious in hindsight. The diagonal equations come from middle-school algebra that most of us already know.

If you're a beginner in CP (psst, I am too), then N-Queens is one of the best backtracking problems to start with. It's kind of hard, sure, but it helps you get comfortable with backtracking (add-traverse-remove), arguably one of the most fundamental concepts in CP.