How to solve the 4 queens puzzle in Java ?

In this blog we are going to take a look at the 4 queens puzzle and –

1. Pictorially understand the problem and the solution in detail.
2. Do a step by step analysis of the data structure required to arrive at the solution.
3. Write the code in Java. I will be explaining each line of code so that you get an understanding of not just the ‘how’ but also the ‘why’ behind a particular line of code.

Why 4 queens and not 8 queens ?

In another blog, we will be solving not just the 8 queens problem but we will be taking a look at the solution to the ‘N’ queens problem. I think it is important to get a good understanding of the smaller and common bits by first considering the 4 queens problem since it is a subset of the 8 queens or ‘N’ queens problem.

We will be choosing an optimized data structure and also handling the different scenarios in the code for the 4 queens problem which will give you a strong foundation. With this strong foundation, you will find it much easier to solve the 8 or ‘N’ queens problem. Let’s go ahead and get a good understanding of the problem.

What is the 4 queens problem ?

It is the problem of placing 4 queens on a 4 * 4 chessboard so that no two queens threaten each other. This really means that no two queens share the same row, same column or same diagonal. Remember these constraints as it is the most important part of the solution and the code.

Solution to the 4 queens problem

With the constraints mentioned above, there are only 2 solutions to the 4 queens problem. As you can see from the 2 solutions, no two queens share the same row, same column or diagonal. I wanted you to visualise the solution to the puzzle first so that you get a better idea about the approach that we are going to take.

How to get to the solution?

The way to arrive at these solutions is to start at the top left corner of the board and start placing the queens one by one on the board. If we come to a point where we realize that there is a conflict between the queen just placed on the board and one of the existing queens, we simply rule out that step to get to the solution and try placing that queen on another position – this also means we are going back a step. This is also called as backtracking.

When you are in the process of finding a job, ideally, one would: Prepare -> Apply -> Interview. If you fail the interview and find yourself royally underprepared, you would go back and read the things you missed out on before you start applying again- backtracking, something that you don’t always like to do but need to do in order to progress further.

We start placing the queens one by one on the board, the starting position can be column 1 as shown below. Every column will have only 1 queen.The approach we will be taking is placing a queen on each column one by one. One can approach it row by row as well. Once a queen has been placed on a particular position in a column, with all conditions satisfied, we move to the next column.

As shown above, when we start exploring for a position on the 2nd column, we cannot place the queen on the first 2 positions(shown with an ‘X’) . This is because of a row and diagonal conflict with the first queen. However, the 3rd position seems correct. Let’s move on to the 3rd column now.

So far we have placed 2 queens. As shown above, on the left hand side, when we try to place the 3rd queen in column 3, we are not able to find a suitable position for it because of the position of previous queens. There is a conflict with the first queen because of sharing the same row and a conflict with the 2nd queen because of diagonal and row conflicts. This means we need to go back, backtrack, to the 2nd column and place the queen on next position in the 2nd column – shown on right side in the image above. We continue in this way until we are able to place all the 4 queens without conflicts.

We started by placing the first queen at top left corner. Then we performed the steps mentioned above to place the other queens. This first position of the first queen might give us a solution. We then move on to explore other solutions by placing the first queen again at different positions on the first column. The rest of the grid has been shown in dotted lines to indicate that in each step below, positions of the other 3 queens are yet to be determined. Remember that one column can have only 1 queen.

Technical deductions

With this understanding, we need to:

1. Handle a 4 * 4 chess board along with 4 queens.
2. Choose an appropriate data structure to track the solution/position of the queens.
3. Handle conflicts when placing the queens on the board.

Let’s take a look at each one of these steps in detail.

Representing a 4 *4 chess board

A chess board can be represented using a row and column layout as shown above. We have 4 rows and 4 columns starting from row 0, column 0 in the left topmost corner and {3 , 3} at the bottom right representing row and column number 3. Any cell can be represented as { row , column } combination. One approach could be to use a 2 dimensional array to represent the board and the positions occupied by the queen but we are actually not going to use it. We are going to have much more optimized solution in terms of space.

Let’s take a look at the solutions again, mapping them with row and column numbers:

1. For solution 1, queens positions- [ {1,0} , {3,1} , {0,2} , {2,3} ]
2. For solution 2, queens positions – [ {2,0}, {0,1} , {3,2} , {1,3} ]

Data structure to hold the solutions

2 terms that have occurred repeatedly in the logical approach are the words ‘column’ and suitable ‘position in a column’. We need a data structure to represent this.

Let’s look at solution number 1 – [ {1,0} , {3,1} , {0,2} , {2,3} ] . We know that each column can have only 1 queen, take a look at the column numbers in each of the {row , column} pairs in solution number 1 – { 0, 1 , 2, 3 } . Now let’s single out the row numbers – { 1, 3, 0, 2 }.

