Is there is a algorithm to solve a special maze problem?(NOT Shortest path)

Question

I'd like to ask you a question about the maze There is a maze like

1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 0 1 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 1
1 0 1 0 1 0 1 1 1 0 1 1 1 0 1 1 1 1 1 0 1
1 0 0 0 1 0 0 0 1 0 1 2 1 0 0 0 1 0 0 0 1
1 1 1 1 1 1 1 0 1 0 1 0 1 1 1 0 1 1 1 0 1
1 0 0 0 0 2 1 0 0 0 1 0 0 0 0 0 0 0 1 0 1
1 0 1 1 1 1 1 0 1 0 1 1 1 1 1 0 1 0 1 0 1
1 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 1
1 0 1 0 1 0 1 1 1 0 1 0 1 0 1 1 1 1 1 0 1
1 0 0 0 1 0 1 2 1 0 1 0 1 0 1 2 0 0 0 0 1
1 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 1
1 0 0 0 0 2 1 0 1 0 1 0 1 2 1 0 1 0 0 0 1
1 0 1 1 1 1 1 0 1 0 1 0 1 1 1 0 1 0 1 0 1
1 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 1
1 0 1 0 1 0 1 1 1 1 1 0 1 0 1 1 1 1 1 0 1
1 0 1 0 0 0 0 0 0 0 1 0 0 0 1 2 0 0 0 0 1
1 0 1 1 1 0 1 1 1 0 1 0 1 0 1 1 1 1 1 1 1
1 0 0 0 1 0 0 0 1 2 1 0 1 0 0 0 1 0 0 0 1
1 0 1 1 1 1 1 0 1 1 1 0 1 1 1 0 1 0 1 0 1
1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 1 0 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1

The start is (0,1)and The end is (20,19) The number 1 represents the wall, the number 0 represents the path, and the number 2 represents the treasure. There must be a path between treasures What I want to do is start at the entrance, go through all the treasures and leave at the exit, hoping to find the shortest path, and record the order of the shortest path and the treasure traversal

I have tried the following code, but this code does not consider the treasure traversal order, but in a fixed traversal order, so I think it is wrong

import heapq


DIRECTIONS = [(0, 1), (0, -1), (1, 0), (-1, 0)]

def heuristic(a, b):

    return abs(a[0] - b[0]) + abs(a[1] - b[1])

def a_star_search(graph, start, end):
    frontier = []
    heapq.heappush(frontier, (0, start))
    came_from = {}
    cost_so_far = {}
    came_from[start] = None
    cost_so_far[start] = 0

    while frontier:
        current = heapq.heappop(frontier)[1]

        if current == end:
            break

        for dx, dy in DIRECTIONS:
            next_node = (current[0] + dx, current[1] + dy)
            if (0 <= next_node[0] < len(graph) and 0 <= next_node[1] < len(graph[0]) and
                graph[next_node[0]][next_node[1]] != 1):
                new_cost = cost_so_far[current] + 1
                if next_node not in cost_so_far or new_cost < cost_so_far[next_node]:
                    cost_so_far[next_node] = new_cost
                    priority = new_cost + heuristic(end, next_node)
                    heapq.heappush(frontier, (priority, next_node))
                    came_from[next_node] = current

    path = []
    while current is not None:
        path.append(current)
        current = came_from[current]
    path.reverse()

    return path
def write_list_to_file(lst, filename):
    with open(filename, 'w') as file:
        for row in lst:
            file.write(' '.join(str(element) for element in row))
            file.write('\n')


def read_list_from_file(filename):
    lst = []
    with open(filename, 'r') as file:
        for line in file:
            row = [int(element) for element in line.strip().split()]
            lst.append(row)
    return lst


graph = read_list_from_file('output.txt')


targets = [(i, j) for i, row in enumerate(graph) for j, cell in enumerate(row) if cell == 2]
write_list_to_file(targets,'target.txt')


start = (0, 1)
path = []
for end in targets:
    path.extend(a_star_search(graph, start, end)[:-1])
    start = end
path.extend(a_star_search(graph, start, (20, 19)))
print(path)
write_list_to_file(path,'pathalgorithm.txt')

My problem is not similar on the website, because I still need to consider the impact of the wall, so I hope to get your help

A day later I have tried to solve this problem, and I would like to ask everyone to help me check whether it is correct

def write_list_to_file(lst, filename):
    with open(filename, 'w') as file:
        for row in lst:
            file.write(' '.join(str(element) for element in row))
            file.write('\n')


def read_list_from_file(filename):
    lst = []
    with open(filename, 'r') as file:
        for line in file:
            row = [int(element) for element in line.strip().split()]
            lst.append(row)
    return lst


