CODEWITHSUNDEEP
pythonalgorithmrecursionknights-tour
Salvador Dali
Salvador Dali

Reputation: 222969

What am I missing in DFS in knight tour?

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?

Upvotes: 4

Views: 887

Answers (2)

tobias_k
tobias_k

Reputation: 82949

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]

Upvotes: 3

jonrsharpe
jonrsharpe

Reputation: 122151

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.

Upvotes: 4

Related Questions