solving MAZE using python

  

#Maze dimensions 8*13 

def print_maze(maze):

    for row in maze:

        for item in row:

            print(item, end='')

        print()

     

def find_start(maze):

    for row in range(len(maze)): #len of maze is 8

        for col in range(len(maze[0])): #col=13

            if maze[row][col] == 'S':

                return row, col  #row=1,col=0

# This is function tells if we have a valid position.

def is_valid_position(maze, pos_r, pos_c):

    if pos_r < 0 or pos_c < 0:

        return False

    if pos_r >= len(maze) or pos_c >= len(maze[0]):

        return False

    if maze[pos_r][pos_c] in ' E':

        return True

    return False

#ALGORITHM

def solve_maze(maze, start):

    # We use a Python list as a stack - then we have push operations as append, and pop as pop.

    stack = []

    # Add the entry point (as a tuple)

    stack.append(start)  #[(1,0)]

    #total steps by rat

    steps=0

    # Go through the stack as long as there are elements

    while len(stack) > 0:

        pos_r, pos_c = stack.pop()  #pos_r=1,pos_c=0

        print("Current position", pos_r, pos_c) #1,0

        if maze[pos_r][pos_c] == 'E':

            print("GOAL")

            print("Total steps: ",steps)

            return True

        if maze[pos_r][pos_c] == 'X':

            # Already visited

            continue

        # Mark position as visited

        maze[pos_r][pos_c] = 'X'  # mark 1,0 with X

        steps+=1

        # Check for all possible positions and add if possible

        #Top row

        if is_valid_position(maze, pos_r - 1, pos_c):

            stack.append((pos_r - 1, pos_c))

        #Bottom row

        if is_valid_position(maze, pos_r + 1, pos_c):

            stack.append((pos_r + 1, pos_c))

        #Left col

        if is_valid_position(maze, pos_r, pos_c - 1):

            stack.append((pos_r, pos_c - 1))

        #rigth col

        if is_valid_position(maze, pos_r, pos_c + 1):

            stack.append((pos_r, pos_c + 1))

        # To follow the maze

        print('Stack:' , stack)

        print_maze(maze)

    # We didn't find a path, hence we do not need to return the path

    return False

#maze = load_maze("maze.txt")

#maze = convert_maze(maze)

maze =[['#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#'],

 ['S', ' ', '#', ' ', ' ', ' ', ' ', ' ', '#', ' ', ' ', ' ', '#'],

 ['#', ' ', '#', ' ', ' ', '#', '#', ' ', ' ', ' ', '#', ' ', '#'],

 ['#', ' ', '#', ' ', ' ', '#', '#', ' ', '#', '#', '#', ' ', '#'],

 ['#', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '#', ' ', ' ', ' ', '#'],

 ['#', '#', '#', '#', '#', '#', '#', '#', '#', ' ', '#', ' ', '#'],

 ['#', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '#', ' ', 'E'],

 ['#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#']]

print_maze(maze)

print("\n\n")

print("Start point is ")

start = find_start(maze)  #1,0

print(start)  #1,0

print("\n\n Solution is ")

print(solve_maze(maze, start))