Problem Solving with Algorithms and Data Structures using Kotlin 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.

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.

As we did in Section 10.9, we will wrap our solution inside of a class so that we can keep track of some information in instance variables. The KnightTourSolver class maintains a single instance variable named tourPath, which tracks the tour in-progress as it is being constructed. The ordering of the items in the path is critical for our solution, so typically we would use a list for this purpose, but we also want to be able to look to see whether a vertex has already been visited. Looking up a vertex in a list would take \(O(n)\) time, so we instead use a set. This works great, but at the end of the algorithm, we need to have the items in the order that they were added to the set. For many set implementations this would be problematic. In Kotlin, however, when we iterate over a set in Kotlin via mutableSetOf, we are in fact guaranteed to visit items in the order that they were added.

The constructor for the KnightTourSolver class shown in Listing 10.13.1 takes three parameters: the graph, the vertex in the graph we wish to explore; and limit, the number of nodes in the path we hope to find. The instance variable tourPath is initialized, and then the init method starts the knightTour method.

The knightTour method is recursive. When the knightTour function is called, it adds the new vertex, then checks the base case condition. If we have a path that contains the complete number of vertices, we return 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. If at any point a recursive call returns false, indicating that no tour could be found, the loop continues trying alternative neighbors. If all neighbors fail, then no tour can be found from the current path. The vertex most recently added is removed, and the function returns false.

class KnightTourSolver(val graph: GraphADT<Int>,
                       val startVertex: Int,
                       val limit: Int) {
    val tourPath = mutableSetOf<Int>()

    init {
        knightTour(startVertex)
    }

    private fun knightTour(newVertex: Int): Boolean {

        tourPath.add(newVertex)

        if (tourPath.count() == limit) {     // found a tour
            return true
        } else {
            // Try each neighbor
            val neighbors = graph.getNeighbors(newVertex)!!   // We know every node has a neighbor
            for (neighbor in neighbors) {
                if (neighbor !in tourPath) {
                    val done = knightTour(neighbor)
                    if (done) {
                        return true
                    }
                }
            }

            // If got to here, no tour found; remove current and return false
            tourPath.remove(newVertex)
            return false
        }
    }
}

DFS backtracks if all neighbors of a particular vertex have been explored and we have not yet reached our goal limit. Specifically, backtracking happens when we return from knightTour with a status of False. In 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 30, we remain inside the while loop and look at the next vertex in neighbors.

Let’s look at a simple example of knightTour (Listing 10.13.1) in action. You can refer to the figures below to follow the steps of the search. Unvisited vertices are colored white, and visited vertices are colored gray. For this example we will assume that the call to the getNeighbors method on line 24 happens to order the nodes in alphabetical order, but there’s no such guarantee in practice. We begin by calling knightTour(A) (in this visual example, nodes are letters, not numbers).

knightTour starts with node A in Figure 10.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 10.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 10.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 10.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 10.13.6). From vertex D on, knightTour can continue to make recursive calls until we get to node C again (see Figure 10.13.7, Figure 10.13.8, and Figure 10.13.9). However, this time when we get to node C the test tourPath.count() == limit succeeds, 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. It will have the [A, B, D, E, F, C], which is the order we need to traverse the graph to visit each node exactly once.

Figure 10.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.

Here is a program to test the Knight’s Tour code. (It returns an alternate solution than the one in the above diagram.) It shows the path on the first line, and then prints out a chess board with the number of each location for reference.