Category: puzzle

In this blog we are going to discuss the problem of finding the maximum contiguous sum of elements in an array. Now, that was a mouthful ! Don’t worry, we will break this problem up step by step so that you will get a thorough understanding of the problem and the solution. This problem is also referred to as the Maximum subarray problem.

Our first approach to the solution will be the usage of brute force technique and then we will move on to solve the problem using Kadane’s algorithm. As we write the code in Java, we will keep improving the code so that we get a complete understanding of each line of code required to solve this problem.

What is the maximum contiguous sum in a subarray ?

We have an array of integers as input. The array can contain both positive and negative values. Let’s break the 4 important words in ‘Maximum contiguous sum in subarray‘ :

1. Subarray means part of an array.
2. Sum is the addition of the elements of an array.
3. Contiguous means a sequence, no breaks. Hence, contiguous sum means the addition should be between a sequence of values one after the other without a break.
4. Maximum contiguous sum is finding the maximum value after adding such a sequence of values.

Let’s look at a few examples to understand this better-

Examples of contiguous and non contiguous subarray

Barring the last one, all the other examples show contiguous elements in an array. It can be only a single element anywhere in the array. It can be 2,3…n elements as long as there is no break in between. Since these are all part of the array, we refer to them as subarray. In the last example, the green blocks form a subarray but they are not contiguous and hence cannot be part of the solution. Having understood the concept of a contiguous subarray, we need to find the maximum sum contiguous subarray.

Examples of maximum sum contiguous subarray

We have understood the concept of a contiguous subarray, now let’s understand the concept of maximum sum in a contiguous subarray. First, take a look at examples 1,2,3 and 4, they are quite straight forward. Starting from the leftmost element, add the elements one by one without breaking the sequence and try to get a maximum value as shown on the right.

Let’s take a look at example number 5. At first glance, it might seem that the answer is 12. But it’s not ! Let’s start from the left, initially, the sum is 0. Adding 10,the first element in the array, gives us 10. Add the 2nd element, -5 to it, gives us 5. Now we add 12 to it, this gives us a total of 17 which is bigger than 12.

Example 6 is also straight forward. Here, it might seem that 10 + 20 = 30 which is bigger than 20, but note that 10 and 20 are not contiguous. Let’s move to the last example, number 7.

Let us approach example number 7 step wise –

1. We start in a similar way.Initially, the sum is 0, adding 30, the first element in the array to the sum, gives us 30. The maximum value so far is 30.
2. Add -40 to it and we get -10. We don’t change the maximum value as it is greater than -10.
3. Add 20 to it, we get a 10 and we again don’t change the maximum value.
4. If we were to add 40 to it, we get a 50. At this point, we have a new maximum value of 50. But wait a minute…
5. If you consider only the 2 last elements which form a subarray and add their values, we get 60, which is bigger than 50. So, 60 is the right answer.
6. Let’s revisit step 2 and 3. The result upto step 2 is -10. Adding the next element, 20, gives us 10. But when we add that current element,20,the outcome of the addition results in lower value than the current element,20. Let’s rephrase it, the current element has higher value as compared to adding it to previous sum. This means, we can reset the continuity or discard the previous sum. Remember this, it is an important condition to solve this problem.

I hope that makes sense. If the current element by itself has a bigger value than adding it to the previous sum, it means we can discard the previous sum since we are on a quest to find contiguous maximum sum. If we did not do this, the previous sums will act as a deterrent to our overall sum. With this, we also restart the continuity from this point onwards.

Using brute force to solve the problem

Let’s consider the following example

We need to find the maximum sum contiguous subarray. A subarray as we know can be just a single element or a sequence of ‘n’ elements. Let’s take a simple approach to solve this problem.

1. We put a marker at 30, initialize the sum to 0 and –
   • Add 30 to the sum , resulting in 30.
   • Add -40 to current sum, resulting in a sum of -10.
   • Add 20 to current sum, resulting in a sum of 10.
   • Add 40 to resulting sum, resulting in a sum of 50.
   • At every step above, compare the sums to maintain a maximum value among them. At the end, what we have done is explored every possible contiguous subarray from the first element, 30 and found maximum value among them.
2. Add a marker at -40, re-initialize the sum to 0, maintain the current maximum value from step 1 and –
   • Add -40 to the current sum, resulting in -40.
   • Add 20 to the current sum, resulting in -20.
   • Add 40 to the current sum, resulting in 20.
   • At each step, compare the sum with the current maximum value to find maximum among them. All possible contiguous subarrays starting from the second element, 40 have been explored.
