maze.py

import copy
import os
import time

MAZE = [
    ["#", "#", "#", "#", "#"],
    [" ", " ", " ", "#", " "],
    [" ", "#", " ", "#", " "],
    [" ", " ", " ", " ", " "],
    ["E", "#", "#", "#", "#"],
]

MAZE = [
    [" ", " ", " ", "#", "#", "#", "#", "#", "#", "#", "#", "#", "#", "#", "#", "#", "#", "#", "#", "#", "#", "#", "#", "#", "#", "#", "#", "#", "#", "#", "#"],
    [" ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", "#"],
    ["#", "#", "#", "#", "#", "#", "#", "#", "#", "#", " ", " ", "#", "#", "#", "#", "#", "#", "#", "#", "#", "#", "#", "#", "#", " ", " ", "#", "#", "#", "#"],
    ["#", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", "#", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", "#"],
    ["#", "#", "#", "#", "#", "#", "#", "#", "#", "#", " ", " ", "#", "#", "#", "#", "#", "#", "#", "#", "#", "#", "#", "#", "#", " ", " ", "#", "#", "#", "#"],
    ["#", " ", " ", " ", " ", " ", " ", " ", " ", "#", " ", " ", "#", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", "#", " ", " ", "#", " ", " ", "#"],
    ["#", "#", "#", "#", " ", " ", "#", "#", "#", "#", " ", " ", "#", "#", "#", "#", " ", " ", "#", "#", "#", "#", " ", " ", "#", " ", " ", "#", " ", " ", "#"],
    ["#", " ", " ", "#", " ", " ", "#", " ", " ", " ", " ", " ", "#", " ", " ", " ", " ", " ", "#", " ", " ", "#", " ", " ", "#", " ", " ", " ", " ", " ", "#"],
    ["#", " ", " ", "#", " ", " ", "#", " ", " ", "#", " ", " ", "#", "#", "#", "#", " ", " ", "#", " ", " ", "#", "#", "#", "#", "#", "#", "#", " ", " ", "#"],
    ["#", " ", " ", " ", " ", " ", " ", " ", " ", "#", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", "#", " ", " ", " ", " ", " ", " ", " ", " ", "#"],
    ["#", " ", " ", "#", " ", " ", "#", " ", " ", "#", "#", "#", "#", "#", "#", "#", "#", "#", "#", "#", "#", "#", " ", " ", "#", "#", "#", "#", "#", "#", "#"],
    ["#", " ", " ", "#", " ", " ", "#", " ", " ", "#", " ", " ", " ", " ", " ", " ", " ", " ", "#", " ", " ", " ", " ", " ", "#", " ", " ", " ", " ", " ", "#"],
    ["#", " ", " ", "#", "#", "#", "#", "#", "#", "#", "#", "#", "#", "#", "#", "#", " ", " ", "#", "#", "#", "#", "#", "#", "#", " ", " ", "#", "#", "#", "#"],
    ["#", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", "#"],
    ["#", " ", " ", "#", "#", "#", "#", " ", " ", "#", "#", "#", "#", "#", "#", "#", "#", "#", "#", " ", " ", "#", "#", "#", "#", " ", " ", "#", " ", " ", "#"],
    ["#", " ", " ", "#", " ", " ", "#", " ", " ", "#", " ", " ", "#", " ", " ", " ", " ", " ", " ", " ", " ", "#", " ", " ", " ", " ", " ", "#", " ", " ", "#"],
    ["#", " ", " ", "#", " ", " ", "#", "#", "#", "#", " ", " ", "#", " ", " ", "#", "#", "#", "#", "#", "#", "#", "#", "#", "#", " ", " ", "#", " ", " ", "#"],
    ["#", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", "#", " ", " ", "#", " ", " ", " ", " ", " ", "#", " ", " ", "#", " ", " ", "#", " ", " ", "#"],
    ["#", " ", " ", "#", "#", "#", "#", "#", "#", "#", "#", "#", "#", " ", " ", "#", " ", " ", "#", "#", "#", "#", " ", " ", "#", "#", "#", "#", " ", " ", "#"],
    ["#", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", "#", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", "#", " ", " ", " ", "E", " ", "#"],
    ["#", "#", "#", "#", "#", "#", "#", "#", "#", "#", "#", "#", "#", "#", "#", "#", "#", "#", "#", "#", "#", "#", "#", "#", "#", "#", "#", "#", "#", "#", "#"],
]

MAZE = [
    [" ", "#", "#", "#", "#", "#", "#", "#", "#", "#", "#", "#", "#", "#", "#", "#", "#", "#", "#", "#", "#"],
    [" ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", "#", " ", "#", " ", " ", " ", "#", " ", "#"],
    ["#", " ", "#", " ", "#", " ", "#", " ", "#", " ", "#", " ", "#", " ", "#", " ", "#", " ", "#", " ", "#"],
    ["#", " ", "#", " ", "#", " ", "#", " ", "#", " ", "#", " ", "#", " ", "#", " ", "#", " ", "#", " ", "#"],
    ["#", "#", "#", "#", "#", "#", "#", "#", "#", " ", "#", "#", "#", " ", "#", " ", "#", " ", "#", " ", "#"],
    ["#", " ", " ", " ", "#", " ", " ", " ", " ", " ", " ", " ", "#", " ", " ", " ", "#", " ", "#", " ", "#"],
    ["#", "#", "#", " ", "#", "#", "#", " ", "#", "#", "#", " ", "#", " ", "#", " ", "#", "#", "#", " ", "#"],
    ["#", " ", "#", " ", " ", " ", " ", " ", " ", " ", "#", " ", "#", " ", "#", " ", "#", " ", "#", " ", "#"],
    ["#", " ", "#", " ", "#", "#", "#", " ", "#", " ", "#", "#", "#", " ", "#", " ", "#", " ", "#", " ", "#"],
    ["#", " ", " ", " ", " ", " ", "#", " ", "#", " ", " ", " ", "#", " ", "#", " ", "#", " ", "#", " ", "#"],
    ["#", " ", "#", "#", "#", "#", "#", " ", "#", "#", "#", "#", "#", " ", "#", " ", "#", " ", "#", " ", "#"],
    ["#", " ", " ", " ", "#", " ", " ", " ", " ", " ", " ", " ", " ", " ", "#", " ", "#", " ", "#", " ", "#"],
    ["#", "#", "#", " ", "#", " ", "#", "#", "#", "#", "#", " ", "#", " ", "#", "#", "#", " ", "#", " ", "#"],
    ["#", " ", " ", " ", "#", " ", " ", " ", "#", " ", "#", " ", "#", " ", "#", " ", "#", " ", " ", " ", "#"],
    ["#", "#", "#", " ", "#", "#", "#", " ", "#", " ", "#", "#", "#", " ", "#", " ", "#", "#", "#", " ", "#"],
    ["#", " ", " ", " ", "#", " ", " ", " ", " ", " ", "#", " ", " ", " ", " ", " ", " ", " ", "#", " ", "#"],
    ["#", "#", "#", " ", "#", "#", "#", " ", "#", " ", "#", "#", "#", " ", "#", "#", "#", " ", "#", " ", "#"],
    ["#", " ", " ", " ", "#", " ", "#", " ", "#", " ", " ", " ", "#", " ", "#", " ", "#", " ", " ", " ", "#"],
    ["#", " ", "#", " ", "#", " ", "#", "#", "#", " ", "#", " ", "#", " ", "#", " ", "#", " ", "#", "#", "#"],
    ["#", " ", "#", " ", "#", " ", " ", " ", " ", " ", "#", " ", " ", " ", "#", " ", " ", " ", " ", "E", "#"],
    ["#", "#", "#", "#", "#", "#", "#", "#", "#", "#", "#", "#", "#", "#", "#", "#", "#", "#", "#", "#", "#"],
]

def solve_maze(maze, start_row, start_column, solution):
    # print maze
    # os.system('clear')
    # for maze_row in maze:
    #     print("".join(maze_row))
    # print()

    # check if outside the maze
    try:
        maze[start_row][start_column]
    except IndexError:
        return False

    # check if wall
    if maze[start_row][start_column] == "#":
        return False

    # check if dead end or already checked
    if maze[start_row][start_column] == "." or maze[start_row][start_column] == "D":
        return False

    # check if exit
    if maze[start_row][start_column] == "E":
        maze[start_row][start_column] = "+"
        return solution

    # mark as checked
    maze[start_row][start_column] = "."

    # check all directions
    solutions = []
    solutions.append(solve_maze(copy.deepcopy(maze), start_row + 1, start_column, solution + ["DOWN"]))
    solutions.append(solve_maze(copy.deepcopy(maze), start_row - 1, start_column, solution + ["UP"]))
    solutions.append(solve_maze(copy.deepcopy(maze), start_row, start_column + 1, solution + ["RIGHT"]))
    solutions.append(solve_maze(copy.deepcopy(maze), start_row, start_column - 1, solution + ["LEFT"]))

    # filter all failed solutions and get the shortest one
    solutions_lists = [x for x in solutions if isinstance(x, list)]
    if solutions_lists:
        return min(solutions_lists, key=len)

    # mark as dead end
    maze[start_row][start_column] = "D"
    return False


def solve_maze_bfs(maze, start_row, start_column, solution):
    # https://en.wikipedia.org/wiki/Breadth-first_search
    # Breadth-First-Search( Maze m )
    #     EnQueue( m.StartNode )
    #     While Queue.NotEmpty
    #         c <- DeQueue
    #         If c is the goal
    #             Exit
    #         Else
    #             Foreach neighbor n of c
    #                 If n "Unvisited"
    #                     Mark n "Visited"
    #                     EnQueue( n )
    #             Mark c "Examined"
    # End procedure

    queue = [[start_row, start_column, solution]]

    while queue:
        # print maze
        # os.system('clear')
        # for maze_row in maze:
        #     print("".join(maze_row))
        # print()

        # print queue
        # for queue_data in queue:
        #     print(queue_data)
        # print()

        # get next from the queue
        row, column, solution = queue.pop(0)

        # check if exit
        if maze[row][column] == "E":
            return solution

        # get all neighbors
        neighbors = [
            [1, 0, "DOWN"],
            [-1, 0, "UP"],
            [0, 1, "RIGHT"],
            [0, -1, "LEFT"]
        ]

        # check each neighbor if not visited
        for neighbor in neighbors:
            try:
                if maze[row + neighbor[0]][column + neighbor[1]] in [" ", "E"]:
                    queue.append([row + neighbor[0], column + neighbor[1], solution + [neighbor[2]]])
            except IndexError:
                continue

        # mark as visited
        maze[row][column] = "."


PROCESS_TIME = time.process_time()
print(solve_maze(copy.deepcopy(MAZE), 1, 4, ["START"])[1:])
print(time.process_time() - PROCESS_TIME)

PROCESS_TIME = time.process_time()
print(solve_maze_bfs(MAZE, 1, 4, ["START"])[1:])
print(time.process_time() - PROCESS_TIME)