Solving the math puzzle of the Schönbrunn maze in Vienna

input

5 5
4 2
2 2
2 -2 4 -1 3
-3 3 -1 3 -2
1 -2 0 -2 3
-3 2 -3 2 -4
4 -2 1 -3 2

main.py

# read the input from a file
n, m = [int(c) for c in input().split(' ')]
sx, sy = [int(c) for c in input().split(' ')]
ex, ey = [int(c) for c in input().split(' ')]

# utilities to convert coordinates to vertex id and vice versa
def coord_to_id(i, j):
    return i * m + j

def id_to_coord(x):
    return (x // m, x % n)

# store the grid
g = [ [int(c) for c in input().split(' ')] for _ in range(n)]

# build the graph
graph = {}
for i in range(n):
    for j in range(m):
        # read how many steps can be taken
        steps = abs(g[i][j])
        if steps == 0:
            continue
        x = coord_to_id(i, j)
        # define the list of neighbors
        graph[x] = []
        # from the current tile x, jump "steps" tile up, left, down, right
        if i - steps >= 0:
            graph[x].append(coord_to_id(i-steps, j))
        if i + steps < n:
            graph[x].append(coord_to_id(i+steps, j))
        if j - steps >= 0:
            graph[x].append(coord_to_id(i, j-steps))
        if j + steps < m:
            graph[x].append(coord_to_id(i, j+steps))

start = coord_to_id(sx, sy)
end = coord_to_id(ex, ey)

# store all the solutions
paths = []
# backtrack a solution
prev = {}
visited = set()
prev[start] = None

# called dfs, but is actually a complete search
def dfs(u):
    if u == end:
        a = end
        p = []
        while a != None:
            p.append(a)
            a = prev[a]
        paths.append(p)
        return
    for v in graph[u]:
        if v not in visited:
            visited.add(v)
            prev[v] = u
            dfs(v)
            # complete search: pretend this path was not explored
            # to consider it later
            visited.remove(v)

# search
visited.add(start)
dfs(start)

# results
solutions = []
for p in paths:
    tiles = [id_to_coord(tile) for tile in p[::-1]]
    s = sum([g[x[0]][x[1]] for x in tiles])
    # log all the solutions
    solutions.append((s, len(tiles), tiles))

# find the best
best = min(solutions, key=lambda s: (abs(s[0]), s[1]))
print('The best solution is a sum of', best[0], 'in', best[1], 'steps.')
sol = ' -> '.join([str(c) + ', tile ' + str(g[c[0]][c[1]]) for c in best[2]])
print(sol)