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

There is one last interesting topic regarding the knight’s tour problem, then we will move on to the general version of the depth-first search. The topic is performance. In particular, knightTour is very sensitive to the method you use to select the next vertex to visit. For example, on a \(5 \times 5\) board you can produce a path in about 1.5 seconds on a reasonably fast computer. But what happens if you try an \(8 \times 8\) board? In this case, depending on the speed of your computer, you may have to wait up to a half hour to get the results! The reason for this is that the knight’s tour problem as we have implemented it so far is an exponential algorithm of size \(O(k^N)\text{,}\) where \(N\) is the number of squares on the chess board, and \(k\) is a small constant. Figure 7.14.1 can help us visualize why this is so. The root of the tree represents the starting point of the search. From there the algorithm generates and checks each of the possible moves the knight can make. As we have noted before, the number of moves possible depends on the position of the knight on the board. In the corners there are only two legal moves, on the squares adjacent to the corners there are three, and in the middle of the board there are eight. Figure 7.14.2 shows the number of moves possible for each position on a board. At the next level of the tree there are once again between two and eight possible next moves from the position we are currently exploring. The number of possible positions to examine corresponds to the number of nodes in the search tree.

We have already seen that the number of nodes in a binary tree of height \(N\) is \(2^{N+1}-1\text{.}\) For a tree with nodes that may have up to eight children instead of two, the number of nodes is much larger. Because the branching factor of each node is variable, we could estimate the number of nodes using an average branching factor. The important thing to note is that this algorithm is exponential: \(k^{N+1}-1\text{,}\) where \(k\) is the average branching factor for the board. Let’s look at how rapidly this grows! For a board that is \(5 \times 5\) the tree will be 25 levels deep, or \(N = 24\) counting the first level as level 0. The average branching factor is \(k = 3.8\) so the number of nodes in the search tree is \(3.8^{25}-1\) or \(3.12 \times 10^{14}\text{.}\) For a \(6 \times 6\) board, \(k = 4.4\text{,}\) there are \(1.5 \times 10^{23}\) nodes, and for a regular \(8 \times 8\) chess board, \(k = 5.25\text{,}\) there are \(1.3 \times 10^{46}\text{.}\) Of course, since there are multiple solutions to the problem we won’t have to explore every single node, but the fractional part of the nodes we do have to explore is just a constant multiplier which does not change the exponential nature of the problem. We will leave it as an exercise for you to see if you can express \(k\) as a function of the board size.

Luckily there is a way to speed up the \(8 \times 8\) case so that it runs in under one second. In the Listing 7.14.3 we show the code that speeds up the knightTour. This method, called orderByAvail, will be used in place of the call to vertex.getNeighbors at lines 9–11 in Section 7.13. The critical line in the orderByAvail method is line 15. This line ensures that we select the vertex that has the fewest available moves to go next. You might think this is really counterproductive; why not select the node that has the most available moves? You can try that approach easily by running the program yourself and inserting the line Collections.reverse(sortList) right after the sort.

The problem with using the vertex with the most available moves as your next vertex on the path is that it tends to have the knight visit the middle squares early on in the tour. When this happens it is easy for the knight to get stranded on one side of the board where it cannot reach unvisited squares on the other side of the board. On the other hand, visiting the squares with the fewest available moves first pushes the knight to visit the squares around the edges of the board first. This ensures that the knight will visit the hard-to-reach corners early and can use the middle squares to hop across the board only when necessary.

Utilizing this kind of knowledge to speed up an algorithm is called a heuristic. Humans use heuristics every day to help make decisions, and heuristic searches are often used in the field of artificial intelligence. This particular heuristic is called Warnsdorff’s algorithm, named after H. C. von Warnsdorff who published his idea in 1823.

public static ArrayList<Vertex<Integer>> orderByAvail(
  Vertex<Integer> start) {
    ArrayList<CountAndVertex<Integer>> sortList = new ArrayList<>();
    for (Vertex<Integer> v: start.getNeighbors()) {
        if (v.color == VertexColor.WHITE) {
            int count = 0;
            for (Vertex<Integer> w: v.getNeighbors()) {
                if (w.color == VertexColor.WHITE) {
                    count = count + 1;
                }
            }
            sortList.add(new CountAndVertex<Integer>(count, v));
        }
    }
    Collections.sort(sortList);
    ArrayList<Vertex<Integer>> resultList = new ArrayList<>();
    for (CountAndVertex<Integer> pair: sortList) {
        resultList.add(pair.vertex);
    }
    return resultList;
}

The preceding method has to keep track of a vertex and its count of unvisited neighbors as a pair of values. Since Java doesn’t allow us to make an array with heterogeneous types, we need to create a class for this pair; Listing 7.14.4 shows the code for this CountAndVertex class. Its compareTo method uses subtraction to return a negative value when this.count is less than other.count, zero when they are equal, and a positive number when this.count is greater than other.count.

class CountAndVertex<T extends Comparable<T>>
    implements Comparable<CountAndVertex<T>> {
    int count;
    Vertex<T> vertex;

    public CountAndVertex(int count, Vertex<T> vertex) {
        this.count = count;
        this.vertex = vertex;
    }

    public int compareTo(CountAndVertex other) {
        return (this.count - other.count);
    }
}