## How to solve the ‘N’ queens puzzle in Java ?

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

## 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.

###### 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.

## How to solve the bridge crossing puzzle in Java ?

In this blog we are going solve an interesting puzzle of bridge crossing in Java. The bridge crossing puzzle is also referred to as the Bridge and Torch problem.We will first understand what the puzzle is all about, come with different logical solutions and finally we will write the code for the same in Java. As always, I will approach the code step by step so that you get a complete understanding of the solution.

##### What is the bridge crossing problem ?

It is night time and 4 people come to a river. There is a bridge and one torch. They need to get to the other side of the river using the bridge. This bridge is narrow and hence only 2 people can cross the bridge at a time. Since it is night time, the torch has to be used.

Each person takes a certain amount of time to cross the bridge. Person A can cross the bridge in 1 minute, B in 2 minutes, C in 5 minutes and D in 8 minutes. When 2 people cross the bridge, they walk at the slower person’s pace. The question is – Can we get them across the bridge in 15 or fewer minutes since the torch only lasts for 15 minutes ?

##### A quick solution that comes to mind

If A and B were to start crossing the bridge with the torch, they would take 2 minutes to get to the other side. Person A takes 1 minute and B takes 2 but A has to walk at B’s speed. Person ‘A’ seems to be the fastest among them. So common logic says, let’s get ‘A’ back. So ‘A’ comes back with the torch, now the total time is 3, 2 from earlier one and 1 for ‘A’ to come back. We had 2 journeys so far, 1 forward and 1 backward.

We would assume that since ‘A’ is the fastest, ‘A’ should be the torchbearer and help everyone cross one by one. So ‘A’ and ‘C’ start crossing the bridge. They walk at C’s speed. Now the total time is 3 + 5 = 8. 3 from the earlier journeys and the 5 from C’s speed. Now, our fastest, the torchbearer needs to come back. So 8 + 1 = 9. So we have had 2 more journeys, 4 in all. 2 forward and 2 backward.

Finally, person ‘D’ remains. Our great torchbearer,’A’, and ‘D’ start walking, taking a time of 8 minutes which is D’s speed. The total time is 9 + 8 = 17 minutes. This was one more journey, so we have a total of 4 + 1 = 5 journeys. This was a forward journey. So for 4 people, we had 3 forward and 2 backward journeys and a total time of 17 when A, the fastest among all does the torch bearing activity.

Well, well, well – this is not the optimum solution although it seems like it is. The torch only works for 15 minutes !

##### The right logical solution

It seems that since A takes the least amount of time to cross the bridge, we must send everyone else with A. In the solution above, C and D are crossing separately. If we made them cross together, we could actually do better. Let’s try that solution.

This is definitely a better solution and in fact the right solution given the condition. All 4 people have crossed the bridge in 15 minutes. The key here is that in step 3, C and D, the slowest among the 4, travelled together rather than individual trips across the bridge.

##### Technical analysis

We have 4 people, let us represent this using ‘n’, we have n = 4.

We will be receiving the time taken by each person to cross the bridge as an input. How can we store this ? The simplest is an array. Note that we will sort this array in ascending order.

If we were to sort the array in descending order and started the journey with ‘C’ or ‘D’ , we would have made ‘C’ to travel back with the torch and then ‘C’ has to go to the other side at some point in time. So ‘C’ would have travelled thrice increasing the overall time which would not be a feasible solution.

```int [] timeToCross =  { 1, 2, 5, 8};
```

So, timeToCross[0] indicates the time taken by A which is 1 minute. In the logical steps shown above, Step 1 shows ‘A’ and ‘B’ starting off their journey, followed by ‘A’ coming back. How can we represent that using the array we just created ?

###### Step 1 and 2
```timeToCross[1] + timeToCross[0]

```

Let’s break it up. timeToCross[1] indicates time taken by ‘B’. The first step is ‘A’ and ‘B’ crossing together. The time taken is the time taken by ‘B’ to cross since ‘B’ is slower than ‘A’ and that is the reason why the array is also sorted. So the first logical step of ‘A’ and ‘B’ crossing is represented as timeToCross[1].

The timeToCross[0] is the time taken by ‘A’. Why do we have this ? Well, step 2 is ‘A’ coming back. So we have combined logical steps of 1 and 2 in one line of code.

###### Step 3

Step 3 is ‘C’ and ‘D’ crossing together. The time taken will be time taken by ‘D’ since ‘D’ is slowest among ‘C’ and ‘D’. How can we represent that using the array?

```timeToCross[n-1]
```

Since, n =4, we refer to it with index, n-1, the index starts from 0. n-1 =3 which is the index of ‘D’.

###### Step 4

We have managed to get ‘C’ and ‘D’ , the slowest among all 4 to cross the bridge. Now, the next step is ‘B’ coming back with the torch. This can be shown as

```timeToCross[1]
```

At the end of this step 4, we have managed to get 2 people among 4 to the other side of the bridge. What is the total time so far ? Let combine the code from steps 1, 2, 3 and 4.

```timeToCross[1] + timeToCross[0] + timeToCross[n-1] + timeToCross[1];
```

Let’s add all this code into a function

```public static int totalTime(int[] timeToCross , int n)
{
int time = timeToCross[1] + timeToCross[0] + timeToCross[n-1] + timeToCross[1];

}
```
###### Extending the problem to have ‘n’ people crossing the bridge

