CODEWITHSUNDEEP
pythonalgorithmstack
Robin Andrews
Robin Andrews

Reputation: 3804

Maze Solving Using Stack in Python - is my Algorithm correct?

I've written some Python code to help me understand how to solve a maze using a stack and no recursion.

what I've come up with SEEMS to work (as in the target position in the 2d array representing the maze is reached is several versions of the maze). The representation if 1 for a wall, 0 for a space, 2 for the goal and 3 for "visited".

However, I'm suspicious and would like someone to confirm whether the logic is correct or if not what I need to do to fix it.

My main concern is that coordinates are being put back on the stack even when they have been visited.

Please understand the chicken and egg nature of my situation - I don't fully understand how the algorithm works, so I've written some code to help me understand but I'm not sure if the code is correct, which partly depends on understanding the algorithm...

As always, any help much appreciated. Code below:

class Stack:
    def __init__(self):
        self.list = []

    def push(self, item):
        self.list.append(item)

    def pop(self):
        return self.list.pop()

    def top(self):
        return self.list[0]

    def isEmpty(self):
        return not self.list

    def empty(self):
        self.list = []

maze = [[0, 0, 1, 1],
        [0, 1, 0, 1],
        [0, 0, 1, 1],
        [0, 0, 2, 0]]

MAZE_SIZE = len(maze)


def print_maze(maze):
    for row in maze:
        print((row))

def is_valid_pos(tup):
    (col, row) = tup
    if col < 0 or row < 0 or col >= MAZE_SIZE  or row >= MAZE_SIZE :
        return False
    return maze[row][col] == 0 or maze[row][col] == 2


def solve(maze, start):
    s = Stack()
    (col,row) = start
    print('pushing ({},{})'.format(col,row))
    s.push((col,row))

    while not s.isEmpty():
        print('Stack contents: {}'.format(s.list))
        input('Press Enter to continue: ')
        print('Popping stack')
        (col, row) = s.pop()
        print('Current position: ({}, {})'.format(col,row))

        if maze[row][col] == 2:
            print('Goal reached at ({}, {})'.format(col,row))
            return
        if maze[row][col] == 0:
            print('Marking ({}, {})'.format(col,row))
            maze[row][col] = 3
        print_maze(maze)
        print('Pushing coordinates of valid positions in 4 directions onto stack.')
        if is_valid_pos((col+1, row)): s.push((col+1, row)) 
        if is_valid_pos((col, row+1)): s.push((col, row+1))
        if is_valid_pos((row, col-1)): s.push((row, col-1))
        if is_valid_pos((row-1, col)): s.push((row, col))


solve(maze, (0,0))

Upvotes: 1

Views: 2407

Answers (1)

blhsing
blhsing

Reputation: 106995

Since in your coordinate system columns always come before rows, you should change:

if is_valid_pos((row, col-1)): s.push((row, col-1))
if is_valid_pos((row-1, col)): s.push((row, col))

to:

if is_valid_pos((col-1, row)): s.push((col-1, row))
if is_valid_pos((col, row-1)): s.push((col, row-1))

and your code would work.

Upvotes: 2

Related Questions