Have you ever played chess? If yes, you already know that the queen is the most important piece and that it can move any number of squares vertically, horizontally or diagonally. If you haven’t, don’t worry: today, we’ll only learn how to place 8 queens on the chessboard such that no queen is able to move to a square occupied by another queen. In chess jargon, we say that the queens won’t be able to attack each other. How do we do this? We use backtracking.
The backtracking algorithm finds a solution to problems in which some constraints must be respected. It tests all possible solutions until it finds the correct one. Let’s try an example, with four queens and a small board. We will start by placing the first queen:
The second step is to place the second queen in a safe position, and then the third one:
At this point, there is no safe square on which we can place the last queen. So, we will change the position of the previous one. This is backtracking!
As you can see, there is no other square to safely place the third queen. This will require multiple backtracks, which means we will have to go back again and change the position of the second queen we placed.
We will have to perform multiple backtracks again to place all queens correctly and finally obtain a solution:
If you want to learn more how multiple backtracking steps inevitably lead you to a solution, check out Computer Science Distilled. It will also show you many other computational strategies that help you solve interesting problems!
Now that you know how backtracking works, we can solve the full-sized 8 queens problem. Below, there is a chessboard you can play with to practice your skills and find a solution. Start by placing the first queen by clicking on the top-left square of the chessboard. You will see that the queen you placed will be listed under the “Current queens” list.
You can now place another queen in a position that will prevent them from attacking each other. Our first queen is in a8, the second, for example, can be placed on c7. Keep on placing queens until there is no safe square on the chessboard left. At that point, it is time to backtrack by clicking “undo”. This will clear the last queen you placed and let you choose another square to place it. You can also remove a queen from the board by clicking directly on it.
By playing the interactive game, you can start to get a feel for backtracking. As humans, it can become difficult for us to keep track of all previous queen placements. This is where programming helps! Below, you can find an animation generated by a program demonstrating its flawless backtracking skills:
- Start by placing the first queen on the top-left square of the chessboard.
- If we’ve placed the 8 queens, we’re done. Otherwise, is it possible to place another queen in a safe position?
- If yes, then mark this [row, column] as part of the solution, and go back to point 2.
- If no, then change the position of the previous queen (backtracking) and go back to point 2.