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, different than the one we tried. Hence, this will require multiple backtracks. 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.
Current queens
Pseudocode:
- 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.
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:
Pseudocode:
- 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.
I used your app to check whether queens are attacking one another. I feel obligated to share the most interesting of my thoughts on the subject.
Part 1 of 4:
Obviously, in a solution, two queens cannot be in the same row. Less obviously, it follows that for 8 queens and 8 rows, there must be exactly one queen in each row.
In the example provided in chapter 3 of the “Computer Science Distilled” book, after 4 queens are placed in the first 4 rows, there are several unattacked squares, but none of them are in the 6th row. But there needs to be a queen in the 6th row. Therefore, we can skip all the searching shown in the example, and backtrack directly to choosing a different square for the queen in the 4th row. Searching by rows results in a more efficient search algorithm.
Part 2 of 4:
Following the example of chapter 3 of the “Computer Science Distilled” book, I propose two algorithms for searching by rows. Both use iteration, neither uses recursion.
Algorithm 1:
for each square in row 1
place/relocate the row 1 queen there
for each unattacked square in row 2
place/relocate the row 2 queen there
for each unattacked square in row 3
place/relocate the row 3 queen there
for each unattacked square in row 4
place/relocate the row 4 queen there
for each unattacked square in row 5
place/relocate the row 5 queen there
for each unattacked square in row 6
place/relocate the row 6 queen there
for each unattacked square in row 7
place/relocate the row 7 queen there
for reach unattacked square in row 8
place/relocate the row 8 queen there
print out the positions of all 8 queens
don’t stop now because we have been tipped off
that there are several solutions.
end all 8 loops
End of Algorithm 1
It seems inelegant to have 8 nested iteration loops. I propose the alternative:
Algorithm 2:
Initialize row[level], level=1,…,8 by [1,2,3,4,5,6,7,8]
Initialize level=1 and col[1]=0
while (level > 0)
Increment col[level] by 1 at least once and as often as necessary
until either col[level]==9 or (row[level],col[level]) is unattacked.
if (col[level] == 9) [case 1]
level = level – 1 [i.e. backtrack]
else [case 2]
if (level == 8) [case 2a]
Print out the positions of all 8 queens.
Don’t stop now because we have been tipped off
that there are several solutions.
else [case 2b]
level = level + 1
col[level] = 0
end if
end if
end while
End of Algorithm 2:
I intend to post parts 3 and 4 in a different post.
I see that in my previous post, my indents were ignored by the software. I learn.
Part 3:
Chapter 3 in the “Computer Science Distilled” challenged us to find manually a solution for the 8 queens problem. Many years ago, I did so, and found more than one solution manually.
In chess, the 4 central squares are considered the most important. I had/have this hunch that the 4 central squares are a good place to start when searching for a solution to the 8 queens problem. There are 2 possibilities: (1) There is one queen somewhere in the 4 central squares, (2) there is no queen anywhere in the 4 central squares.
I tried to investigate possibility 1. Place a queen on (4,4), then search row 5, row 6, row 7, row 8, row 3, row 2, and row 1 in that order. Basically, I was using algorithm 2 in my previous post, except that the initializations were as follows:
Initialize row(level), level=1,…, 8 as [4,5,6,7,8,1,2,3]
Initialize col[1] = 4
Initialize level = 2 and col[2] = 0
while (I don’t run out of patience)
In less than one hour, I found the following solutions:
+ + X + + + + + + + + + + X + + + + + + + X + + + + + + X + + +
+ + + + X + + + + + + + + + + X + + X + + + + + X + + + + + + +
+ + + + + + + X + X + + + + + + + + + + + + X + + + + + + + + X
+ + + X + + + + + + + X + + + + + + + X + + + + + + + X + + + +
X + + + + + + + X + + + + + + + X + + + + + + + + X + + + + + +
+ + + + + + X + + + + + + + X + + + + + + + + X + + + + + + X +
+ X + + + + + + + + + + X + + + + X + + + + + + + + X + + + + +
+ + + + + X + + + + X + + + + + + + + + X + + + + + + + + X + +
and 2 more solutions. I searched (row 5, column 1) and (row 5, column 2),
but not the other possibilities for the queen in row 5.
Part 4 (This is really wandering off topic which is really computer algorithms):
While looking for a more efficient manual search algorithm,
I found the following solution in which there are no queens at all
in the central 4×4 block of squares.
+ + X + + + + +
+ + + + X + + +
+ X + + + + + +
+ + + + + + + X
X + + + + + + +
+ + + + + + X +
+ + + X + + + +
+ + + + + X + +
Central symmetry.
In my previous post, the computer software removed the extra spaces that I had inserted. Here are the four solutions:
+ + X + + + + +
+ + + + X + + +
+ + + + + + + X
+ + + X + + + +
X + + + + + + +
+ + + + + + X +
+ X + + + + + +
+ + + + + X + +
+ + + + + X + +
+ + + + + + + X
+ X + + + + + +
+ + + X + + + +
X + + + + + + +
+ + + + + + X +
+ + + + X + + +
+ + X + + + + +
+ + + + + X + +
+ + X + + + + +
+ + + + + + X +
+ + + X + + + +
X + + + + + + +
+ + + + + + + X
+ X + + + + + +
+ + + + X + + +
+ + + + X + + +
X + + + + + + +
+ + + + + + + X
+ + + X + + + +
+ X + + + + + +
+ + + + + + X +
+ + X + + + + +
+ + + + + X + +
Hi Peter! Thanks for your great comments! Yes, that’s precisely the train of though I indended to spark :) and the optimization to backtrack faster was a very well thought move. Keep up you learning journey!