Solving Maze using Graphs # -*- coding: utf-8 -*- """ Created on Mon Oct 21 21:46:55 2019 @file: @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')