We have 2 people left out of 4. This is 4 -2. We represented this number 4 by ‘n’. If we were to generalize this puzzle for ‘n’ persons, at this point, we would always have ‘n-2’ persons left for crossing. So with ‘A’,’B’,’C’,’D’, we have ‘A’ and ‘B’ left.

What if we have more than 4 persons ? What if we had ‘n’ persons ? We apply the same logic for the remaining n-2 people. It looks like we have solved a part of the problem, a subproblem. When we need to apply the same logic for the remaining data, recursion can be a good idea. The input to this function will be the time that we have calculated so far and the second input will be 2 fewer persons.

```public static int totalTime(int[] timeToCross , int n)
{
int time = timeToCross[1] + timeToCross[0] + timeToCross[n-1] + timeToCross[1];

return time + totalTime(timeToCross, n - 2)
}
```

What if the actual input supplied to this function had only 2 or 3 people instead of 4 ? What if we had just 1 person to cross the bridge ? This can be solved with the following conditions –

```public static int totalTime(int[] timeToCross , int n)
{
if (n < 3)
{
//as the elements are sorted.
return timeToCross[n - 1];
}
//3 people will be addition of all.
else if (n == 3)
{
return timeToCross[0] + timeToCross[1] + timeToCross[2];
}
//n>=4
int time = timeToCross[1] + timeToCross[0] + timeToCross[n-1] + timeToCross[1];

return time + totalTime(timeToCross, n - 2)
}
```
###### When there are 1 or 2 people to cross the bridge, n = 1 or 2

If the total number of persons who want to cross the bridge is either 1 or 2, we simply return the time taken by n – 1. For 1 person, n = 1 , timeToCross[n-1] will be timeToCross[0] which will be the only input to the problem. For 2 persons, n = 2 , the array is sorted, hence timeToCross[n – 1] = timeToCross[2 -1] = timeToCross[1]. This is the slowest of the 2 persons and the input is also 2 people. The first ‘if’ condition in the code takes care of this scenario.

###### When there are 3 people to cross the bridge, n =3

If n=3 , time taken will be addition of all 3. How is that ? If A, B and C were to cross the bridge, A and B start the journey, time taken will be the addition of: time taken by ‘B’ , followed by ‘A’ returning with the torch and finally time taken by ‘A’ and ‘C’ which is time taken by ‘C’. So time taken by A +B + C. This is handled with 2nd if condition.

###### Back to our puzzle where we have 4 people, the final step , step 5

At the end of step 4, C and D are on the other side of the bridge. We are left with A and B. When A and B start crossing the bridge, time taken by them is 2 minutes, since B, the slower one takes 2 minutes. The total time upto step 4 was calculated by code on line 2 below.

```     //n>=4
int time = timeToCross[1] + timeToCross[0] + timeToCross[n-1] + timeToCross[1];

return time + totalTime(timeToCross, n - 2)
```

For final step 5, last line above is executed. When called recursively, n < 3, so we return timeToCross[1]. So when ‘A ‘ and ‘B’ are left, timeToCross[1] will be time taken by ‘B’ which is 2. This final step 5 gets handled in the condition: if(n < 3).

```public static int totalTime(int[] timeToCross , int n)
{
if (n < 3)
{
//as the elements are sorted.
return timeToCross[n - 1];
}
//3 people will be addition of all.
...
//n >= 4
...
}
```
##### Does it work for all scenarios ?
###### Scenario 2

From a logical perspective –

1. A and B start their journey and take a total time of 2.
2. ‘A’ returns which means the total time is now 2+1 = 3.
3. ‘C’ and ‘D’ walk across, this means, 3 + 10 = 13.
4. ‘B’ returns with the torch, 13 + 2 = 15.
5. Finally, ‘A’ and ‘B’ walk across, 15 + 2 = 17.

In short, it is {A,B} + {A} + {C,D} + {B} + {A,B}

From the code perspective, n >=4 , so what is executed first is

```int time = timeToCross[1] + timeToCross[0] + timeToCross[n-1] + timeToCross[1];

return time + totalTime(timeToCross, n - 2)
```

timeToCross [] = {1, 2, 5, 10}. So, substituting these values in the code above results in: 2 + 1 + 10 + 2 = 15. See the trace of the logical step above, that is what we get at end of step 4. Finally, the 2nd line in the code snippet above is executed, the recursive call. This will result in 15 + recursive call with n-2.

When this recursive call is executed, n =2. So the first ‘if ‘ condition is satisfied, this returns 15 + timeToCross[n-1] , n = 2, so it returns 15 + timeToCross[1] which is 15 + 2, that is 17. So we get 15 +2 = 17. Looks like the code works fine.

###### Scenario 3

Well, let us apply the same approach like the earlier scenarios.

1. A+ B travel together, they take 20 minutes.
2. ‘A’ returns with the torch, 20 + 1 = 21.
3. ‘C’ and ‘D’ travel. This results in a total time of 21 + 22. 21 from earlier one and 22 from current. Total so far is 43.
4. Now ‘B’ comes back with the torch, 43 + 20 = 63.
5. Finally, ‘A ‘ and ‘B’ cross, 63 + 20 = 83.

Unfortunately, this is not the optimum solution.

