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?
Complementary to Jon's excellent answer, here's another version that's closer to your original code, so you see that exactly was the problem:
def knightTour(current, limit, path):
path.append(current) # add current before returning, or the last
if len(path) == limit: # node will be missing in the returned path
return path
# (no need to check length)
for i in graph[current]:
if i not in path: # (no point in creating a set in each iteration)
tour = knightTour(i, limit, path)
if tour: # only return the path if it is not None, i.e.
return tour # if the recusion was succesful (backtracking)
else:
path.pop() # (use implicit return None)
Called as knightTour(0, 25, []), the result is [0, 11, 2, 9, 12, 1, 8, 19, 22, 13, 4, 7, 10, 21, 18, 17, 6, 3, 14, 23, 16, 5, 15, 20, 24]