3. Add a marker at 20, initialize the sum to 0 and –
   • Add 20 to current sum, resulting in 20.
   • Add 40 to current sum, resulting in 60.
   • At each step, compare each sum with maximum and find maximum among them. All the contiguous subarrays starting from 20 have been explored.
4. Add a marker at 40, initialize the sum to 0 and:
   • Add 40 to current sum, resulting in 40,
   • In this step, compare the sum,40, with maximum obtained in steps above and set appropriate value.
   • This is the end of the array,we should have found maximum value by now.

Why are we putting markers ? We are putting these markers to have a kind of starting point for the subarray. A subarray can start at every element in the array. For an array of size 4, we put 4 markers. So, I hope you can imagine a ‘for’ loop from 0 – n representing each marker.

What do we do for each marker ? From the element being pinned (Sorry, too much usage of Zoom) as a marker, we first initialize sum to 0. Then we start adding the numbers after that pinned element upto the last element. So, another for loop inside the already existing loop, we get a nested for loop. Inside the nested for loop, we find the sum. So, sum = sum + element. Remember, we need to find the maximum at each step now. This can be done using another variable which will be compared against sum.

As you can see above, the marker starts at the leftmost element and keeps moving ahead one by one. For each position of the marker, we iterate from the marker upto the end of the array and keep finding the sum. At every iteration ,we evaluate if we have found a new maximum value.

Code using brute force approach

public class MaxSumSubArray {

    public static void main(String[] args) {
        
        int[] arr = {30, -40, 20, 40};

        int sum = findMaxSum(arr);
        System.out.println("The maximum contiguous sum in the sub array is : " + sum);
    }

    private static int findMaxSum(int[] arr) {

        int currentSum;
        int maxSum = 0;

        for (int marker = 0; marker < arr.length; marker++) {
            //reinitialize sum when marker moves ahead.
            currentSum = 0;

            for (int j = marker; j < arr.length; j++) {
                currentSum = currentSum + arr[j];
                if (currentSum > maxSum) {
                    maxSum = currentSum;
                }
            }
        }
        return maxSum;
    }
}

Notice that on line 20, j is initialized to marker which moves ahead by one each time. We don’t want to find subarrays every time from the first element.

Does the code work for all inputs ?

The input that we passed has a mix of positive and negative numbers. What if we pass the input as a set of all negative numbers ? If we were to pass the input as {-30, -40 , -20 , -40} , we get the output as 0. We need to fix our code to handle this scenario. Take a look at the following code snippet –

private static int findMaxSum(int[] arr) {

    ...
    int maxSum = 0;

    for (int marker = 0; marker < arr.length; marker++) {
        ...
        for (int j = marker; j < arr.length; j++) {
            currentSum = currentSum + arr[j];
            if (currentSum > maxSum) {
                maxSum = currentSum;
            }
        }
    }
    return maxSum;
}

As you can see, the maximum sum is initialized to 0. Since all the values in the array are negative values, the current sum is always a negative value, it is never greater than the maximum sum, which is 0. Hence the ‘if’ condition is never satisfied and the maximum sum is returned as 0.

The fix for this is changing a single line of code –

int maxSum = Integer.MIN_VALUE;

With this change, an input consisting of only negative values should work as expected.

Time complexity of the brute force approach

In the code above, there are 2 nested ‘for’ loops. For every position of the marker, we are iterating through the rest of the array. The time complexity of this code is hence O(N²). If you are completely new to the Big O notation, I would recommend this excellent article by Rob Bell.

The solution works and it is a decent way to get started. Once we have a working solution, we should start thinking along the lines of improving the code and the performance of the code. But remember, don’t get obsessed about improving the performance of every piece of code you write !

We can definitely do better in solving this problem by improving the time complexity to O(n). Let’s explore Kadane’s algorithm.

How to pronounce Kadane ?

Before we get started, I would like to sidestep a little bit with respect to the pronunciation of Kadane. We have a cricketer who goes by the name Ajinkya Rahane. His surname, Rahane , is pronounced as Ra-ha-‘nee’ with an emphasis on the ‘ne’. Kadane is not pronounced like that. It’s more like pronouncing the ‘cane’ in sugarcane or the way you pronounce ‘Dane’ when you refer to someone from Denmark. Peter Schmeichel is the most capped Danish footballer of all time, and the first Dane to reach 125 caps. There is no drag on the ‘ne’ in Dane. Similarly, don’t drag on the ‘ne’ in Kadane. By the way, his full name is Joseph Born Kadane, you can read more about him here. Hey Arsenal fans, speaking of Danes, you can’t forget the great Nicklas Bendtner, can you ? Let’s get back to Kadane’s algorithm now.

