# Non-recursive BFS Maze Solving with Python

I wrote this program to help me understand how BFS and Queues work. (Also DFS if I replace the queue with a stack).

It works, but I'm curious how well I implemented the algorithm.

Are there any obvious improvements?

For example, I notice that there are duplicate values in the Queue. I understand that I should avoid visiting already visited positions. However the queue contains only "prospective" positions which are yet to be visited. Should I modify the algorithm to not enqueue positions which it already contains?

My agenda is to understand Data Structures and Algorithms and write reasonable quality code to implement the basic concepts.

from os import system
from random import randint

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

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

def dequeue(self):
temp = self.list[0]
del self.list[0]
return temp

def isEmpty(self):
return not self.list

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

def create_maze(n):
maze = []
for row in range(n):
row = []
for col in range(n):
if randint(0,3) == 0:
row.append(1)
else:
row.append(0)

maze.append(row)

maze[0][0] = 0
maze[n-1][n-1] = 2
return 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):
q = Queue()
(col,row) = start
print('Enqueueing ({},{})'.format(col,row))
q.enqueue((col,row))

while not q.isEmpty():
print('Queue contents: {}'.format(q.list))
input('Press Enter to continue: ')
print('Dequeueing')
(col, row) = q.dequeue()
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('Enqueueing coordinates of valid positions in 4 directions.')
if is_valid_pos((col+1, row)): q.enqueue((col+1, row))
if is_valid_pos((col, row+1)): q.enqueue((col, row+1))
if is_valid_pos((col-1, row)): q.enqueue((col-1, row))
if is_valid_pos((col, row-1)): q.enqueue((col, row-1))

print("Goal can't be reached.")

while True:
system('cls')
maze = create_maze(4)
MAZE_SIZE = len(maze)
solve(maze, (0,0))
input('Press Enter to restart: ')


Feedback in mostly top-down order

"""Doc strings""". You should get in the habit of adding these at the top of your file, the top of every class, and the top of every (public) function.

class Queue. I'm certain you know that Python comes with everything including the kitchen sink, so it should come as no surprise that there exists a deque already builtin. I'll assume you implemented your own for practice. ;-)

self.list The list member should not be accessed outside of the Queue class; it is an internal private detail. To indicate this, you should name the member with a leading underscore, referencing it as self._list. Python does not enforce public/private semantics, but many code-review tools (such as pylint) will check for and complain about these violations. Also, leading underscores can "hide" members from autogenerated documentation.

You actually do reference it outside the Queue class, to print the queue's contents. You should instead implement the method which converts the object to a string, for printing. It is called __str__, and you could implement it like:

class Queue:
# ... your other methods here

def __str__(self):
return str(self._list)


Then instead of .format(q.list), you could write .format(q).

    def dequeue(self):
temp = self.list[0]
del self.list[0]
return temp


This is verbose code to retrieve an item from the start of a list, remove the item from the list, and return the item. The list has a builtin method to do this: pop(0).

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


    maze = []
for row in range(n):
row = []
...
maze.append(row)


The variable row is created in the for loop, and assigned the value 0 (an integer). Then, the next statement reassigns row to [] (a list). Fortunately, when the loop returns for the next value, it doesn't try to add 1 to row, but rather retrieves the next value from the range(n), and the loop works properly. But this is still poor coding. pylint will complain that the type of row (not that python has typed variables) changes between an int and a list.

Better would be to use a different variable names, or since the int value of row is never used, to use no variable name at all. A single underscore is by convention the "throwaway" variable, used when you need a variable but will never use it.

    maze = []
for _ in range(n):
row = []
...
maze.append(row)


row.append(0)
row.append(1)
maze[n-1][n-1] = 2
maze[row][col] = 3


Magic numbers! What is 0? What is 1? What is 2? What is 3?

Help maintain the code by giving names to these numbers. For example, you could add:

EMPTY = 0
BLOCKED = 1
GOAL = 2
VISITED = 3


at the top of your program, and then use:

maze[n-1][n-1] = GOAL


Readers/maintainers of your program will understand more quickly what is meant by GOAL than by 2.

But, just assigning values to variable names is slightly dangerous. They are variables can therefore can be changed. Better would be to create an Enum:

from enum import Enum
class Position(Enum):
EMPTY = 0
BLOCKED = 1
GOAL = 2
VISITED = 3


Then you can write:

maze[n-1][n-1] = Position.GOAL


And the value of Position.GOAL cannot be changed.

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


You always call is_valid_pos((..., ...)), constructing a tuple to pass to the function, which immediately unpacks the tuple into col and row. Why not simply use col and row as parameters?

The tests for whether row and col are within the valid range is more complex than it needs to be. Python allows for chained comparisons. The compound test:

if 0 <= row  and  row < MAZE_SIZE:


can be written as:

if 0 <= row < MAZE_SIZE:


Python evaluates 0 <= row, then row < MAZE_SIZE, then the and of the two values. So the function may be rewritten as:

def is_valid_pos(col, row):
if  0 <= col < MAZE_SIZE  and  0 <= row < MAZE_SIZE:
return (maze[row][col] == Position.EMPTY  or
maze[row][col] == Position.GOAL)
return False


As of Python 3.6, we have "f-strings". This means instead of:

print('Enqueueing ({},{})'.format(col,row))


where you need to match the format() arguments to the correct {} codes positions, we can write:

print(f'Enqueueing ({col},{row})')


which is shorter and may be simpler to understand.

    if is_valid_pos((col+1, row)): q.enqueue((col+1, row))
if is_valid_pos((col, row+1)): q.enqueue((col, row+1))
if is_valid_pos((col-1, row)): q.enqueue((col-1, row))
if is_valid_pos((col, row-1)): q.enqueue((col, row-1))


This code style is error prone. You probably copied the first line, and pasted it 3 times, and then changed the +1's to -1's, and moved them from col to row. Did you make the same change to corresponding the is_valid_pos() and q.enqueue() calls?

Better might be:

    enqueue_if_valid(q, col+1, row)
enqueue_if_valid(q, col, row+1)
enqueue_if_valid(q, col-1, row)
enqueue_if_valid(q, col, row-1)


and write an enqueue_if_valid() function:

def enqueue_if_valid(q, col, row):
if is_valid_pos(col, row):
q.enqueue((col, row))


I notice that there are duplicate values in the Queue. I understand that I should avoid visiting already visited positions. However the queue contains only "prospective" positions which are yet to be visited. Should I modify the algorithm to not enqueue positions which it already contains?

Since we have moved the 4 enqueue operations into a call to one function, it would now become easier to implement this improvement. One way would be to search the queue for the tuple you are about to add, but an easier way would be to mark maze[col][row] with Position.ENQUEUED, if it was Position.EMPTY. Then the next time you are about to enqueue that position, instead of that position being valid, it would return invalid and not be enqueued a second time.

What is maze? Is it a local variable, and passed to solve(maze, ...) and print_maze(maze)? Or is it a global variable that is_valid_pos() automatically knows about?

Pick one.

MAZE_SIZE is also a global. Do you need it? Or could you just use len(maze) when it is required?

• Great. Thanks for all that. I will assimilate... – Robin Andrews Sep 28 '18 at 12:25