As shown above, we place 1 queen in 1 column. The position { 1, 0 } tells us that the first queen is placed at row 1 and column 0. In the 1st column, the queen is on 3rd row and so on for other 2 columns. If we were to separate out the column number as an index to a single dimension array, the value at each index/column will be the row number as shown on the right side of the above figure. From this array, we can actually determine the position of the 4 queens. Index 0 tells us the position of first queen, Index 1 the second queen and so on. Hence a single dimension array is sufficient to represent the position of the queens as compared to a 2-d array.

		int [] board = { -1, -1, -1, -1 };

We declare a single dimension array called board and initialize all the values to -1 before we start placing the queens one by one. The size is 4 since we need to place 4 queens.

How to check for conflicts when placing queens ?

Well, no two queens can be placed on –

1. Same row
2. Same column
3. Along the diagonal

The same column will not hold true in our case since we are taking a column placement approach and we have only 1 queen placed on 1 column.

When we attempt to place a queen at a particular position or row in a given column, we need to check that the current queen being placed does not share the same row with an existing queen. How do we check that using the single dimension array ?

As you can see, using the board array, we can easily determine if 2 queens share the same row. An important point to remember is that when we try to place a queen at a particular position in the current column, we need to check for row conflict with all previously placed queens. Due to this, we need a pointer to current column and a ‘for’ loop which runs from 0 to current column. In this loop we will check if the row values are the same since 2 queens which share the same row will land up having the same value in the board array.

Let’s define a function, noKill, which takes 2 parameters – one is the board array and the 2nd parameter is the current column of the queen being placed.

private static boolean noKill(int[] board, int currentColumnOfQueen) {

        for (int i = 0; i < currentColumnOfQueen; i++) {
            // same row
            if (board[i] == board[currentColumnOfQueen])
                return false;
        }
        return true;
}

When we call this function, we will pass –

1. The value of the current column under consideration reflected by the 2nd parameter.
2. The board array – Will have values of the row numbers for each column of previously placed queens. Along with this, we will assign the current position of the queen under consideration in the board array which will be accessed using the 2nd parameter.

Checking for diagonal conflicts is a little bit more involved. We can take advantage of the fact that a chess board is made of squares.

Let’s consider 2 scenarios to understand the diagonal condition better.

1. The first queen is at { 0 , 0 } and we want to place a queen in column 1 which is where the current column is pointing at. Let’s consider { 1 , 1} which is the diagonal element for queen at { 0 , 0} . Let’s take the difference between the row number and column number starting with the {row,column} of current column under consideration and a queen already placed. This will result in [ {1-0},{1-0} ]. The value of the difference is the same, 1 and 1.
2. Assuming the first queen is at { 3 , 0 } and we are at column 3 wanting to place the queen at {0 , 3} where current column is pointing. So difference in row number is {0 – 3} and difference in column number is { 3 – 0} . The absolute difference is the same, 3 and 3.

I have shown you just 2 examples but you can consider any of the diagonals on the board and notice that the difference in row and column values land up being the same.

Accessing the column number of the current queen under consideration is simple since we have the a pointer to the current column. Our ‘for’ loop will run from 0 – current column since we need to check the presence of a diagonal with all previously placed queens. We already have a ‘for’ loop for the row check and hence we can utilize that same loop. To get the row value, we access the board array since the board array contains the position of the row at a given column.

(currentColumnOfQueen - i) == Math.abs(board[currentColumnOfQueen] - board[i])

The left hand side gives us the difference in column values. The right hand side gives us the difference in row value. The Math.abs function call is required as shown in the previous example where one diagonal can give us a negative value. Add this to the existing code of the noKill function gives us the following-

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;
	}

That’s the final code for checking conflicts. Using a ‘for’ loop which iterates from 0 to current column, we check if the current queen, which we want to place, has a row or diagonal conflict with any of the earlier positioned queens. If we find a conflict for any queen, the function returns false. If there are no conflicts, the function returns true on the last line.

Calling the noKill function

Dealing with the first Queen

We start with the first queen placed at 0,0 and for this one position, we find appropriate positions for the other queens across the board in columns 1, 2 and 3. There are 3 more positions for which we repeat this same procedure, { 1 , 0 } , { 2 ,0 } and { 3 , 0 }. This is a total of 4 positions, so we need to count 4 times for 4 queens. We need a ‘for’ loop starting from 0, less than n. In each row position for column 0, note the row values – 0, 1, 2 , 3. Remember, the row values correspond to the value in the board array. We are dealing with a row value in column 0 which is the first element in board array, board[0]. This ‘for’ loop is really to determine the row position of the first queen. So this can be translated into code as follows-

for (int i = 0; i < NO_OF_QUEENS; i++) {
    board[0] = i; // this will assign the row number
    ...
}

Dealing with the second Queen