Kadane’s algorithm

You can get a good overview of the algorithm here. What is important to note is that, at any given index, the algorithm computes the subarray with the largest sum upto that index. Let’s get into an example.

This is the same example which we considered when we used the brute force approach. When we went through the process step by step using brute force, do you remember a condition which was going to play a crucial role in solving this problem ?

If the current element by itself has a bigger value than adding it to the previous sum, it means we can discard the previous sum since we are in a quest to find maximum contiguous sum. If we did not do this, the previous sums will act as a deterrent to our overall sum.

The sum obtained up to the 2nd element is -10. Now, the next element is 20. If we add the previous sum of – 10 to 20, we get 10. However the current element, 20, is bigger than the sum. Why should we carry a baggage of lesser value as compared to the current element which is much bigger ? So, we reset the continuity and now the sum and the maximum value should be 20 from where we move on to the next element.

So in short, we need to take the maximum between the current element and the sum obtained by adding the previous sum to current element. If the current element is bigger, we reset the sum and the subarray. What if it is not ? What if the sum is bigger ? To get our answer , let’s consider the element 40, which is the next element in the array.

What does it mean if the current element is smaller than the sum obtained by adding current element to previous sum ? It means, the sum, the bigger value, can help us further as it has enhanced our overall value as compared to current element. It also means that the previous sum does not act as a deterrent and we continue with our sequence of elements.

So, in short, for every element in the array, we need to –

1. Find the maximum value between the current element and the addition of the current element to the previous sum.
2. If the current value is bigger, we need to reset. It will also give us a new value to the sum so that we can to continue our exploration further in the array.
3. If the maximum between the two is the value of the addition of the current element and the previous sum, this value becomes the new sum.
4. Once steps 1, 2 and 3 are done, remember, we need to maintain the max value like we did in the brute force approach.

Code for Kadane’s algorithm

public class MaxSumSubArray {

    public static void main(String[] args) {

        int[] arr = {30, -40, 20, 40};

        int sum = findMaxSum(arr);
        System.out.println("The maximum sum in the sub array is : " + sum);
    }

    private static int findMaxSum(int[] arr) {
        int sum = 0;
        int max = 0;

        for (int i = 0; i < arr.length; i++) {
            sum = Math.max(sum + arr[i], arr[i]);
            max = Math.max(sum, max);
        }
        return max;
    }
}

In the ‘for’ loop, we have simply translated the theory that we just understood into code. We find the maximum between the current element ( arr[i] ) at hand and the addition of the previous sum and the current element (sum + arr[i]). The one that has maximum value becomes the new sum.

sum = Math.max(sum + arr[i], arr[i]);

Once we have the new sum, we check if it is the new maximum and if it is, we assign it to the variable, max.

            max = Math.max(sum, max);

Did you notice that there is a single ‘for’ loop ? There are no nested loops ! The time complexity of this code using Kadane’s algorithm is O(n) which is better than the brute force approach. We only iterate through the elements of the array once. Does the code work for all inputs ? What if we supplied an array of all negative values ? Unfortunately, it does not.

Like the brute force approach, we have initialized the variable, max, to 0. One option is to assign it to Integer.MIN_VALUE, like we did in the brute force approach. There is another way to do it as well, the first element of the array can be assigned to the variables sum and max. We can then start our iteration from the 2nd element onwards.

private static int findMaxSum(int[] arr) {
        int sum = arr[0];
        int max = arr[0];

        for (int i = 1; i < arr.length; i++) {
            ...
        }
        return max;
}

Conclusion

We have seen 2 approaches to solve the problem of finding the maximum contiguous subarray. The first approach was simple but it had a time complexity of O(N²). On the other hand, Kadane’s algorithm has a time complexity of O(n), linear time, which is better than brute force. But, unless you know the algorithm before hand, it is difficult to come up with this solution at runtime, like, in an interview. But now I hope that after reading this blog, you will remember Kadane’s algorithm which is quite an effective technique to solve this problem.

If you still can’t remember the algorithm, it’s alright! I am sure that you will at least remember that the pronunciation is not ‘Kadanee..’ !

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:

1. Same row
2. Same column
3. 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-

1. 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.
2. 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.
3. 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 –

1. The board array which will maintain the position of the queens placed on the board.
2. 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.
3. 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

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.