8 queens puzzle and the power of recursion

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 with a challenge: solve the classic "8 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. Forget about internet, there were no computers in our homes. We used to reserve “NIIT computer drome” for an hour or so, to try out our programs. The time we get to use computer was really limited. So, I used to write the programs on a paper and keep refining it until they were perfect. When we are in front of the computer, we don’t think about any logic. Simply sit and type-in the code. After reading this, I am sure that 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 if I could put eight queens on a chess board without them attacking each other. So, I decided to give it a shot manually. I took some paper and a pencil and experimented with numerous alternatives by noting the spots with the pencil. I tried for at least 2-3 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 a lot easier than manually arranging 8 queens on the board. But I wasn't sure if my program would yield any results. I went to the computer drome to put it to the test. My program began to work after a few iterations, and to my amazement, it provided many positions. I was struggling to find at least one situation with eight queens on the board without attacking each other. However, my program provided me with 92 distinct positions. That's when I understood how effective recursion can be. It is difficult to visualize. However, once you comprehend the power, you will begin to appreciate it.

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

Hold on there! 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. But this time in Python, as they both are already familiar with it.

And I was thinking about posting the solution to see if anyone had any better ideas or if there was any way to enhance it further.

Approach

Each row should have one queen, and each column should have one queen. Also, we must ensure that these queens do not attack diagonally.

The process starts with a queen in the first row, first column. Then proceed to the next row and identify a safe column to place the next queen. Repeat the process in the next row and so forth. If we are unable to place a queen in a row, we must take a step back and locate the next possible column in the preceding row, before continuing. Continue in this manner until we manage to place the queens in all eight rows. Isn't that simple?

Solution

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

solution = [[-1] for _ in range(INDEX)]
solution_list = [] ?# list of solutions.        

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

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

? ? # check previous rows where we have already placed queens
? ? for k in range(0, row):
? ? ? ? # check row and column
? ? ? ? if (k == row) or (solution[k] == col):
? ? ? ? ? ? return False
? ? ? ? # check diagonal positions
? ? ? ? if (row - k) == (col - solution[k]) or (row - k) == (solution[k] - col):
? ? ? ? ? ? return False
? ? return True        

The above function iterates through the previous rows (on the solution array) to determine whether or not the new cell (row and col supplied as parameters) is safe.

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

# solve a row at a time
def solve(row):
? ? """Solve one row"""
? ? if row == INDEX: ?# we have a solution, add it to the list
? ? ? ? solution_list.append(solution.copy())
? ? ? ? return

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

When using recursion, we must be sure to include an exit point. Otherwise, it will enter an infinite call loop. That is the first line of the above function.?If the value of 'row' is 8, it indicates that we have already placed queens in all of the rows (remember, the array index begins with 0). Return to the caller after adding the solution to the list.

The recursive call with the next row number (given as a parameter) can be seen in the last line. We do this after locating a safe column in the current row.

Sample output

Source code

The source code is available in a github repository. People who are interested in experimenting with it, please feel free to do. I tried to add comments in the code. But, in case anyone needs more explanation please feel free to reach out to me

Conclusion

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

Please check the Wikipedia to get more information about the "8 queens puzzle"

See the results in graphical format (same python program using WebAssembly): https://eight-queens-nine.vercel.app/webassembly/pyodide/index.html

?