For every position of the first queen, we need to find a position for the second queen. This position will be any one of { 0 , 1 } , { 1 , 1 } , { 2 , 1 } , { 3 , 1 }. We start at {0 , 1 } as shown above. So again, we are looking at a loop which could executes 4 times. Remember, this loop could execute 4 times for each position of queen 1. So we are looking at a nested for loop.

What about the value at index 1 (shown with a ‘ ? ‘ ) in the board array which tracks the position of the 2nd queen ? We do the same thing, start with row 0 and move upto row 3 until we find a correct position. This position will be determined by row and diagonal conflict with queen 1. Let’s go ahead and modify the earlier code to handle this scenario

for (int i = 0; i < NO_OF_QUEENS; i++) {
    board[0] = i; // this will assign the row number
    for (int j = 0; j < NO_OF_QUEENS; j++) {
        board[1] = j;
        if (noKill(board, 1)) {
            //do something
        }
    }
}

1. Line 3 is the nested for loop
2. Line 4 assigns the current iteration value to the board array element 1.This means it will contain a row value,starting from row 0 and moving on to row 3 until an appropriate position is found. The value at board[1] will represent position of the 2nd queen.
3. Lines 5,6,7 call the noKill function and pass the board array along with the parameter, 1 , which indicates the current column at which we want to place the 2nd queen. The current column is column number 1

What should happen if noKill returns false ? If it returns false, we found a conflict, it will increment the value of j by 1 and try and find the next position in column 1 for queen 2.

What if it returns true ? If it returns true, it means we found a position for the 2nd queen and we move on to find a position for the 3rd queen. This is really the same procedure as queen 1 and 2. So let’s look at the code for the same.

Dealing with the 3rd and the 4th Queen

for (int i = 0; i < NO_OF_QUEENS; i++) {
    board[0] = i; // this will assign the row number
    for (int j = 0; j < NO_OF_QUEENS; j++) {
        board[1] = j;
        if (noKill(board, 1)) {
            for (int k = 0; k < NO_OF_QUEENS; k++) {
                board[2] = k;
                if (noKill(board, 2)) {
                    for (int l = 0; l < NO_OF_QUEENS; l++) {
                        board[3] = l;
                        if (noKill(board, 3)) {
                            //display queens
                        }
                    }
                }
            }
        }
    }
}

There are 4 loops, one corresponding to each queen. The final call to the noKill function on line 11 corresponds to column 3, the last column. If we have reached this stage, it means we have found a position for all 4 queens without any conflicts. We can display the positions of the queen by displaying the board array.

Displaying the queens

We have 2 possibilities of placing the queens without conflicts on a 4 *4 board. We start printing row wise. Every column can have just 1 queen and that is true for the row as well, every row can have 1 queen only. The code displays a ‘Q’ when a row value in the board (accessed by board[j]) array matches the current iteration of the row, otherwise it displays a ‘*’.

Complete code

//Solves 4 queen using nested for loops.
public class FourQueen {

    public static int NO_OF_QUEENS = 4;

    public static void main(String[] args) {

        int [] board = {-1, -1, -1, -1};

        for (int i = 0; i < NO_OF_QUEENS; i++) {
            board[0] = i;
            for (int j = 0; j < NO_OF_QUEENS; j++) {
                board[1] = j;
                if (noKill(board, 1)) {
                    for (int k = 0; k < NO_OF_QUEENS; k++) {
                        board[2] = k;
                        if (noKill(board, 2)) {
                            for (int l = 0; l < NO_OF_QUEENS; l++) {
                                board[3] = l;
                                if (noKill(board, 3)) {
                                    displayQueens(board);
                                }
                            }
                        }
                    }
                }
            }

        }
    }

    private static void displayQueens(int[] board) {
        System.out.println("-------------");
        int n = board.length;
        for (int row = 0; row < n; row++) {
            System.out.println("Hello");
            for (int value : board) {
                if (value == row) {
                    System.out.print("Q\t");
                } else {
                    System.out.print("*\t");
                }
            }
            System.out.println();
        }
    }

    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;
    }

}

Conclusion

The code is simple and uses just a single dimension array to store the results. I think it is definitely a good start for understanding the 4 queens problem and the challenges involved in finding conflicts. However the code does not look clean with the 4 nested loops for 4 queens.

This code may be simple but could get ugly if we were to solve 8 queens problem, imagine 8 nested loops and your eyeballs moving from left to right and then from right to left tracking those braces. After this eyeballing, there is a good chance you might want to close your eyes for a few seconds. The good news is that we can get rid of the nested loops using recursion – we seem to be solving the same problem for each column/queen. The single dimension array and the part where we check for conflicts will remain the same and hence this code can be reused to a good extent.

I hope you have understood the challenges and the solution to the 4 queens problem which will definitely give you a strong foundation to tackle the ‘N’ queen puzzle. I think 8 queens or ‘N’ queens using recursion deserves to be a part of another blog.

References

1. A good description on the google developers guide can be found here .
2. A great lecture on the MIT OpenCourseWare channel.