Solving the 8 queens puzzle recursively with Python
If you are like me, you are here because someone gave you a chessboard and told you to place 8 queens on said 8×8 chessboard so that no two queens threaten each other; thus, a solution requires that no two queens share the same row, column, or diagonal. You were intrigued by the question and thought, how hard could it be? Then you spent some time trying to solve it to no avail. Finally, you started wondering if it would be faster for you to code the puzzle rather than solving it. I am here to tell you that for me, it was definitely the case, and here is how you can do it. Before I move on to the coding solution, here is one of the solutions to the problem (there are 12)
Recursively solving the puzzle
The method that I am going to describe uses backtracking which a fancy way to say recursion. Yes, you can brute force your way using the 8⁸ or nearly 17 million possible combinations, but where is the fun in that?
Let’s dig into backtracking. You have an empty chessboard. After you place the first queen anywhere you want on the first column, you move on to the second column and search for a square to place the second queen. If you succeed, you move on to the third column and so on. After n steps, you will realize that since you started randomly, you probably ran out of spaces to place a queen onto the nth column. If that is the case, you go back one step and search for an alternative square for the (n-1)th queen. If there are no alternative steps, you remove that queen as well and go back to the (n-2)th column to search for an alternative square. If you find one, you move forwards again to (n-1) and keep going. You will realize that I am describing a search strategy that sort of looks like a tree. You go down one branch until you consume all possible combinations before you come back up to explore another branch. This is also known as a depth-first search.
Python code
The python code will require two functions. One, to check if the placement of a queen is valid on a given board. Two, to recursively try to place queens onto the board. Let’s first create an 8×8 (or any size) grid.
Our initial chess board is an empty list of lists of 0. We will place 1’s in place for the queens. Next, let’s check out the valid placement code
You can see that the code checks the column, row, and diagonals and returns True if a placement is valid. Finally, we can code our main function for solving the problem.
Let’s break down a few moving pieces. The code goes through every column and every row and if a square is empty and a queen placement is valid, it places a queen at the said square and calls itself again.
The only way we can end up on line 12 is if the algorithm consumed all possible combinations of a given branch. If that is the case, we need to check if we are done! If there are 8 queens placed on the board, we can simply return or grid and move up the branches. Otherwise, we remove the queen we placed and keep going. We can easily call this code with one line.
And we are done! If you follow this procedure, you will get the following solution which is one of the solutions. You can get the other solutions by changing your initial grid i.e. placing a one in a place you want a queen.
[[1 0 0 0 0 0 0 0]
[0 0 0 0 1 0 0 0]
[0 0 0 0 0 0 0 1]
[0 0 0 0 0 1 0 0]
[0 0 1 0 0 0 0 0]
[0 0 0 0 0 0 1 0]
[0 1 0 0 0 0 0 0]
[0 0 0 1 0 0 0 0]]Plotting the solution on a chessboard
Let’s add some finishing touches by plotting the solution on an sns heatmap. Add the following function
Then simply call it
