Problem Solving with Algorithms and Data Structures using Kotlin 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 nearly instantly on a reasonably fast computer. But what happens if you try a much larger board? The program could slow down considerably. 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 10.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 10.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.

The knight’s tour code that we have written takes a very long time to run on a \(9 \times 9\) board. (We got bored waiting, and just stopped it before it finished.) Luckily there is a way to speed up the code further so that the \(9 \times 9\) case (and much bigger) run in under one second. In the Listing 10.14.3 we show the code that speeds up the knightTour. This method, called orderByAvail, will be used in place of the call to graph.getNeighbors at line 16 in Section 10.13. The critical line in the orderByAvail method is line 24. 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 changing sortedBy to sortedByDescending.

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.

private fun orderByAvail(start: Int): List<Int> {
    data class CountAndVertex(val count: Int, val vertex: Int)
    val availCount = mutableListOf<CountAndVertex>()
    val startNeighbors = graph.getNeighbors(start)
    if (startNeighbors == null) { // no neighbors at all
        return listOf()
    }
    for (v in startNeighbors) {
        if (v !in tourPath) {   // v is not already visited
            var count = 0
            val vNeighbors = graph.getNeighbors(v)
            if (vNeighbors != null) {
                for (w in vNeighbors) {
                    if (w !in tourPath) {
                        count += 1
                    }
                }
            }
            availCount.add(CountAndVertex(count, v))
        }
    }

    // Sort availCount by count
    val sortedCount = availCount.sortedBy { countAndVertex -> countAndVertex.count }

    // Return list consisting of just the vertices in the list
    return sortedCount.map { countAndVertex -> countAndVertex.vertex }
}

The preceding method has to keep track of a vertex and its count of unvisited neighbors as a pair of values. We used a data class to represent the pair, and then created a list of them. In line 24, we used the list method sortedBy, which sorts the list. The catch is that it is a list of CountAndVertex objects, which are not Comparable, so Kotlin doesn’t know what it means for one item to be greater or less than another. We resolve that my supplying sortedBy with a brief inline function indicating how to sort the data. The syntax

{ countAndVertex -> countAndVertex.count }

creates an unnamed function that sortedBy uses whenever it needs to know the value of a countAndVertex object for sorting purposes. This unnamed function takes one parameter, which is a CountAndVertex object, and it returns the value of the count variable within the object.

In line 27, we then wish to return just the list of vertices that have now been sorted; we don’t need the counts anymore. The Kotlin method map returns a new list by applying a supplied function to each item in the starting list. In this case, we have another small inline function. This one again takes a CountAndVertex object, and returns the vertex.

These small inline functions are for historical reasons referred to as lambda expressions.