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.

chess-knight-1

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:

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

  1. 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?
  2. Which algorithm - BFS or DFS - is faster?
  3. 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:

word-search-dfs-1

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:

  1. 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.
  2. 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.
  3. 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 ints r and c keep track of the current position we’re at in the char[][] matrix.
  4. 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.