# BFS and DFS Practice Problems

Last time, we introduced the two major tree searching algorithms, which are **breadth first search (BFS)** and **depth first search (DFS)**. Today, we’ll be going over a couple of practice problems to help us solidfy our understanding of these two important algorithms. We’ll go through these two exercises step by step.

## The Chess Knight Problem

*Given a standard 8x8 chess board, find the minimum number of moves that a knight must take in order to reach a particular destination square from a given source square on the chess board.*

*This problem is adapted from Techie Delight.*

For this problem, please navigate to the `repl.it`

repo linked here and fork the `repl`

.

In the game of chess, the knight is a chess piece that has strict requirements for how it can move. Namely, it must move either (1) two square vertically and one square horizontally, or (2) two squares horizontally and one square vertically. You can read more about the knight on Wikipedia. Here is also a helpful diagram from Techie Delight that illustrates the valid moves for a knight with red X’s.

The word ‘*minimum*’ tells us that we should use the BFS algorithm for this problem. To sketch out our approach, we can represent each of the 64 squares of the chess board as vertices in a graph, with edges connecting squares that a knight can directly reach in exactly one move. We’ll start at the source square, and then use BFS to explore the board until we arrive at the destination.

The first thing that we need to do is write a Java class that will represent each of the vertices in our graph. In our implementation, these vertices will be `Knight`

objects, which you will implement in the `Knight.java`

source code linked above. Our `Knight`

objects have to keep track of the `x`

position on the chess board that this node represents, the `y`

position on the chess board, and the number of steps that the knight has taken so far. Note that `x`

and `y`

must both be between `0`

and `7`

inclusive because a standard chess board has 8 by 8 squares.

**Problem 1:** Read through the starter code to make sure that you understand its structure. Implement the constructor, `getX()`

, `getY()`

, and `getStepsTaken()`

functions in `Knight.java`

. These should be fairly straightforward.

*Hover here to see the solution.*

```
public Knight(int x, int y, int stepsTaken) {
this.x = x;
this.y = y;
this.stepsTaken = stepsTaken;
}
public int getX() { return this.x; }
public int getY() { return this.y; }
public int getStepsTaken() { return this.stepsTaken; }
```

There is one more function that we need to implement in `Knight.java`

: the `move()`

function. This function is important because it will ultimately help us move from one square to another on the chess board. This function takes in a `Knight k`

and a “*move number*” `n`

(described below) and generates a new `Knight`

node object to represent that chess move to the new square. A couple things to keep in mind as you’re writing this function:

- As we described above, a knight has either different sets of valid “moves” that it can make on the chess board. For this problem, we have represented these space of possible moves with the
`int[]`

arrays`movesLR`

and`movesUD`

. For a move to be valid for the knight, the new`Knight`

must have moved`movesLR[i]`

steps in the left-right direction and`movesUD[i]`

in the up-down direction, where`i`

is any number between`0`

and`7`

inclusive. We refer to`i`

as the “*move number*” from above. - The knight cannot be moved to a coordinate that is not on the actual chess board. This means that in order for a move to be considered valid, both the
`x`

and`y`

coordinates must stay between`0`

and`7`

inclusive. If this is not the case, then you can simply return`null`

. - Recall that
`stepsTaken`

keeps track of how many steps the knight has already taken to arrive at this new square from the source square. Therefore, you must make sure to increment the number of steps taken by`1`

when generating the new`Knight`

object.

**Problem 2:** Implement the `move()`

function in `Knight.java`

now.

*Hover here to see the solution.*

```
public static Knight move(Knight k, int n) {
/* Ensure that a valid move number was given as an argument. */
if (n < 0 || n > 7) { return null; }
int newX = k.getX() + Knight.movesLR[n];
int newY = k.getY() + Knight.movesUD[n];
/* Ensure that a valid move was made. */
if (newX < 0 || newX >= BOARD_SIZE || newY < 0 || newY >= BOARD_SIZE) {
return null;
}
Knight newKnight = new Knight(newX, newY, k.getStepsTaken() + 1);
return newKnight;
}
```