We need another approach here. Let’s try to get C and D to the other end but this time with A, the one taking the least duration to cross.

1. A + D travel together, time taken is 22.
2. Then ‘A’ returns, total time is 22 + 1 = 23.
3. Then ‘A’ and ‘C’ travel. This results in , 23 + 21 , 23 from earlier one and 21 from current. The total so far is 44. Note that, at the end of this step, ‘C’ and ‘D’, the slowest among all are on other side of the bridge.
4. Now ‘A’ comes back, 44 + 1 = 45.
5. Finally, ‘A ‘ and ‘B’ cross, 45 + 20 = 65.

From the code perspective, we need to make changes to handle this scenario as well. So the sequence here is – {A , D} ,{ A } , {A , C} , {A } , {A , B}. Since, n =4, we get :

timeToCross[n-1] + timeToCross[0] + timeToCross[n-2] +timeToCross[0]

The n -1 indicates the index of ‘D’, n -2 indicates index of ‘C’. After this, we have the recursive call which will handle the last part of A+B travelling together.

##### Two cases for all scenarios

We have seen 2 cases now. How do we choose between them ? Well, we take the minimum from both and solve the subproblem at hand. Then the recursive calls will solve the rest of the problem.

```int timeTakenCaseOne = timeToCross[1] + timeToCross[0] + timeToCross[n-1] + timeToCross[1];
int timeTakenCaseTwo  = timeToCross[n-1] + timeToCross[0] + timeToCross[n-2] + timeToCross[0];
```
```public static int totalTime(int[] timeToCross , int n){
//Either 2 people or 1 person.
if (n < 3)
{
//as the elements are sorted.
return timeToCross[n - 1];
}
//3 people will be addition of all.
else if (n == 3)
{
return timeToCross[0] + timeToCross[1] + timeToCross[2];
}
// n >= 4
else
{
int timeTakenCaseOne = timeToCross[1] + timeToCross[0] + timeToCross[n-1] + timeToCross[1];
int timeTakenCaseTwo  = timeToCross[n-1] + timeToCross[0] + timeToCross[n-2] + timeToCross[0];

if (timeTakenCaseOne < timeTakenCaseTwo)
{
return timeTakenCaseOne + totalTime(timeToCross, n - 2);
}
else if (timeTakenCaseTwo < timeTakenCaseOne)
{
return timeTakenCaseTwo + totalTime(timeToCross, n - 2);
}
return timeTakenCaseTwo + totalTime(timeToCross, n - 2);
}
}
```

The are no changes in the code when n < 2 or when n = 3. Only changes are when n >= 4. We need to handle 2 scenarios and take the minimum from them. The calculation, timeTakenCaseOne has been calculated like before. timeTakenCaseTwo is the calculation which we had to consider for a scenario that failed. We simply consider the minimum value and recursively solve the subproblem.

##### Conclusion

We considered multiple scenarios and finally we came up with 2 paths out of which we considered the optimum path. The code can handle all scenarios now and is generic enough for ‘n’ persons wanting to cross the bridge. This was done using recursion which can be a very effective technique to solve problems like the bridge and torch.

The bridge and torch puzzle is an interesting one, the code is really not that difficult but one needs to be aware of all scenarios. As a quick tip, we find optimum time between the 2 cases mentioned below and then apply recursion.

1. ‘C’ and ‘D’ (the slowest) cross together.
2. ‘C’ and ‘D’ (slowest) cross with ‘A’, the fastest among all.

I would request you to solve one scenario on paper to get a much better understanding of the same. A good scenario would be the following input {1,6,10,13,15,16,17}. The output of this should be 75.

Happy bridge crossing !

##### References

A very interesting paper by Rote on this puzzle which does a deep dive.

R-Bloggers has a very good read on the same problem, the code is in R language.

## How to find if 2 strings are anagrams in Java without sorting ?

In this blog we are going to learn how to find if 2 given strings are anagrams of each other. We will be solving this problem without sorting the 2 strings and see if we can improve on the time complexity. I have a step by step explanation of finding if 2 strings are anagrams using a sorting technique here. If you are completely new to anagrams and would like know about solving this in Java using sorting, I would urge you read that first.

##### How can we solve this problem without sorting the strings ?

Let’s start with a simple example, an example which we saw in the previous blog about anagrams – “evil” and “vile” or “coronavirus” and “carnivorous”. These are anagrams since the characters in them are the same and they appear the same number of times, the characters are just rearranged.

They key here is that they appear the same number of times. This means the frequency of each character in the 2 strings is the same. In the string “evil”, each character, ‘e’, ‘v’, ‘i’ and ‘l’ appears once in the string “vile”.

The image below shows you the frequency of each character in the strings “coronavirus” and “carnivorous”

It is clear that each character in “coronavirus” has same frequency as characters in “carnivorous”. Can we use this frequency to figure out if they are anagrams ?

##### Finding out the frequency of each character in the string

Like the previous blog, we are going to remove any spaces and also going to convert all letters to lowercase. So let’s begin with some code.

```public static boolean isAnagram(String first, String second) {

char[] charactersOfFirst = first.replaceAll("\\s", "").toLowerCase().toCharArray();
char[] charactersOfSecond = second.replaceAll("\\s", "").toLowerCase().toCharArray();

if (charactersOfFirst.length != charactersOfSecond.length) {
return false;
}

//Code here for frequency check.

return true;
}
```

