Knight's tour

The knight’s tour puzzle is played on a chess board with a single chess piece, the knight.

The object of the puzzle is to find a sequence of moves that allow the knight to visit every square on the board exactly once.

Solve with graph

• represent the legal moves of a knight on a chessboard as a graph
• use a graph algorithm to find a path of length rows * cols - 1

Build the Graph

DFS

• stack

To speed up, always pick the vertex to go next that has the fewest available moves.

General DFS

O(V+E)

class DFSGraph(Graph):
    def __init__(self):
        super().__init__()
        self.time = 0

    def dfs(self):
        for aVertex in self:
            aVertex.setColor('white')
            aVertex.setPred(-1)
        for aVertex in self:
            if aVertex.getColor() == 'white':
                self.dfsvisit(aVertex)

    def dfsvisit(self,startVertex):
        startVertex.setColor('gray')
        self.time += 1
        startVertex.setDiscovery(self.time)
        for nextVertex in startVertex.getConnections():
            if nextVertex.getColor() == 'white':
                nextVertex.setPred(startVertex)
                self.dfsvisit(nextVertex) # implicitly stack
        startVertex.setColor('black')
        self.time += 1
        startVertex.setFinish(self.time)