At this poit, we’re now finished with our `Knight.java`

implementation. Let’s turn our attention now to `Main.java`

. When implementing BFS, recall that we don’t want to visit the same chess square twice. To ensure this, we have a `HashSet`

of `Knight`

objects called `visited`

, which will keep track of `Knight`

objects that we have already visited. We want the `seen()`

function in `Main.java`

to return whether or not the argument `Knight k`

has already been visited before, through making appropriate usage of the `visited`

`set`

.

**Problem 3:** Implement the `seen()`

method in `Main.java`

now.

*Hover here to see the solution.*

```
public static boolean seen(Knight k) {
for (Knight piece : visited) {
if (piece.getX() == k.getX() &&
piece.getY() == k.getY()) {
return true;
}
}
return false;
}
```

Now comes the main part of this exercise: implementing the BFS algorithm in the `minSteps()`

function. This function takes two arguments: `src`

source square coordinate and `dst`

destination square coordinate. Both of these cooredinates are `int[]`

objects in the form `{ x-coordinate, y-coordinate }`

. This function should return the minimum number of moves the knight needs to take to get from `src`

to `dst`

. If it isn’t possible for the knight to get to `dst`

using only valid moves, then you should return `-1`

.

**Problem 4:** Implement the `minSteps()`

method in `Main.java`

now.

*Hover here to see the solution.*

```
public static int minSteps(int[] src, int[] dst) {
// Queue to keep track of which squares to go to next.
Queue<Knight> q = new ArrayDeque<>();
// Generate a node using the src source coordinates, and queue node.
Knight srcPiece = new Knight(src[0], src[1], 0);
q.add(srcPiece);
while(!q.isEmpty()) {
Knight piece = q.poll();
// Handle the case of when we reach the destination dst.
if (piece.getX() == dst[0] && piece.getY() == dst[1]) {
return piece.getStepsTaken();
}
// Add this node to our set of visited nodes.
visited.add(piece);
// Make all possible valid moves and add them to the queue (if
// they haven't been visited before).
for (int i = 0; i < 8; i++) {
Knight newPiece = Knight.move(piece, i);
if (newPiece != null && !visited.contains(newPiece)) {
q.add(newPiece);
}
}
}
return -1;
}
```

You have now implemented BFS to solve this problem! Try running your code now to make sure that it works. If the program works as expected, you should get the following output:

```
It takes a minimum of 6 moves for the knight to get from (0, 7) to (7, 0).
```

This is just one test: feel free to write your own if you’d like! After you get this working, feel free to try out the extension/challenge problems starting here. *The first thing that you should do is change the*`SHORT_TEST`

`boolean`

*in the*`main()`

*function from*`true`

*to*`false`

** .** This will ensure that the driver program doesn’t just run the simple program tests, but also the extended program tests as well in the rest of the

`main()`

function.Last time, we discussed a couple of the practical differences between DFS and BFS algorithms. Namely, while BFS always gives us the shortest, optimal solution, DFS typically gives us a faster solution that requires less time to compute. Let’s try to explore this and see if this is the case here. Note that the DFS algorithm will only give us *one* possible route for the knight to get from `src`

to `dst`

, not necessarily the `shortest`

possible route.

The first thing for us to do is to actually implement the DFS algorithm:

**Challenge 1:** Implement the `findPath()`

method in `Main.java`

now. This should be very similar to the `minSteps()`

method that you implemented above, with the exception that this new function should implement the DFS altorithm as opposed to BFS.

*Hover here to see the solution.*