We have converted both strings into character arrays like we did in the version of the code which used sorting.

How do you usually check the frequency of any object ? If I were to give you a bag full of toys and asked you to tell me the type and the number of each type of toy, you would probably say – “There are 3 planes, 2 tennis balls and 1 football.” What did you just do ? We grouped each type of toy and starting counting them. You must be saying to yourself, “Why did he come up with an example of counting toys !”. Well, with a lockdown, with kids home and the ever increasing list of things to do, you better know everything about all the toys at home !

With strings, which are composed of characters, we need to count each type of character. You can imagine a string as a bag full of characters. In the toy example, we had only 3 items. It’s easy to remember 3 items and the count of each one of them. What if the bag had 15 items ? Would you be able to remember that along with the number of each type ? You would probably make a note of it and have 2 columns, toy type and count. In case of characters, we need to find out the type of character(letter) and the count of each character. So, we need 2 things, character type and count of each type. How many lower case letters can there be ? Well, 26. You wouldn’t make 26 variables now. How can we emulate a note like structure ? Well, an array can help us here. What should be the size of the array? 26, for 26 letters, ‘a’ – ‘z’.

```        int[] frequencies = new int[26];
```
###### How do we maintain the count against each character ?

We have defined an array of size 26 to store the count of each character from ‘a to ‘z’. But how do we increase of count of ‘c’ if we get multiple ‘c’ ? Every letter has an Ascii code. For the letter ‘a’, it is 97, ‘b’ is 98 and so on. What if we could store the count of the character ‘a’ at index 0, ‘b’ at index 1 and so on? Well if the character in the string is an ‘a’ and we subtract an ‘a’ from it, we are actually saying ‘a’ –‘a’ or 97 – 97 which is 0. This can be used as an index into the frequency array which we defined above. If we get a ‘b’, we find the index of ‘b’ as ‘b’ – ‘a’ which is 98 – 97 = 1. So we access index 1 in the array. We do the same for every character we encounter in the string.

Now, we need to store the value at each index – the value will be the count of each character. The values in the array will be initialized to 0. Each time we encounter a character, we access the array at the correct index and simply increment the value.

Let’s take an example of 2 strings, “abby” and “baby”.

As shown above, the index of ‘a’ is 0, ‘b’ is 1 and so on. When we start visiting each character in the string “abby”, we perform a ‘character’ -‘a’ and simply increment the counter at that index. The value at index 1 is 2, this shows that ‘b’ occurs twice. The characters ‘a’ and ‘y’ appear only once. Using this logic, we have maintained the count of each character in the frequency array.

```for (int i = 0; i < charactersOfFirst.length; i++) {
frequencies[charactersOfFirst[i] - 'a']++;
}
```
###### What about frequency of the characters in the second string, “baby” ?

We could create another array and store the frequency of the characters in that 2nd array. Once we create that 2nd array, the 2nd array would have same values for the string “baby” since ‘b’ occurs twice and the characters ‘a’ and ‘y’ appear once. We could then iterate through arrays and compare the value at each index. If a value at an index is different, they are not anagrams.

Do we need a second array ? Can we use the same array for the 2nd string as well ? What we could do is simply decrement the count in the frequency array for each character that occurs in the 2nd string. So for the 2nd string, if we encounter an ‘a’, we go to the index of ‘a’, which is 0 and decrement the value at that index. This will make it 0 for the current example.

```frequencies[charactersOfSecond[i] - 'a']--;
```

How does this help ? Well, if the frequency of the characters in the 2 strings are the same, the first increments it and the 2nd decrements it and at the end of it, all values in the array should be zero.

As shown in the figure above, when we iterate through the first string, we increment the count as shown in top half. In the bottom half, we decrement the values in the same array. The final values can be seen in the middle. In this case, since “abby” and “baby” have same frequency of characters, the entire array has value 0.

##### Combining all these changes in the code
```public static boolean isAnagram(String first, String second) {

char[] charactersOfFirst = first.replaceAll("\\s", "").toLowerCase().toCharArray();
char[] charactersOfSecond = second.replaceAll("\\s", "").toLowerCase().toCharArray();

if (charactersOfFirst.length != charactersOfSecond.length) {
return false;
}

int[] frequencies = new int[26];

for (int i = 0; i < charactersOfFirst.length; i++) {
frequencies[charactersOfFirst[i] - 'a']++;
frequencies[charactersOfSecond[i] - 'a']--;
}

for (int frequency : frequencies) {
if (frequency != 0) return false;
}

return true;
}
```

The 2nd for loop checks if any value in the frequency array is not equal to 0. A value other than 0 would indicate that either there is a different character or frequency of the characters do not match. A positive value would indicate a character in the first string that does not appear in the second and a negative one means the character appears in the 2nd string and not in the first.

###### Conclusion

Using a single array and the ascii code of the letter to count the frequency of the characters is a simple but effective approach to check if 2 strings are anagrams. In fact, this solution has a time complexity of O(n). We did reserve an array of size 26 but that is not much of a concern since we don’t resize the array. We could have avoided the use of the character array and used another string after removing the spaces and converting the string to lower case but I will leave that as an exercise for you. Happy anagramming !

