What am I missing in DFS in knight tour?

Question

I am trying to solve the knight tour problem using DFS. I generated my graph (in this example I have 5x5 matrix):

{
  0: set([11, 7]),
  1: set([8, 10, 12]),
  2: set([9, 11, 5, 13]),
  3: set([12, 14, 6]),
  4: set([13, 7]),
  5: set([16, 2, 12]), 6: set([17, 3, 13, 15]), 7: set([0, 4, 10, 14, 16, 18]), 8: set([19, 1, 11, 17]), 9: set([2, 12, 18]), 10: set([1, 17, 21, 7]), 11: set([0, 2, 8, 18, 20, 22]), 12: set([1, 3, 5, 9, 15, 19, 21, 23]), 13: set([2, 4, 6, 16, 22, 24]), 14: set([23, 17, 3, 7]), 15: set([12, 22, 6]), 16: set([23, 7, 5, 13]), 17: set([6, 8, 10, 14, 20, 24]), 18: set([9, 11, 21, 7]), 19: set([8, 12, 22]), 20: set([17, 11]), 21: set([10, 12, 18]), 
  22: set([19, 11, 13, 15]),
  23: set([16, 12, 14]),
  24: set([17, 13])
}

Then I am trying to invoke DFS to find the path that has the length of 25 (each square was reached). To do this I track the current path, compare it with a desired length and if it was not reached recursively span DFS from all the neighbors. If there are no unchecked neighbors (we reached the dead end but there are still squares that should be reached), I am removing the last element from the path.

def knightTour(current, limit, path):
    if len(path) == limit:
        return path

    path.append(current)

    neighbors = graph[current]
    if len(neighbors):
        for i in neighbors:
            if i not in set(path):
                return knightTour(i, limit, path)
    else:
        path.pop()
        return False

knightTour(0, 24, [])

I am missing something obvious because in my case it can not find the full path and got stuck with [0, 11, 2, 9, 12, 1, 8, 19, 22, 13, 4, 7, 10, 17, 6, 3, 14, 23, 16]. Any idea where is my mistake?

Answer 1

You aren't back-tracking, so your algorithm ends up stuck down a path that can't work (unless it lucks out and gets a result first time). Here is a slightly simpler implementation that works:

def knights_tour(graph, path=None):
    if path is None:
        path = [min(graph)]
    if len(path) == len(graph):
        return path
    visited = set(path)
    for neighbour in graph[path[-1]]:
        if neighbour not in visited:
            path.append(neighbour)
            if knights_tour(graph, path):
                return path
            path.pop()

Note that this only returns the path if the recursive call has returned truth-y (i.e. a complete path has been found), otherwise it removes that neighbour and continues to check the possible paths from the other neighbours.