Maze solver in Python homework help

June 12, 2024
Martin Jonas
🇦🇺 Australia
Python
Dr. Martin Jonas, PhD in Computer Science from Southern Cross University, Australia. With 4 years of experience in Python assignments, I offer expert guidance and support to help you excel in your programming projects.
Key Topics
• Solving Maze using Graphs
Tip of the day
News

Our Python homework help solvers have written a program that can solve a maze, using depth-first search. The maze consists of a series of edges, and a start and end node. There should be multiple test cases to test the solver.

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') ```

Similar Samples

Explore our sample projects to witness the quality and precision of our programming homework solutions. Each sample highlights our expertise, meticulous approach, and dedication to helping you succeed. See for yourself how we can elevate your understanding and performance in your programming courses