```
public static int findPath(int[] src, int[] dst) {
// Stack to keep track of which squares to go to next.
Stack<Knight> s = new Stack<>();
// Generate a node using the src source coordinates, and push node.
Knight srcPiece = new Knight(src[0], src[1], 0);
s.push(srcPiece);
while(!s.isEmpty()) {
Knight piece = s.pop();
// Handle the case of when we reach the destination dst.
if (piece.getX() == dst[0] && piece.getY() == dst[1]) {
return piece.getStepsTaken();
}
// Add this node to our set of visited nodes.
visited.add(piece);
// Make all possible valid moves and push them onto the stack (if
// they haven't been visited before).
for (int i = 0; i < 8; i++) {
Knight newPiece = Knight.move(piece, i);
if (newPiece != null && !seen(newPiece)) {
s.push(newPiece);
}
}
}
return -1;
}
```

After you complete this implementation, try running the driver code once more (again, ensure that `SHORT_TEST`

is set to `false`

in the `main()`

function). Based on your results, answer the following questions:

**Challenge 2:** Answer the following three questions.

- Which algorithm - BFS or DFS - gives a lower number of average knight moves made given randomly chosen sources and destinations? Does your answer make sense with your understanding of each of these two algorithms and what they accomplish?
- Which algorithm - BFS or DFS - is faster?
- Is your answer to part (2) consistent with what you know about BFS or DFS in general? Why or why not?

*Hover here to see the solution.*

Based on our solution code averaged over 10000 tests, we determined that the average path length found using DFS is 29 moves for the knight, while the average path length found using BFS is 2 moves. We know that BFS always yields the shortest, optimal solution, so this empirical result makes sense. What may be somewhat interesting is that the BFS algorithm takes less time to run compared to the DFS algorithm on average. For example, in our sample run, the DFS algorithm took about 1000 microseconds, while the BFS algorithm took about 400 microseconds. This may be surprising because theoretically, BFS should take longer to run than DFS. The reason for this descrepancy is that the BFS-derived optimal path is significantly shorter than the DFS-derived path, and so in this particular case, the number of nodes that DFS has to go through on average make the algorithm perform worse than expected compared to BFS.

It might also be useful for us to be able to print out the moves that the knight will take in order to get from the source to the destination. This is a pretty tricky feature to implement and completely optional, so feel free to try it out if you’d like! Otherwise, let’s move on to the next problem.

## Word Search Solver

*Given a two-dimensional square matrix of characters and a particular word, determine whether the word can be generated by going from character to character within the matrix. No cycles on the path from character to character to generate the word are allowed, and you're free to go up, down, left, right, or diagonal to get to the next character.*

*This problem is adapted from Program Creek.*

Similar to above, navigate to the `replt.it`

repo linked here and fork the `repl`

.

A word search is a common type of puzzle where we try to look for words in a matrix of characters. For example, consider the following matrix:

Following the red sequence of characters spells out the word `forms`

, while following the blue sequence of characters spells out the word `dean`

. There are also other words in this particular matrix, but here are two examples. However, the word `superstitious`

is definitely not in the matrix.

Similar to the chess knight problem from above, we’l break down this problem into smaller pieces to tackle. The first thing that we need to do is sketch out an approach to this problem. We’ll represent the word search matrix as a `char[][]`

matrix, and keep track of the word we’re looking for as the variable `SEARCH_WORD`

. Because we just want to check if the word is contained, and we’re not looking for an “optimal” path, this suggests that we should use DFS for this problem.

For the first part of this problem, you will implement a “deep copying” function to make a new copy of an input matrix. It isn’t clear yet why we’ll need this function, but rest assured we’ll use it in the near future.

**Problem 5:** Read through the starter code to make sure that you understand its structure. Then, implement the function `deepCopy()`

, which takes in a `boolean[][]`

matrix and returns another `boolean[][]`

matrix that has the exact same elements. You can read about what exactly "deep copying" is here.

*Hover here to see the solution.*