## A Step by Step guide to find an anagram in Java

In this blog I am going to give you a detailed understanding of how to find if two strings are anagrams of each other. We will first understand what an anagram is, consider different types of input data and then finally move on to write the code in Java. Like always, we will approach this step by step. Along the way, I will deliberately make a few mistakes which will result in incorrect results for a few cases. We will then fix the code so that we get the appropriate results for all inputs. This way, you will understand the code a lot better.

##### What is an anagram ?

An anagram is a word or a phrase formed by rearranging the letters of another word or phrase. This is straight out of wiki. I think it is a good read if you are interested in the history of anagrams and the application of anagrams.

Let us break the definition down into 2 parts –

1. ‘An anagram is a word or a phrase’ – The phrase part is important as most examples focus on just a single word.
2. ‘formed by rearranging the letters of another word or phrase’ – This is straightforward to understand – the key here is rearrangement.
###### Examples of Anagrams
1. evil” = “vile” – Of course they don’t mean the same ! These are anagrams since the frequency of each character is the same in both words. It is just rearranging the characters in the word ‘evil’, which gives us the word vile.
2. “coronavirus” = “carnivorous” – same frequency of each character in the words coronavirus and carnivorous and just rearrangement of characters.
3. “debit card” = “bad credit”. This is a different kind of an example – a phrase ! Note that this has a space in between, make a note of this. The characters in the phrase on the left side have same frequency of characters as on the right side.
4. “William Shakespeare” = “I am a weakish speller”. A couple of different things to notice in this example – The name on the left side is in uppercase but the one on right side is in lowercase. Another observation is that the name has changed into a sentence. The frequency of the characters on the left side is still the same as on the right side, just rearrangement as usual.
##### Common observations

For 2 words or phrases to be anagrams –

1. The 2 words/phrases must have same characters along with same frequency.
2. They can have a space in between which we need to handle.
3. Upper/Lower case of the words/phrases should be handled appropriately.
##### Time for some code

We need to check if 2 strings/phrases are anagrams. Hence, the input will be 2 strings. Let’s assume that they are not null. If they are anagrams, we return a true else return false. This can easily be translated into a function in Java which takes 2 parameters and returns a boolean value. Let’s call that function, isAnagram.

```public static boolean isAnagram(String first, String second) {

return true;

}
```

The function, isAnagram, takes 2 parameters and returns true for the moment.

Let’s consider our first example of “evil” and “vile”. These are anagrams. The characters have been rearranged. What if we were to arrange them in the same way ?

To arrange the characters in the same way, we need the characters from the string. A string is made up of characters. We can use the toCharArray function on a string to get each character.

```char[] charactersOfFirst = first.toCharArray();
char[] charactersOfSecond = second.toCharArray();
```

We have our character array from each string. How do we arrange them in the same way ? Well, we can sort the characters in each array using the Arrays class.

```Arrays.sort(charactersOfFirst);
Arrays.sort(charactersOfSecond);
```

What is left now is simply checking if the sorted characters are the same. How do we do that ? We can use the Arrays. equals method for this and pass the sorted character arrays to it.

```return Arrays.equals(charactersOfFirst, charactersOfSecond);
```
###### Combining the code from last 3 steps
```public static boolean isAnagram(String first, String second) {

char[] charactersOfFirst = first.toCharArray();
char[] charactersOfSecond = second.toCharArray();

Arrays.sort(charactersOfFirst);
Arrays.sort(charactersOfSecond);

return Arrays.equals(charactersOfFirst, charactersOfSecond);
}
```

Well, that’s it ! Passing the inputs as “evil” and “vile” gives us true. Passing inputs as “coronavirus” and “carnivorous” also give us true.

###### Does this code work for all cases ?

If we were to pass the inputs as “customers”and “store scum”, the function returns false. It should have returned true. The characters are the same along with the frequency. However, did you notice that there is a space in the second word , store scum?

Do you remember that this was one of the scenario we were going to handle ? Well, now is the right time to handle it ! This is simple – just replace the space between the words with an empty string. How do we do that in Java? Use the replaceAll method from String class.The replaceAll method takes 2 parameters, a regular expression in String format and the replacement String. The regular expression for space is: “\s” and we need to replace it with “”, an empty string. So with this understanding, our modified code will be –

```public static boolean isAnagram(String first, String second) {

char[] charactersOfFirst = first.replaceAll("\\s", "").toCharArray();
char[] charactersOfSecond = second.replaceAll("\\s", "").toCharArray();

Arrays.sort(charactersOfFirst);
Arrays.sort(charactersOfSecond);

return Arrays.equals(charactersOfFirst, charactersOfSecond);
}
```

You can see the highlighted code for the changes. The extra ‘\’ in “\\s” is to escape the ‘\’ in the string “\s”. With this change, we get the correct output of true when the input is “customers” and “store scum”. If we were to pass the input as “debit card” and “bad credit”, we get true.

Are we done now ? Well, not really. If we were to pass the input as “William Shakespeare” and “I am a weakish speller”, we get false, which is the incorrect answer. The frequency of the characters is the same in both strings, we handled the space as well.

