The N-Queens Puzzle: A Journey Through Logic and Programming

The N-Queens puzzle is a classic problem of logic and programming that has fascinated chess lovers, mathematicians, and programmers for decades. The challenge seems simple at first: given an NxN chessboard, can you place N queens so that none of them attack each other? As many chess players know, the queen is the most powerful piece in the game: it can move horizontally, vertically, and diagonally. So, each queen must have its row, column, and diagonal free from other queens.

For small boards, the problem might seem easy. For N=1, you can simply place the queen on any square. But for N=2 and N=3, there is no way to place the queens without them attacking each other. Only for N≥4 does the puzzle have at least one solution.

4x4: The First Step

Let’s start with a simple case: the 4x4 board. If we tried to place all possible arrangements of 4 queens on the 16 squares, without worrying about their movements, we would get:

$$\binom{16}{4} = 1820$$

This is the total number of ways to pick 4 squares out of 16. But many of these arrangements don’t satisfy the puzzle’s rules. We can think about the problem in a more efficient way by applying levels of simplification:

First level
Since a queen controls the entire row it’s in, we can simplify the problem by placing only one queen per row. This gives:

$$4^4 = 256$$

Why $4^4$? Because for each of the 4 rows, we can choose any of the 4 columns. At this point, though, some configurations might have multiple queens in the same column.

Second level
We add the rule of one queen per column: no column can have more than one queen. Now we count all possible column permutations:

$$4! = 24$$

Third level
We then eliminate any arrangement where queens attack each other diagonally. At this level, we have to check each permutation to see if the diagonals are safe. For 4x4, only 2 solutions meet this rule. For larger N, a specific algorithm is needed to find the valid solutions.

5x5: More Complexity

With a 5x5 board, the initial number of arrangements grows quickly:

$$\binom{25}{5} = 53,130$$

We apply the same levels of simplification:

First level
One queen per row:

$$5^5 = 3,125$$

Again, at this level, queens might share the same column.

Second level
We filter the arrangements by considering only the column permutations:

$$5! = 120$$

Third level
We remove arrangements where queens can attack diagonally. For 5x5, there are 10 valid solutions.

8x8: The Classic Board

With the classic 8x8 board, the complexity explodes:

$$\binom{64}{8} \approx 4.4 \text{ billion}$$

We apply the same three levels:

First level
One queen per row:

$$8^8 = 16,777,216$$

Again, queens might share the same column.

Second level
We filter by using the column permutations:

$$8! = 40,320$$

Third level
We remove arrangements where queens can attack diagonally. The final number of valid solutions is 92.

It’s interesting that many of these solutions are symmetric, meaning they can be obtained by rotating or reflecting the board. Usually, all distinct arrangements are counted, even if they are symmetric. If we wanted to count only the fundamental arrangements (those that can’t be rotated or reflected to get another solution), for N=8, there would be 12.

From Brute Force to Backtracking

As we’ve seen, the number of possible configurations grows rapidly as N increases. But how can we actually approach the problem from an algorithmic perspective?

Brute force: the exhaustive search approach

A first method is to generate all possible arrangements of N queens on the chessboard and then filter out the valid ones, where no queen attacks another. This approach is easy to understand, but it quickly becomes too slow for even moderate values of N.

for each possible arrangement of N queens on an NxN board:
    if no queen attacks another:
        save the solution

Backtracking: the smart approach

Backtracking builds the solution one queen at a time, row by row, immediately discarding configurations that would lead to a conflict. In this way, we “prune” many useless configurations and save computational time.

function solve(row, occupied_columns, diagonals1, diagonals2):
    if row == N:
        save the solution
    else:
        for each column from 0 to N-1:
            if column not in occupied_columns
               and (row + column) not in diagonals1
               and (row - column) not in diagonals2:
                add column to occupied_columns
                add (row + column) to diagonals1
                add (row - column) to diagonals2
                solve(row + 1, occupied_columns, diagonals1, diagonals2)
                remove column, (row + column), (row - column)

In this pseudocode, occupied_columns keeps track of the columns already occupied by a queen, while diagonals1 and diagonals2 represent the main and secondary diagonals already occupied. This way, every time we try to place a new queen, we immediately check if the position is safe.

The fundamental difference between the two approaches lies in when the validity of a configuration is checked.

• Brute force generates all possible complete arrangements of N queens and only checks if the solution is valid at the very end. This means it spends a lot of time building and examining configurations that could have been discarded much earlier.
• Backtracking, instead, checks the validity of the partial arrangement at every step, as soon as a new queen is placed. If a conflict is found, the algorithm immediately abandons that path and backtracks, avoiding unnecessary work.

This early validation and pruning of invalid paths is what makes backtracking dramatically more efficient than brute force, especially as the size of the board increases.

Conclusion

The N-Queens puzzle is not just a fun logic game or a programming exercise: it’s a fascinating journey that connects chess, algorithms, and strategy.

Thinking in levels of simplification helps us tackle complex problems step by step, while implementing backtracking shows us how efficiency can come from even the simplest challenges.

Have fun! 🚀♟️

Alberto