Problem Solving with Algorithms and Data Structures using Java: The Interactive Edition

The search algorithm we will use to solve the knight’s tour problem is called depth-first search (DFS). Whereas the breadth-first search algorithm builds a search tree one level at a time, a depth-first search creates a search tree by exploring one branch of the tree as deeply as possible. In this section we will look at two algorithms that implement a depth-first search. The first algorithm we will look at specifically solves the knight’s tour problem by explicitly forbidding a node to be visited more than once. The second implementation is more general, but allows nodes to be visited more than once as the tree is constructed. The second version is used in subsequent sections to develop additional graph algorithms.

The depth-first exploration of the graph is exactly what we need in order to find a path through 64 vertices (one for each square on the chessboard) and 63 edges. We will see that when the depth-first search algorithm finds a dead end (a place in the graph where there are no more moves possible) it backs up the tree to the next deepest vertex that allows it to make a legal move.

The knightTour function shown in Listing 7.13.1 takes four parameters: the currentDepth in the search tree; path, a list of vertices visited up to this point; vertex, the vertex in the graph we wish to explore; and limit, the number of nodes in the path. The knightTour function is recursive. When the knightTour function is called, it first checks the base case condition. If we have a path that contains 64 vertices, we return from knightTour with a status of true, indicating that we have found a successful tour. If the path is not long enough, we continue to explore one level deeper by choosing a new vertex to explore and calling knightTour recursively for that vertex.

public static boolean knightTour(int currentDepth,
    ArrayList<Vertex<Integer>> path,
    Vertex<Integer> vertex, int nodesInPath) {
    boolean done;

    vertex.color = VertexColor.GRAY;
    path.add(vertex);

    if (currentDepth < nodesInPath) {
        ArrayList<Vertex<Integer>> neighbors =
          new ArrayList<>(vertex.getNeighbors());
        Collections.sort(neighbors);
        int i = 0;
        done = false;
        while (i < neighbors.size() && !done) {
            if (neighbors.get(i).color == VertexColor.WHITE) {
                done = knightTour(currentDepth + 1, path,
                    neighbors.get(i), nodesInPath);
            }
            i = i + 1;
            nIterations++;
        }
        if (!done) { // prepare to backtrack
            path.remove(path.size() - 1);
            vertex.setColor(VertexColor.WHITE);
        }
    } else {
        done = true;
    }
    return done;
}

DFS also uses colors to keep track of which vertices in the graph have been visited. Unvisited vertices are colored white, and visited vertices are colored gray. If all neighbors of a particular vertex have been explored and we have not yet reached our goal length of 64 vertices, we have reached a dead end and must backtrack. Backtracking happens when we return from knightTour with a status of false. In the breadth-first search we used a queue to keep track of which vertex to visit next. Since depth-first search is recursive, we are implicitly using a stack to help us with our backtracking. When we return from a call to knightTour with a status of false, in line 16, we remain inside the while loop and look at the next vertex in neighbors.

Let’s look at a simple example of knightTour (Listing 7.13.1) in action. You can refer to the figures below to follow the steps of the search. For this example we will assume that the call to the getNeighbors method on line 6 orders the nodes in alphabetical order. We begin by calling knightTour(0, path, A, 6) (where the path is initially empty).

knightTour starts with node A in Figure 7.13.2. The nodes adjacent to A are B and D. Since B is before D alphabetically, DFS selects B to expand next as shown in Figure 7.13.3. Exploring B happens when knightTour is called recursively. B is adjacent to C and D, so knightTour elects to explore C next. However, as you can see in Figure 7.13.4 node C is a dead end with no adjacent white nodes. At this point we change the color of node C back to white. The call to knightTour returns a value of False. The return from the recursive call effectively backtracks the search to vertex B (see Figure 7.13.5). The next vertex on the list to explore is vertex D, so knightTour makes a recursive call moving to node D (see Figure 7.13.6). From vertex D on, knightTour can continue to make recursive calls until we get to node C again (see Figure 7.13.7, Figure 7.13.8, and Figure 7.13.9). However, this time when we get to node C the test n < limit fails so we know that we have exhausted all the nodes in the graph. At this point we can return True to indicate that we have made a successful tour of the graph. When we return the list, path has the values [A, B, D, E, F, C], which is the order we need to traverse the graph to visit each node exactly once.

Figure 7.13.10 shows you what a complete tour around an \(8 \times 8\) board looks like. There are many possible tours; some are symmetric. With some modification you can make circular tours that start and end at the same square.