What algorithmic redundancies in my recursive pathfinding function are causing essentially infinite runtime?

Question

Usually when this kind of issue comes up, the answer is some sort of infinite loop. But I'm having trouble figuring out where that could have been introduced in my code.

Let's say we're dealing with a standard 8x8 chess board and I want to find the most efficient path from one square to another, say from red to green. The solution is 3 moves.

def calculate_dest(curr, path):
    return (curr[0] + path[0], curr[1] + path[1])

def curr_is_valid(curr):
    return 0 <= curr[0] <= 7 and 0 <= curr[1] <= 7

def helper(dest, soFar):
    # if len(soFar) > 4:
    #     return 63
    if not curr_is_valid(soFar[-1]):
        return 63
    elif soFar[-1] in soFar[:-1]:
        return 63
    elif soFar[-1] == dest:
        return len(soFar) - 1
    else:
        return min(helper(dest, soFar + [calculate_dest(soFar[-1], p)]) for p in [(2, 1),
                                                                                  (2, -1),
                                                                                  (-2, 1),
                                                                                  (-2, -1),
                                                                                  (1, 2),
                                                                                  (1, -2),
                                                                                  (-1, -2),
                                                                                  (-1, 2)])

dest: destination point represented as tuple (i.e. (0, 1))

soFar: record of all points traversed, represented as a list of tuples (i.e. [(0, 1), (1, 3)])

When I run the above code with the comments uncommented, helper((0, 1), [(0, 0)]) returns 3 like I expect in 2 seconds. Not great, but when I put the comments back in because the function is supposed to work for any number of moves around the board, it keeps running, basically forever (I tried waiting a few minutes but at that point you know something is wrong).

I'm pretty sure the base case soFar[-1] in soFar[:-1] should have taken care of paths that started recrossing, which would certainly then introduce an infinite loop, so I'm not sure then, why the function runs into an infinite-ish loop?

It's also possible that the way I have designed my function is fundamentally inefficient. My thinking was that recursion would be necessary in this case.

Answer 1

You want to do a BFS since it's guaranteed to return the shortest path.

Here's the code:

def is_valid(curr):
    return 0 <= curr[0] <= 7 and 0 <= curr[1] <= 7

def get_neighbors(cur):
    for offset in [(2, 1),
                    (2, -1),
                    (-2, 1),
                    (-2, -1),
                    (1, 2),
                    (1, -2),
                    (-1, -2),
                    (-1, 2)]:
        nxt = (cur[0] + offset[0], cur[1] + offset[1])
        if is_valid(nxt):
            yield nxt

def helper(start, dest):
    visited = set()
    q = [(start, 0)]
    while q:
        front, distance = q.pop(0)
        visited.add(front)
        if front == dest:
            return distance
        for neighbor in get_neighbors(front):
            if neighbor not in visited:
                q.append((neighbor, distance + 1))
print(helper((0, 0), (0, 1)))

Output:

3