def heuristic(a, b):
    return abs(a[0] - b[0]) + abs(a[1] - b[1])

def a_star_search(maze, start, end):
    queue = [(0, start, [], 0)]
    heapq.heapify(queue)
    visited = set()

    while queue:
        _, current, path, cost = heapq.heappop(queue)
        if current == end:
            return path + [end]

        if current in visited:
            continue
        visited.add(current)

        for dx, dy in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
            x, y = current[0] + dx, current[1] + dy
            if 0 <= x < len(maze) and 0 <= y < len(maze[0]) and maze[x][y] != 1:
                heapq.heappush(queue, (cost + heuristic((x, y), end), (x, y), path + [current], cost + 1))

    return None

def find_shortest_path(maze, start, end, treasures):
    all_points = [start] + treasures + [end]
    shortest_paths = {(a, b): a_star_search(maze, a, b) for a in all_points for b in all_points if a != b}

    min_distance = float("inf")
    min_path = None
    for treasure_order in permutations(treasures):
        total_distance = 0
        path = [start]
        for i in range(len(treasure_order)):
            if i == 0:
                a, b = start, treasure_order[i]
            else:
                a, b = treasure_order[i-1], treasure_order[i]
            total_distance += len(shortest_paths[(a, b)]) - 1
            path.extend(shortest_paths[(a, b)][1:])

        total_distance += len(shortest_paths[(treasure_order[-1], end)]) - 1
        path.extend(shortest_paths[(treasure_order[-1], end)][1:])

        if total_distance < min_distance:
            min_distance = total_distance
            min_path = path

    return min_path, min_distance

maze = read_list_from_file('output.txt')
start = (0, 1)
end = (20, 19)
treasures = [(x, y) for x in range(len(maze)) for y in range(len(maze[0])) if maze[x][y] == 2]

shortest_path, shortest_distance = find_shortest_path(maze, start, end, treasures)

print("Shortest path:", shortest_path)
print("Shortest distance:", shortest_distance)

treasures_order=[]
for path in shortest_path:
    if path in treasures or path ==start or path == end:
        treasures_order.append(path)
print(treasures_order)
write_list_to_file(shortest_path,'path3.txt')

The result is shortest_path

and the shortest_distance is 178 The traversal order of the treasure is

[(0, 1), (5, 5), (11, 5), (17, 9), (9, 7), (11, 13), (3, 11), (9, 15), (15, 15), (20, 19)]

I am not sure if this is the shortest path, so I still hope you can teach me,I would appreciate very much.

new question

I suddenly thought of a new question, I now do not want the shortest total path, but want to make the least number of turns, that is, as far as possible to take the shape of 'Z', please do you have any good suggestions