Why is it failing ? Did you notice that the characters ‘W’ and ‘S’ in the first input string are in capital letters but in the second string, they are in lower case. The character arrays are sorted based on the ascii codes for upper and lower case letters. Ascii code for upper case letters starting from ‘A’ begins from 65 and for ‘a’, it starts from 97. So sorting them with mixed case characters and then applying equals does not help. The Arrays.sort method sorts each character array in ascending format. So in each character array, you see upper case letters(lower ascii) first followed by lower case(higher ascii value). Let’s modify the code to handle this scenario.

```public static boolean isAnagram(String first, String second) {

char[] charactersOfFirst = first.replaceAll("\\s", "").toLowerCase().toCharArray();

char[] charactersOfSecond = second.replaceAll("\\s", "").toLowerCase().toCharArray();

Arrays.sort(charactersOfFirst);
Arrays.sort(charactersOfSecond);

return Arrays.equals(charactersOfFirst, charactersOfSecond);
}
```

As shown in the highlighted code above, we only add the call to the function toLowerCase(). We add this function call for both the inputs. By doing this, we treat characters in both inputs as lower case. Now, if were were to pass the input as “William Shakespeare” and “I am a weakish speller”, we get true, which is the correct input.

I know what you are thinking now. You must be saying , “Oh, please tell me that we are done now ! “. Well, just one more change and our code will be ready for all scenarios. In fact I would say the next change is more of an improvement.

##### Final changes to the code

We have handled spaces, case sensitivity and the contents of the string by converting it to a character array and then sorting it. But what if the input strings are of unequal length even after removing the spaces ? In this scenario, we don’t want to sort the array and compare them later. What we can do is simply check for the length of the 2 character arrays after we remove the spaces between the words.

```public static boolean isAnagram(String first, String second) {

char[] charactersOfFirst = first.replaceAll("\\s", "").toLowerCase().toCharArray();
char[] charactersOfSecond = second.replaceAll("\\s", "").toLowerCase().toCharArray();

if (charactersOfFirst.length != charactersOfSecond.length) {
return false;
}

Arrays.sort(charactersOfFirst);
Arrays.sort(charactersOfSecond);

return Arrays.equals(charactersOfFirst, charactersOfSecond);
}
```

It would be incorrect to check for length of the input strings as the first step in the function. If the input strings were “William Shakespeare” and “I am a weakish speller” and we were to check for the length of the string before converting it into a character array, the code would return false. The length of the string “William Shakespeare” is 19 and length of “I am a weakish speller” is 22. Even though they are valid anagrams, comparing input string lengths would not be right.

##### Conclusion

We have handled most of the scenarios and I think the code above is the final version. But it is the final version using this approach of sorting the character array and using the Arrays.equals method to check for contents. This is not just a valid solution but a good solution as well. I have not considered a scenario where the string contains special characters but this can be handled in the same way we handled the spaces.

The code above which uses sorting has time complexity of O(n log n). We can improve this code further by using a different technique where we can avoid the sorting. I will definitely write another blog on this soon. Until then, Happy Anagramming !

## How to find permutations of a String using recursion in Java ?

In this blog we are going to find out all the permutations of a given string. Like always, we will first start from the basics – Understand what is a permutation of a string, break the procedure down into smaller steps and understand the procedure of finding out one permutation. Finally, we will write code in Java for the same. Along the way, I will also be explaining each line code and show you pictorial representations of the code execution so that you can visualize it better.

##### What is a permutation ?

Different ways of arranging a set of items is permutation. A string is a sequence of characters. Permutation of a string is arranging the characters of the string in different ways. Let’s take an example to understand this.

###### Permutation of a String

The string “ace” can be arranged as “ace”, “aec”, “cae”, “cea”, “eac”,”eca” – different arrangements of the characters a,c,e which make the string “ace”. Note that the string “ace” is of length 3 and we get 6 different permutations of the same – 3 factorial. If the input string was “aced”, we will get 24 permutations – 4 !

Did you notice that the first 2 permutations “ace”, “aec” have a as the first letter and the 2 other letters are then concatenated to the letter a.

Extracting the first character ‘a’ from “ace” leaves us with the remaining characters “ce”. It can be rearranged as “ce” , “ec”. Finally appending each to “a” results in “ace” and “aec“.

If we single out the character ‘c’ in ace, we are left with “ae”. With “ae”, rearranging them gives us “ae” and “ea”. Appending this to ‘c’ results in “cae” and “cea“.

If we single out the character ‘e’ in ace, we are left with “ac”. With “ac”, rearranging them results in “ac” and “ca”. Appending this to ‘e’ results in “eac” and “eca“.

##### Translating these observations into a technical perspective

We are taking a single character from the given string, starting with ‘a’, moving on to ‘c’ and finally visiting ‘e’. This can be done using the charAt function. We also need a for loop as we need to single out each character from the string.

```for(int i = 0; i < remainingString.length();i++) {
char ch = remainingString.charAt(i);
...
}
```

For each character that we extract, we need the rest of the string. So when we extract ‘a’ from the “ace”, we need “ce” so that we can have different arrangements of “ce” to append it to ‘a’. When we extract ‘c’ from “ace”, we need “ae”. When we extract ‘e’ from “ace”, we need “ac”. In short, when we are at a particular iteration , i , in the for loop, we need a string from the characters before and after that character.

###### How do we extract the remaining characters ?

