Path finding in grid

Question

I trying to print all the paths in a mxm matrix which terminate if I visit an already visited node. I have tried a recursive solution but i am not sure how to handle the base case

def is_valid_move(x, y):
    return 0 <= x < m and 0 <= y < m
def find_paths(G, x, y, visited, path):
        visited.add((x, y))
        path.append((x, y))

        if len(visited) == m:
            return [path]# Print the path when all nodes are visited
        else:
            paths = []
            for dx, dy in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
                nx, ny = x + dx, y + dy
                if is_valid_move(nx, ny) and (nx, ny) not in visited:
                    new_paths = find_paths(G, nx, ny, set(visited), list(path))
                    paths.append(new_paths)

                if is_valid_move(nx, ny) and (nx, ny) in visited:
                    completed_path = [vertex for vertex in path]
                    paths.append(completed_path.append((nx, ny)))
            return paths

G = [['ghargh', 'drwtex', 'qdgeun'], ['xmhjkl', 'kmswji', 'cvjosd'], ['vbrmwq', 'fgdhey', 'eyuite']]
result_paths = find_paths(G, 0, 0, set(), [])

This code will give me paths which are of length m. But I also want paths which terminate earlier. For example if I start at (0,0) the following path should also be present in all the possible paths (0,0)->(0,1)->(0,2)->(1,2)->(2,2)->(2,1)->(1,1)->(0,0)

Answer 1

Your problem lies here:

if is_valid_move(nx, ny) and (nx, ny) in visited:
    completed_path = [vertex for vertex in path]
    paths.append(completed_path.append((nx, ny)))

First of all, there's no need to say [vertex for vertex in path]; that's just going to create a copy of path, so use path. Secondly, since (nx, ny) has already been visited, you shouldn't append it to completed_path (otherwise it wouldn't be a path). Finally, you should know that foo.append(bar) returns None in Python. Therefore, in the last line of the code block above, you're appending None to paths (and then returning paths after the if statement). The code block above should be changed as follows:

if is_valid_move(nx, ny) and (nx, ny) in visited:
    paths.append(path)