This is an exact duplicate of your previous question: [Is there is a algorithm to solve a special maze problem?](https://stackoverflow.com/questions/76628947/is-there-is-a-algorithm-to-solve-a-special-maze-problem) — beaker, Jul 09 '23 at 14:30
Hello, this problem is completely different from the previous problem, where I asked for the minimum number of turns — Ethereal, Jul 10 '23 at 01:24

score 1 · Answer 1 · answered Jul 09 '23 at 05:27

This is a really interesting problem, so I would try to write something up if I had more time, but unfortunately I don't so I'll just give you my thoughts.

While my first idea was to just find the shortest path from treasure to treasure and try all the permutations (as you do in your solution if I understood correctly), this can easily get out of hand as you have more treasures because the amount of permutations and distance checking you need to perform goes up factorially - O(n!*n). A more efficient approach would be to treat the treasures as checkpoints along pure shortest path. There are some pretty good thoughts on this idea in this post.

What I think would be a good way of approaching the problem would be something like this:

Find the pure shortest path (without any treasure), let's call it PSP
Put the "player" at the starting point (i know you don't mention a player, this is just for sake of explanation)
Find the closest treasure to the player
find the shortest path from the PSP to the treasure (plus the path needed to return to the PSP if the player is not currently at the PSP)
find the shortest path from the player to the treasure
pick the shortest of two options
move the player through the path (so now it is at the endpoint of the path, aka the treasure)
repeat steps 3-7 until all treasures have been visited
find the shortest path from player to exit

Overall this should scale relatively well for larger mazes. In addition, you could also try to recalculate the PSP after every movement, which could improve performance in some cases. Keep in mind, however, that this method might not find the ABSOLUTE shortest path in some cases, but should always be fairly close. As with any algorithm problem, you often trade accuracy for performance. So the permutation solution is more accurate, but this should be faster.

Hope this helps!

Alain T. · Accepted Answer · 2023-07-09T15:52:10.700

You could approach this in two steps:

determine the shortest path between every points of interest forming a network of path segments
find the permutation of treasure that minimizes the total path combining the path segments, .

By using the point-to-point shortest path segments, the complete path is allowed to double-back and overlap paths.

Here is an example:

Setup:

mazeStr= """1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 0 1 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 1
1 0 1 0 1 0 1 1 1 0 1 1 1 0 1 1 1 1 1 0 1
1 0 0 0 1 0 0 0 1 0 1 2 1 0 0 0 1 0 0 0 1
1 1 1 1 1 1 1 0 1 0 1 0 1 1 1 0 1 1 1 0 1
1 0 0 0 0 2 1 0 0 0 1 0 0 0 0 0 0 0 1 0 1
1 0 1 1 1 1 1 0 1 0 1 1 1 1 1 0 1 0 1 0 1
1 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 1
1 0 1 0 1 0 1 1 1 0 1 0 1 0 1 1 1 1 1 0 1
1 0 0 0 1 0 1 2 1 0 1 0 1 0 1 2 0 0 0 0 1
1 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 1
1 0 0 0 0 2 1 0 1 0 1 0 1 2 1 0 1 0 0 0 1
1 0 1 1 1 1 1 0 1 0 1 0 1 1 1 0 1 0 1 0 1
1 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 1
1 0 1 0 1 0 1 1 1 1 1 0 1 0 1 1 1 1 1 0 1
1 0 1 0 0 0 0 0 0 0 1 0 0 0 1 2 0 0 0 0 1
1 0 1 1 1 0 1 1 1 0 1 0 1 0 1 1 1 1 1 1 1
1 0 0 0 1 0 0 0 1 2 1 0 1 0 0 0 1 0 0 0 1
1 0 1 1 1 1 1 0 1 1 1 0 1 1 1 0 1 0 1 0 1
1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 1 0 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1"""

maze      = [ [int(p) for p in line.split()] for line in mazeStr.split("\n")]
maze      = [ row+[1] for row in maze ] +[[1]*len(maze[0])]
treasures = [ (r,c) for r,row in enumerate(maze)
                    for c,v in enumerate(row) if v == 2 ]
start     = (0,1)
finish    = (20,19)

An extra column and an extra row of 1s is added to the maze in order to make the movement validations simpler to implement

To simulate the moves, you will need a function that returns the available neighbors of a given position:

def neighbors(R,C):
    return ((r,c) for r,c in [(R+1,C),(R-1,C),(R,C+1),(R,C-1)]
                  if maze[r][c] != 1)

To compare paths, you'll need a function that measures their "cost". Here is one that counts the number of turns (you could use len() if you only want the shortest distance):

def turnCount(path):
    return sum( (r0-r1) != (r1-r2) or (c0-c1) != (c1-c2)
                for (r0,c0),(r1,c1),(r2,c2) in zip(path,path[1:],path[2:]) )

The final path will be composed of subPaths (shortest) that go from start to treasure, between treasures and to the finish position. This function produces a dictionary of shortest paths to all points of interest (poi) from a given position. It does so by tracking a list of paths that grow without going to previously seen positions. When a path hits a point of interest, the output dictionary is updated, keeping only the shortest for each target position:

def findPaths(fromPos):
    poi   = dict()
    paths = [[fromPos]]
    seen  = {fromPos}
    while paths:
        prev,paths = paths,[]
        for path in prev:
            for (r,c) in neighbors(*path[-1]):
                if (r,c) in seen: continue
                paths.append([*path,(r,c)])
                if maze[r][c] == 0: continue
                if (r,c) not in poi \
                or turnCount(paths[-1])<turnCount(poi[r,c]):
                    poi[r,c] = paths[-1]
        seen.update(path[-1] for path in paths)
    return { f:p[1:] for f,p in poi.items() } # exclude starting point

The main logic first builds a dictionary of links from all relevant positions (start, finish and treasures). It then checks every permutation of treasures traversal order to determine the shortest complete path (from start, going through all treasures and reaching finish):

from itertools import permutations
links     = { pos:findPaths(pos) for pos in [start,finish,*treasures] }
bestPath  = []
bestTurns = None
for order in permutations(treasures):
    path  = [start]
    for t in order:
        path += links[path[-1]][t]
    path += links[finish][path[-1]][-2::-1]+[finish]
    turns = turnCount(path)
    if not bestPath or turns<bestTurns:
        bestPath,bestTurns = path,turns

For the final segment of the trajectory, the path is computed from the finish position so it needs to be inverted and exclude the last treasure position

output (expressed as Up/Down/Left/Right movements for brevity):

r0,c0 = start
for r,c in bestPath[1:]:
    if r<r0:print("U",end="")
    if r>r0:print("D",end="")
    if c<c0:print("L",end="")
    if c>c0:print("R",end="")
    if maze[r][c]==2: print(" Treasure at",(r,c))
    r0,c0 = r,c
print(" <Exit>")

DDDRRUURRDDRRDDDDLLLLDDLLUUUURRRR Treasure at (5, 5)
LLLLDDDDRRDDRR Treasure at (11, 5)
LLLLDDRRDDRRRRRRDD Treasure at (17, 9)
UULLLLUURRUUUU Treasure at (9, 7)
DDDDRRUUUUUURRRRDDDD Treasure at (11, 13)
UUUURRUULLLLUU Treasure at (3, 11)
DDRRRRRRDDRRDDLLLL Treasure at (9, 15)
RRDDRRDDDDLLLL Treasure at (15, 15)
RRRRUUUULLDDLLLLDDDDRRDDRRUURRDDD <Exit>

The complete path (bestPath) is:

[(0, 1), (1, 1), (2, 1), (3, 1), (3, 2), (3, 3), (2, 3), (1, 3), (1, 4), (1, 5), (2, 5), (3, 5), (3, 6), (3, 7), (4, 7), (5, 7), (6, 7), (7, 7), (7, 6), (7, 5), (7, 4), (7, 3), (8, 3), (9, 3), (9, 2), (9, 1), (8, 1), (7, 1), (6, 1), (5, 1), (5, 2), (5, 3), (5, 4), (5, 5), (5, 4), (5, 3), (5, 2), (5, 1), (6, 1), (7, 1), (8, 1), (9, 1), (9, 2), (9, 3), (10, 3), (11, 3), (11, 4), (11, 5), (11, 4), (11, 3), (11, 2), (11, 1), (12, 1), (13, 1), (13, 2), (13, 3), (14, 3), (15, 3), (15, 4), (15, 5), (15, 6), (15, 7), (15, 8), (15, 9), (16, 9), (17, 9), (16, 9), (15, 9), (15, 8), (15, 7), (15, 6), (15, 5), (14, 5), (13, 5), (13, 6), (13, 7), (12, 7), (11, 7), (10, 7), (9, 7), (10, 7), (11, 7), (12, 7), (13, 7), (13, 8), (13, 9), (12, 9), (11, 9), (10, 9), (9, 9), (8, 9), (7, 9), (7, 10), (7, 11), (7, 12), (7, 13), (8, 13), (9, 13), (10, 13), (11, 13), (10, 13), (9, 13), (8, 13), (7, 13), (7, 14), (7, 15), (6, 15), (5, 15), (5, 14), (5, 13), (5, 12), (5, 11), (4, 11), (3, 11), (4, 11), (5, 11), (5, 12), (5, 13), (5, 14), (5, 15), (5, 16), (5, 17), (6, 17), (7, 17), (7, 18), (7, 19), (8, 19), (9, 19), (9, 18), (9, 17), (9, 16), (9, 15), (9, 16), (9, 17), (10, 17), (11, 17), (11, 18), (11, 19), (12, 19), (13, 19), (14, 19), (15, 19), (15, 18), (15, 17), (15, 16), (15, 15), (15, 16), (15, 17), (15, 18), (15, 19), (14, 19), (13, 19), (12, 19), (11, 19), (11, 18), (11, 17), (12, 17), (13, 17), (13, 16), (13, 15), (13, 14), (13, 13), (14, 13), (15, 13), (16, 13), (17, 13), (17, 14), (17, 15), (18, 15), (19, 15), (19, 16), (19, 17), (18, 17), (17, 17), (17, 18), (17, 19), (18, 19), (19, 19), (20, 19)]

Note1: Because of the "turnCount" costing method, this logic is not perfect as there could be multiple "shortest paths" between points of interest that start or end in a direction that could add a turn to the complete path. These alternate shortest paths are not taken into account so there could be cases where an even shorter path is possible. If the cost was merely the length (distance) this would not be an issue. In this case both calculations produce the same result (178 moves) but depending on the maze pattern, counting turns and counting distance may produce different shortest paths.

Note2: Using permutations is a brute force approach that will exponentially take more time as you increase the number of treasures. there are more advanced techniques to find the optimal combination of paths more efficiently (e.g. dynamic programming, A*)

Is there is a algorithm to solve a special maze problem?(NOT Shortest path)

new question

2 Answers2