← All perspectives
Algorithms

8 Queens Puzzle and the Power of Recursion

A personal introduction to recursive backtracking through the classic Eight Queens puzzle, including a concise Python implementation.

By Harikumar G Pillai

Let me start with an old story. I was taking a C language course as part of my studies. If I’m not wrong, that was around 1996–97. “Recursion” was the theme of the day. Following our normal evening discussions, our teacher, Shiva, issued us a challenge: solve the classic Eight Queens puzzle using recursion.

Those were the days when we didn’t have search engines such as Google—or the internet itself—to search for solutions. There were no computers in our homes. We used to reserve the NIIT computer drome for an hour or so to try our programs.

The time we got to use a computer was really limited. So I used to write programs on paper and keep refining them until they were perfect. When we were in front of the computer, we didn’t think about the logic. We simply sat and typed in the code. After reading this, I am sure my younger coworkers will understand why it irritates me when they attempt to run their programs after each line.

Challenge

Coming back to the challenge, I wasn’t sure whether I could put eight queens on a chessboard without them attacking one another. I decided to give it a shot manually. I took paper and a pencil and experimented with numerous alternatives by noting the positions. I tried for at least two or three hours and failed terribly. I was thinking about it all the time—while bathing, eating, smoking, and so on.

Finally, I decided to experiment with recursion. It was much easier than manually arranging eight queens on the board, but I wasn’t sure whether my program would yield any results. I went to the computer drome to put it to the test. After a few iterations, my program began to work and, to my amazement, provided many positions.

I had struggled to find even one arrangement with eight queens that did not attack one another. My program produced 92 distinct positions.

That’s when I understood how effective recursion can be. It is difficult to visualize. However, once you comprehend its power, you begin to appreciate it.

That exercise provided me with a solid foundation in recursion. I have employed recursion in several sophisticated solutions. Its beauty is that we need only a few lines of code to build a complex solution.

Hold on—what exactly am I up to? Giving a spiel about my illustrious past? That isn’t my objective. Let me return to the subject.

At home, my children and I were discussing chess and the topic of Eight Queens came up. That prompted me to give it another shot, this time in Python, as they were already familiar with it. I also wanted to post the solution to see whether anyone had better ideas or ways to improve it further.

Approach

Each row should have one queen, and each column should have one queen. We must also ensure that the queens do not attack diagonally.

The process starts with a queen in the first row and first column. We then proceed to the next row and identify a safe column for the next queen. We repeat the process row by row. If we cannot place a queen in a row, we take a step back and locate the next possible column in the preceding row. We continue until queens have been placed in all eight rows.

Isn’t that simple?

Solution

The first step is to finalize the logic for determining whether a cell is safe.

INDEX = 8
solution = [-1 for _ in range(INDEX)]
solution_list = []  # List of solutions

I use a one-dimensional array to record positions. The index represents the row and its value represents the column. When we discover a solution, we add it to solution_list and move on to find the next possible solution.

# Check whether the current position is safe
def is_safe(row, col):
    """Check whether it is safe to place the queen."""

    # Check previous rows where queens have already been placed
    for k in range(0, row):
        # Check the column
        if solution[k] == col:
            return False

        # Check diagonal positions
        if (row - k) == abs(col - solution[k]):
            return False

    return True

The function iterates through the previous rows in the solution array to determine whether the new cell—supplied as row and col—is safe.

It is now time to go over each row and look for a safe cell.

# Solve one row at a time
def solve(row):
    """Find every valid arrangement."""
    if row == INDEX:
        solution_list.append(solution.copy())
        return

    for col in range(INDEX):
        if is_safe(row, col):
            solution[row] = col
            solve(row + 1)

When using recursion, we must include an exit point. Otherwise, the program enters an infinite call loop. That is the first condition in the function above. If row is 8, it indicates that queens have already been placed in all rows. We add a copy of the solution to the list and return to the caller.

The last line contains the recursive call with the next row number. We make this call after locating a safe column in the current row.

Source Code

The source code is available in the Eight Queens GitHub repository. If you are interested in experimenting with it, please feel free to do so. I added comments, but if anyone needs more explanation, please reach out.

Conclusion

I am not sure whether this is the best approach. There could be better ways to solve the puzzle. If anyone has a better solution, please share it with me. I will also refine the GitHub repository if I find a better approach.

You can learn more from the Eight Queens puzzle entry on Wikipedia or see the results in graphical form, using the same Python program through WebAssembly.