```
public static boolean[][] deepCopy(boolean[][] m) {
// Create a new matrix object.
boolean[][] newM = new boolean[m.length][m[0].length];
// Copy over all of the matrix elements.
for (int i = 0; i < m.length; i++) {
for (int j = 0; j < m[i].length; j++) {
newM[i][j] = m[i][j];
}
}
// Return the new matrix object.
return newM;
}
```

After you’ve completed this step, it’s now time to implement the ** recursive** DFS search algorithm to look for the word of interest

`SEARCH_WORD`

in the `char[][]`

matrix. You should complete this in the `search()`

function in `Main.java`

. But first, a couple of things to keep in mind:- The
`boolean[][]`

input matrix`visited`

should keep track of whether the particular location in the character matrix has already been visited or not.`visited`

will change for the different paths that you explore through DFS, and so you will have to make a deep copy of the`visited`

matrix every time you call the function`seach()`

recursively (think about why this should be the case). This is where you should be using the`deepCopy()`

function you wrote in Problem 5 above. - Make sure that as you’re searching through the adjacent characters that you don’t exceed the bounds of the matrix. All of the characters in the matrix will have row and column indices between
`0`

and`BOARD_SIZE - 1`

inclusive. - To re-emphasize, we are implementing a
*recursive*DFS algorithm. The`path`

argument keeps track of the current`String`

that we’re “building up” by walking through the matrix, and the`int`

s`r`

and`c`

keep track of the current position we’re at in the`char[][]`

matrix. - We stated that there are sets of valid “moves” that we can make going from one character to another in the
`char[][]`

matrix. For this problem, we have represented these space of possible moves with the`int[]`

arrays`rowMoves`

and`colMoves`

. For a move to be valid, our row index must have increased by`rowMoves[i]`

and our column index by`colMoves[i]`

, where`i`

is any number between`0`

and`7`

inclusive.

**Problem 6:** Implement the DFS search function `search()`

now.

*Hover here to see the solution.*

```
public static boolean search(String path,
int r,
int c,
boolean[][] visited)
{
// Mark the current node we're at as visited.
visited[r][c] = true;
// Concatenate the character we're at to the working String.
path = path + Character.toString(board[r][c]);
// If we find the String we're looking for, then done recursing.
if (path.equals(SEARCH_WORD)) {
return true;
}
// If we've looked through enough characters and still haven't found
// the word, then we're also done recursing. This happens when either
// (1) we've looked through more characters than the actual length
// of the word, or (2) we've looked through all of the characters in
// the char[][] word search board.
else if (path.length() >= SEARCH_WORD.length() ||
path.length() >= BOARD_SIZE * BOARD_SIZE)
{
return false;
}
// Boolean to keep track of whether we found the word yet.
boolean valid = false;
// Look through all of the valid moves
for (int i = 0; i < rowMoves.length; i++) {
int newR = r + rowMoves[i];
int newC = c + colMoves[i];
if (newR < BOARD_SIZE && newR > -1 &&
newC < BOARD_SIZE && newC > -1 &&
!visited[newR][newC])
{
// Return whether any of the valid moves lead to paths
// that give the String we're looking for.
valid = valid || search(path, newR, newC, deepCopy(visited));
}
}
return valid;
}
```

That’s it! All that’s left is to run our code and see if it works as expected. We have already provided the driver code in the `main()`

function in `Main.java`

. A sample test word search board and search word is provided. If you run the code, you should expect to see the following result:

```
The word (dean) was found in the word search board.
```

Feel free to try running the code again with other `char[][]`

boards and/or `SEARCH_WORDS`

to verify that the program works as expected. Once you have verified that your program works as expected, consider the following two challenge problems (which are completely optional).

**Challenge 3:**Can you print out*all*of the English words that are found in the`char[][]`

matrix? Use the`dictionary.txt`

list of words as the set of all English words that you should consider.**Challenge 4:**Often times in an actual word search puzzle, one must find words that contain characters only going in “one direcion”. This means that all of the characters that make up a word can only go along one vertical line, horizontal line, or diagonal line. Modify your code to conform to this rule.