Solving Maze using Graphs
Maze.py
# -*- coding: utf-8 -*-
"""
Created on Mon Oct 21 21:46:55 2019
@file: maze.py
@author: Antoun
@purpose: to solve a maze problem
"""
class Maze:
"""
This is the maze class that uses the graph representation to describe the
maze to be solved
The class defines several helpful methods and fields:
solve(src,dest): to initialize the variables used by the DFS algorithm
dfs(node): a function to print the valid path between the goal node
and the node specified in the arguments
"""
def __init__(self,edge_list):
"""
a function to initalize the maze vertices according to edge_list
Arguments: edge_list is a list of tuples reprents connections between
verticies
Pre-condition: edge_list is not empty
"""
self._maze={}
self._maze = self._build_maze(edge_list)
def _build_maze(self,edge_list):
for i in range(len(edge_list)):
if((edge_list[i][0] in self._maze) == False):
self._maze[edge_list[i][0]]= []
if((edge_list[i][1] in self._maze) == False):
self._maze[edge_list[i][1]]= []
self._maze[edge_list[i][0]].append(edge_list[i][1])
self._maze[edge_list[i][1]].append(edge_list[i][0])
return self._maze
def solve(self,src,dest):
"""
This function is responsible for initilizing variables used by the dfs
algorithm:
res is a result list of a valid path
goal is the goal node
Arguments: src is the src node, dest is the dest node
"""
self.res=[src]
self.goal = dest
self.dfs(src)
def dfs(self,node):
"""
This is the maian function to solve the problem. it uses recursion and
edge_list and visited list (lies in res list) to find a valid path
between node and self.goal
Arguments: node is the src node of this run of dfs
"""
if(node == self.goal):
print (self.res);
return
for i in range(len(self._maze[node])):
# if visited don't process
if(not self.res.__contains__(self._maze[node][i])):
# add to list as visited node
self.res.append(self._maze[node][i])
self.dfs(self._maze[node][i])
# pop from list as unvisited node after checking its path
self.res.pop()
#TestCase #1
edge_list = [['a','b']]
this_maze = Maze(edge_list)
this_maze.solve('a','b')
#TestCase #2
edge_list = [['a','b'],['a','c']]
this_maze = Maze(edge_list)
this_maze.solve('a','c')
#TestCase #3
edge_list = [['a','b'],['a','c'],['c','d']]
this_maze = Maze(edge_list)
this_maze.solve('a','d')
#TestCase #4
edge_list = [['a','b'],
['a','c'],
['e','c'],
['b','d'],
['a','e']]
this_maze = Maze(edge_list)
this_maze.solve('a','d')
#TestCase #5
edge_list = [['a','b'],
['a','c'],
['b','c'],
['b','d'],
['a','e'],
['e','d'],
['b','e']]
this_maze = Maze(edge_list)
this_maze.solve('a','d')