We make use of the substring function to do that. The variable ‘i’ in the for loop points to current single character that we extract. When we extract ‘c’ from “ace”, we need to get “ae”. We can get all characters before i by making a call to substring(0,i) and everything after i by calling substring(i+1). We append them to get the remaining string.

```for(int i = 0; i < remainingString.length();i++) {
char ch = remainingString.charAt(i);
String next = remainingString.substring(0,i)  +
remainingString.substring(i+1);
...
}
```
##### Applying recursion

What is clear so far is that we start with the first character and apply permutation with remaining characters. Then we choose the second character and apply permutation with remaining characters. We continue this way until we visit each character in the string. To do something like this, recursion can be a good choice.

So let us take the code above and add it to a function, permutations.

```public void permutations(String remainingString , String permutation) {
for(int i = 0; i < remainingString.length();i++) {
char ch = remainingString.charAt(i);
String next = remainingString.substring(0,i)  +
remainingString.substring(i+1);
//Code here for recursive call to permutations
}
}
```

This function takes 2 parameters – remainingString and permutation. Why do we need them ? Well, the parameter remainingString keeps track of length of string to produce one complete permutation of current string.The permutation parameter will keep track of the current permutation.The first time this code starts executing, the remainingString will be the input string, “ace”, and the permutation will be a blank string, “”, since we are yet to start finding permutations. Now we start with ‘a’,fix that and then extract “ce”. So ‘a’ will be stored in ch and “ce” will be stored in variable referred to as next.

###### What do we have so far ?

remainingString = “ace”, permutation = “”, ch = ‘a’, next = “ce”

###### What should the next step be?

The variable, permutation, so far is “”, it should be “a”. It is not a valid end permutation but an intermediate one. The current value is a “”. Appending “” to “a” gives us “a”. So let’s define a variable permute and assign it to permutation +ch.

```            String permute = permutation+ch;
```

So the variable permute = “” + “a” = “a”

```public void permutations(String remainingString , String permutation) {
for(int i = 0; i < remainingString.length();i++) {
char ch = remainingString.charAt(i);
String permute = permutation+ch;
String next = remainingString.substring(0,i)  +
remainingString.substring(i+1);
//Code here for recursive call to permutations
}
}
```

Now, remainingString = “ace”, permutation = “”, ch = ‘a’, next = “ce”, permute =”a”

The next logical step is working on “ce” to extract ‘c’. Once that is done, the intermediate permutation is “ac”. “a” from the previous iteration and ‘c’ extract from current one. When we extract ‘c’ from “ce”, what remains is “e”. This is the same sequence as previous steps.

The solution seems to repeat for the next sub-problem. This can be solved by recursion. We need to call the permutations function. It takes 2 parameters – remainingString and permutation. The variable, next, has value “ce” and permutation currently is “a”. Let’s make a call to permutations function and pass these parameters.

```public void permutations(String remainingString , String permutation) {
for(int i = 0; i < remainingString.length();i++) {
char ch = remainingString.charAt(i);
String permute = permutation+ch;
String next = remainingString.substring(0,i)  +
remainingString.substring(i+1);
//Code here for recursive call to permutations
permutations(next,permute);
}
}
```

After the first recursive call, remainingString = “ce”, permutation = “a”. When code above starts execution, i = 0 , ch = ‘c’ , permute = “a” + ‘c’ = “ac” , next = “e”. Note that when this call happens, i = 0 . This block will get executed twice as the for loop checks for length of remainingString. More on this later. Then there is a recursive call again to the function by passing “e”, “ac”.

In the next iteration, remainingString = “e”, permutation = “ac”. When the code starts executing, i = 0 , ch = ‘e’ , permute = “ace” , next = “”. Then there is a call to recursive function with “” and “ace”.

Now , remainingString = “” , permutation =”ace”. It looks like the remainingString is a blank string along with the fact that permutation is “ace”. We are in a recursive function, every recursive function should have some condition to return if it has processed it’s sub-problem. This part is now solved, isn’t it ? So we need a terminating condition – the length of the variable, remainingString, can be that condition. We simply check if it’s length is zero.

```public void permutations(String remainingString , String permutation) {
if(remainingString.length() == 0 ) {
System.out.println(permutation);
return ;
}

for(int i = 0; i < remainingString.length();i++) {
char ch = remainingString.charAt(i);
String permute = permutation+ch;
String next = remainingString.substring(0,i)  +
remainingString.substring(i+1);
permutations(next,permute);
}
}
```

After the execution of this code we get “ace” and this function returns. The code execution continues from the the location that it was called – this is really the previous step. Take a look at the following flows to get a better understanding. Start from the block which says start and then the steps have been numbered.Push and pop indicates recursive function calls and returning back from a function.

##### Snapshot of the function calls when i = 0 and input is “ace”

Step 1 will get executed twice as length of “ce” is 2. When i is 0, we get “ace” and when i =1 , we get “aec”. When the function returns from step 2, we go back to step 1 where i will become 1. This will cause step 4 to be executed.

Note that, all these steps are happening when input is “ace” and i = 0. When i =1, a similar set of steps will be executed producing 2 more permutations.

##### Snapshot of the functional calls when i = 2 and input is “ace”

The images below will give you a more detailed view of how the code and function calls execute. We call the function, permutations, pass the parameters “ace” and “”.

##### Snapshot of the code execution when input is “ace” and i=1

