In this blog, we are going to solve the ‘N’ queens puzzle in Java. We will begin with an overview of the problem, move on to understand the challenges involved in the solution and finally write the code in Java using recursion. As always, I will be explaining the code in detail with proper reasoning. I have also included images where necessary which will help you to visualize the theory and the solution.
In my previous blog, we had a look at the 4 queens puzzle in detail. Using a lot of pictorial representations, we understood the problem and the solution, chose a single dimension array instead of a 2 dimensional array and finally, we went through each line of code in Java. If you are completely new to the 4/8/’N’ queen puzzle, I would recommend that you read that blog first.
What is the ‘N’ queens problem ?
In the 4 queens puzzle, we were faced with the problem of placing 4 queens on a 4 *4 chess board such that no two queens attack each other. In the ‘N’ queens problem, we will have a N * N chess board and try and place ‘N’ queens such that no 2 queens attack each other. Let’s consider N = 8 to begin with. If 2 queens should not attack each other, it means no two queens share:
- Same row
- Same column
- Diagonal
The constraints for the ‘N’ queens problem remains the same as the 4 queens problem. From a code perspective, we will actually reuse the same function, noKill, to check for conflicts. The 4 queens problem had 2 solutions satisfying these constraints. The 8 queens problem has 92 solutions – we can place 8 queens on the 8 * 8 board in 92 different ways which satisfy the constraints mentioned above.
Logical solution to the puzzle
The steps required to place the 8 queens on the board is similar to the 4 queens puzzle. We take the same approach of placing the queens in a column by column manner. The image above shows how the queens,Q1 to Q8, have been placed in the columns starting from left to right.
As a quick refresher, in order to place the 8 queens without any conflict, we start at the top left corner.The first queen is placed in that square. We move to the 2nd column and find a suitable position in that column which has no conflict with the first queen. Then we move on to the 3rd queen where we will check for conflicts with the previous two queens. This procedure repeats until we are able to place all 8 queens on the board. If we find a conflict at some point, we backtrack to the previous column and move the queen to the next position/row in that column.
Technical parts common to the the 4 queens problem
Handling the results
In the 4 * 4 queens scenario, we initialized a single dimension array of size 4 to hold the results. We will use the same 1 dimensional array but since we have 8 queens to deal with or in fact let’s go ahead and generalize it to ‘N’ queens, we will dynamically initialize a board of size ‘N’.
int [] board = new int[noOfQueens];
The size of the array will be the number of queens we want to place on the board, let’s take that as an input and assign it to the parameter shown above.
The ‘noKill’ function to check conflicts
We wrote the code for this function in the 4 queens problem and this piece of code remains the same for the ‘N’ queens problem as well. We check for same row and diagonal conflicts in the function. Since we place one queen per column, there is no need to do a conflict check for column.
As a quick refresher, the values in the board array will represent the row number of every queen in a particular column, the column serves as an index into the array.
As shown above, the board array will contain [ 0, 4 , 7 , 5 , 2, 6 , 1 , 3 ]. They represent the row number at which a queen is placed. The column number will be the index into the array. So queen number 1 is at { row 0, column 0 } , queen number 8 is at { row 3, column 7 } and so on.
private static boolean noKill(int[] board, int currentColumnOfQueen) {
for (int i = 0; i < currentColumnOfQueen; i++) {
// same row
if (board[i] == board[currentColumnOfQueen])
return false;
// Diagonal
if ((currentColumnOfQueen - i) == Math.abs(board[currentColumnOfQueen] - board[i])) {
return false;
}
}
return true;
}
The code in this function has been explained in detail in my previous blog. Let’s summarize the code in this function-
- The ‘for’ loop checks if the current queen to be placed has any conflicts with all previously placed queens. Hence the loop starts from 0 and moves up to one previous column than the current column under consideration.
- Row conflicts can be checked by comparing the value in the board array at all previous indices (position of previous queens already placed) with the value at current position under contention. If they are the same, it means we have a row conflict.
- A chess board being composed of squares, any diagonal conflict can be detected by the difference in row and column values of 2 squares. If the difference yields the same value, we have a diagonal conflict. As shown below, when we want to place queen 5 , at column number 4, row number 1 , { 1, 4 } , the for loop will check for all diagonal conflicts with existing queens. When that loop runs and i = 1 , Q2 is at { 4 , 1 }. Absolute values of the difference in row and column values yields 3 and hence a diagonal is detected.
Those were the common parts between the 4 queens and ‘N’queens problem. Now, let’s take a look at how to improve the code for 4 queens puzzle and make it cleaner and generic enough to handle ‘N’ queens.
Using recursion to solve ‘N’ queens
We used nested ‘for’ loops while solving the 4 queens problems. In fact we used 4 ‘for’ loops for 4 queens. Since we want to solve 8 queens or in fact ‘N’ queens, the multiple ‘for’ loops is not a viable solution. We need to come up with another solution, recursion will help us here.
When you think of recursion, think of breaking down a big problem into subproblems. You could sometimes apply this philosophy in life too ! We need to place 8 queens, let’s break it down, let’s try and place 1 queen. If we have a function which solves the problem of placing 1 queen with all constraints, we move to the next queen and then we land up doing the same steps again. We can think of placing 1 queen as our subproblem and we have 8 or ‘N’ such subproblems. When we use recursion, the function keeps calling itself.
Well, one cannot keep calling the function recursively, endlessly ! I mean, imagine solving your problems in life endlessly, I mean, we kind of do that but we would definitely like to break that loop, right ?
If you think about the procedure of placing ‘N’ queens, we start from column number 0 at the top left corner, and find positions across the board in each column such that there are no conflicts. When do we stop ? We stop when we place all ‘N’ queens on the board. From a code perspective, we can start from 0 and then as each queen is placed, we can increment that counter. When this counter equals ‘N’, we stop.
When there is a conflict in a particular square, we backtrack to the previous column and move to the next row/position in that column since the current one yielded a conflict. Then the same procedure continues.
Let’s put all of this theory in a function and understand the code-
private static void placeQueen(int[] board, int current, int noOfQueens) {
if (current == noOfQueens) {
displayQueens(board);
return;
}
for (int i = 0; i < noOfQueens; i++) {
board[current] = i;
if (noKill(board, current)) {
placeQueen(board, current + 1, noOfQueens);
}
}
}
The function, placeQueen, takes 3 parameters –
- The board array which will maintain the position of the queens placed on the board.
- A counter , current, which will initially be 0. This will track the number of queens already placed on the board. Everytime one queen is placed without a conflict, the value will be incremented.
- The final parameter is the number of queens that we want to place.
The part of the code which contains the ‘if’ condition simply checks if we have placed all our queens. If we have placed all queens, we return from the function. That is exactly the exit condition for our recursive procedure. I wish it was easy to find an exit condition for all our problems in life !
if (current == noOfQueens) {
displayQueens(board);
return;
}
The ‘for’ loop is a little bit more involved. Let’s take a look at that snippet of code.
private static placeQueen(int[] board, int current, int noOfQueens) {
....
for (int i = 0; i < noOfQueens; i++) {
board[current] = i;
if (noKill(board, current)) {
placeQueen(board, current + 1, noOfQueens);
}
}
}
Let’s understand this code in detail-
- The ‘for’ loop iterates ‘N’ times, the number of queens supplied as input.The first step to solve this puzzle is to place the first queen at the top left corner and then place other queens in other columns. But what is important to remember is that the first queen itself will take 8 different positions.
- The next line in the code, board[current] = i, fixes the position of the queen in left top corner to begin with. Remember when we call this function the first time, current is equal to 0. Then the call to the ‘noKill’ function will return true since it is the first queen and obviously can’t have conflicts. This means the first queen has been successfully placed. With the 1st queen placed successfully, what’s next ? We move to 2nd column and try to fix the second queen’s position. We discussed that we find and fix each queen’s position using recursion. Let’s make a recursive call.
- The recursive call is made by incrementing the counter, current, by 1. We again enter the ‘for’ loop. How many times should this be executed ? What does this do ? It checks if the position of the 2nd queen at {0 , 1 } can be fixed, hence the call to the ‘noKill’ function. In this case, the ‘noKill’ function will return false since there is a row conflict with the first queen. The code comes out of the ‘if’ loop and executes the next iteration in the ‘for’ loop. Now this loop will take care of fixing the position of the 2nd queen again but this time it will try in the 2nd row. How many possible positions are there in this column ? Well, 8 rows, so 8 times. Hence, to answer the previous questions, it could be executed 8 times and what it is doing is, fixing the position of the 2nd queen.
- This goes on until we are able to fix the positions of all 8 queens for just the first position of the first queen. At that point, for queen number 8, if the ‘noKill’ function returns true, we would have placed all 8 queens. The ‘current’ value will be 8 , the ‘if’ condition will return, the function returns.
- Remember, for the first position in top left corner, the second queen can potentially take 8 different positions in the second column and for each position of the second queen, the third can take 8 different positions and so on for all of them.That is why the recursive procedure is an effective way to solve this problem whether there are 4, 8 , or ‘N’ queens. So in effect, there is a complete branch, both depth wise and breadth wise that is being formed.
A very important part of this recursive procedure is that a recursive call is given ONLY when the conflicts are not there, so there is pruning and branches are formed only when there are no conflicts. If the ‘noKill’ function returns false, we don’t give a recursive call again which in turn avoids the creation of another branch in our recursive tree.
Complete Code
public class NQueens {
public static void main(String[] args) {
int n = 8;
nQueens(n);
}
private static void nQueens(int noOfQueens) {
int [] board = new int[noOfQueens];
placeQueen(board, 0, noOfQueens);
}
private static void placeQueen(int[] board, int current, int noOfQueens) {
if (current == noOfQueens) {
displayQueens(board);
return;
}
for (int i = 0; i < noOfQueens; i++) {
board[current] = i;
if (noKill(board, current)) {
placeQueen(board, current + 1, noOfQueens);
}
}
}
private static boolean noKill(int[] board, int currentColumnOfQueen) {
for (int i = 0; i < currentColumnOfQueen; i++) {
// same row
if (board[i] == board[currentColumnOfQueen])
return false;
// Diagonal
if ((currentColumnOfQueen - i) == Math.abs(board[currentColumnOfQueen] - board[i])) {
return false;
}
}
return true;
}
private static void displayQueens(int[] board) {
System.out.print("\n");
for (int value : board)
System.out.printf(value + "%3s" ," ");
System.out.print("\n\n");
int n = board.length;
for (int i = 0; i < n; i++) {
for (int value : board) {
if (value == i)
System.out.print("Q\t");
else
System.out.print("*\t");
}
System.out.print("\n");
}
}
}
The only additional code above is the display function. It is called each time when all 8 queens have been placed successfully. The function has the board array which has the positions of the queens. A sample of the output can be seen below, here, the number of queens was passed as 8. The first line shows the position( row number) of the queen in each column.
Conclusion
Using recursion, the code for the ‘N’ queens problem looks quite clean. Recursion is definitely an important and effective technique to solve certain types of problems. However, recursion must be used with caution, if the technique is not used correctly, one could have performance issues.
The code above is definitely more clean and concise but also more involved. I urge you to trace the code with a smaller value of ‘N’ to get a even better understanding of the code and the recursion involved in solving the problem.
I end this blog by leaving you with a snapshot of the trace when N = 4. Some salient points which will make it easier for you to follow the trace-
- Follow the numbers on the arrows starting from 1 on the left side, they indicate the step numbers.
- The trace starts with the 3 inputs as – the board array initialized to -1, the pointer, current, and finally the total number of queens to be placed on the board.
- Some backtracking can be seen by the arrows represented in red colour.The dotted arrows in blue indicate the pruning.
- In each box, if the board array values are shown in red color, it indicates either a row or diagonal conflict.
- Circle in green signifies that a position for a queen has been found and after that, the value of the counter, current(2nd parameter) is incremented by 1.
References
- Excellent lecture on the MIT OpenCourseWare channel
Memoirs of a Software developer 