I have left out the code tracing when i=2, it can be a good exercise for you.

##### Conclusion

The number of lines of code that we had to write to produce the permutations is small but there is a lot that is happening behind the scenes.Such kind of problems are being asked in technical interviews. Irrespective of this, I think recursion is an important concept to understand and it is also a good fit for a good number of problems.

Recursion is not very straight forward to understand but I hope the pictorial representations and breaking up the code step by step have given you a good understanding of the same. I urge you to take a piece of paper and trace the execution for one particular iteration – this will not only solidify your understanding of the solution to the permutation problem but help you sharpen your skill set by understanding recursion.

## How to find all duplicates in an array – Java and Kotlin

During a conversation with my colleague, he mentioned to me about a problem that he was asked in his technical interview. The problem was to find the duplicates in an array of integers. My immediate reaction – “That is easy and I am sure you got it !” But just then there was a two second silence from his end and then he said that he couldn’t get it right since some additional constraints were mentioned to him ‘later’.

##### Problem Statement

Find the elements which appear twice in an array of integers, where the elements in the array being : 1 ≤ a[i] ≤ n (n = size of array). We need to do this without using additional space in O(n) runtime.

##### Solution

Now, it was my turn to be silent for the next couple of seconds after he told me about the problem statement with the constraints about not using additional space and O(n) runtime.

We had a discussion about using a Set or may be a HashMap in Java since the main part of the problem was to find the “duplicates”. Using a Set or a Map would not be the right solution with these constraints. A nested for loop would also not be the right solution since we need to solve the problem in O(n) runtime. Well, let’s consider some sample data and try solving this step by step.

##### Sample Input data

The output for this input will be 10 and 1. They both appear twice. Note that the length of the array is 10 and the maximum value of any element in the array is <=10. This is an important constraint.

##### Let us solve this step by step
1. Loop through the array and for each iteration-
1. Take the value at each index. Currently at 0, in the first iteration, the value will be 10
2. Subtract one from this value. During iteration 0, the result will be 9. The reason we subtract one is because the value of any element in the array is <=n, where is n is size of the array. The array index starts from 0. So an array of size 10 can contain a maximum value of 10 but there is no arr[10].
3. Use this result as an index. For iteration 0, this will be 9, go to element number 9 and negate the value at this index number 9
##### Why should we do this and what about the duplicates ?

Well, if we encounter another value of 10 in this array, the index obtained using steps above will result in 9 again. We access to value at 9th position which is -7 now. We check if this is less than 0 and if it is less than 0, it means we have already visited the ‘value at this current iteration‘. This means it is a duplicate value. So step 3 in the algorithm above can be modified as follows:

Loop through the array and for each element in the array, let’s refer to the array as arr, do the following –

1. Take the value at each iteration. Currently at 0 in the first iteration, the value will be arr[0] which is 10.
2. Subtract one from this, the value will be 9. Let us refer to this value as index.
3. Using this index, access the value at this index, element at index 9, arr[9]. If the value at this index is less than 0, add arr[current_iteration] to the list of duplicate elements.
4. Negate the value at this index.(currently 9 for this iteration 0)
5. Go back to step 1, the next iteration which is current_iteration + 1.
###### Iteration 4

In this iteration number 4, when we access the value at arr[4], we get a -9. If we were to follow step 2 of the algorithm, we would land up with an index of -10 and then in step 3 we would access arr[-10] which is incorrect. So we need to modify the algorithm to take absolute value of the same.

##### Java Code
```import java.util.ArrayList;
import java.util.List;

public class DuplicatesInArray {

public static List<Integer> findDuplicates(int arr[]) {
List<Integer> duplicates = new ArrayList<>();
for (int i = 0; i < arr.length; i++) {
int index = Math.abs(arr[i]) - 1;
if (arr[index] < 0){
}
arr[index] = -arr[index];
}
return duplicates;
}

public static void main(String[] args) {
int [] arr = {10,2,5,10,9,1,1,4,3,7};

List<Integer> duplicates = findDuplicates(arr);
System.out.println(duplicates);
}
}
```

The Math.abs is required since we could have negated the value at an index in a previous iteration. If we don’t do a Math.abs, we will land up accessing arr[-index]. For the same reason, Math.abs is also required while adding an element to the list of duplicate values.

###### Kotlin code
```fun findDuplicates(arr:IntArray) : List<Int>{

var duplicates  = arrayListOf<Int>()
for(itemIndex in arr.indices){

val goToIndex = Math.abs(arr[itemIndex]) - 1

if(arr[goToIndex] < 0 ){
}

arr[goToIndex] = -arr[goToIndex]
}
return duplicates
}

fun main(){
var arr = intArrayOf(10,2,5,10,9,1,1,4,3,7)
println(findDuplicates(arr))
}
```
##### Conclusion

We have traversed the entire array and the list of duplicates has 2 elements: 10 and 1. The flip side of this algorithm is that the elements of the array are modified but we have not used any additional storage. We have also managed to do this in O(n) as this is just a single pass of entire array.

The code in Java and Kotlin is quite simple but you need to know the algorithm/solution for this particular problem before hand. This problem is an interesting one given the constraints of space and time but I don’t think the solution was so straight forward. In my opinion, I don’t think the outcome of a technical interview should be decide based on just this problem.