Problem: A maze is a rectangular arrangement of blocks (walls) and open spaces (paths). A maze may have a path through i

[answerhappygod]

Problem A Maze Is A Rectangular Arrangement Of Blocks Walls And Open Spaces Paths A Maze May Have A Path Through I 1 (65.02 KiB) Viewed 57 times

Problem: A maze is a rectangular arrangement of blocks (walls) and open spaces (paths). A maze may have a path through it from a given start location to a given end location. You can usually move only one cell at a time. From each cell you choose your next move. Moves can only be into unblocked cells. In a restricted maze (which we are describing here) you can not cross your existing path: i.e., once you visit a particular cell, you can't visit it again (for all intents and purposes, a visited cell is blocked to future attempts to move). For example, this maze: 0 1 2 3 4 5 6 7 0 1 2 3 3 4 5 Has a path: (0,0),(0,1) (1,1) (2,1) (2,2)(3,2)(3,3)(3,4) (2,4) (1,4) (1,5)(1,6) (2,6) (3,6) (4,6) (5,6) (5,7) from start=(0,0) to goal=(5,7). Notice that the vertical dimension starts at zero, and increases down. These are rows, and the first element in a coordinate is the row. The horizontal dimension is the column, the second coordinate.

Approach: Implement a Python function SolveMaze(m,s,g) to determine if a path exists within the maze, m, from the current location s to the goal location g. This does not have to be the shortest path; any path will do. The function must be recursive. Some constraints on your solution: . Your maze is to be represented as a Python list of lists. • The current (s) and goal (g) locations are to be represented as Python tuples (r, c) where r (row) and c (column) represent the index values into the list of the cell location. • Input to your application will be a file of text containing 'O' for an open cell and '1' for a blocked cell. For example the above maze will be in a file as: ооооо1 оо 1 0 1 1 0 0 0 0 1 0 0 1 0 1 0 1 0 1 0 0 0 1 0 0 000 0 1 1 0 1 оо1 ооооо • If a path does not exist, do not output anything to the console. If a path exists, output the maze and mark the path with 'P' as shown below. Рpooooo 1 P 11 PPPO 1 PP 1 P 1 P 1 0 1 P P P 1 PO 0 0 0 0 1 1 P 1 oo 1 ooopp . Your function should also return the boolean value True if a path exists, or False if no path exists. Note: Your path does Here are some hints about SolveMaze (m,s,g): • The argument given to the current location s will be different as the computer explores the maze. • The argument given to the goal location g will never change the target never moves! • As the function explores the maze, the maze changes because you mark the places your path has visited with a 'P! You are not allowed to visit a location more than once. So if your function takes a wrong turn, and blocks the only path, further exploration will not be able to find a path. • Because each step in the exploration changes the maze, you have to be careful about how you call SolveMaze (m,s,g) • The function cannot guess the right path. It has to find the path by exploring all the options. Exploring the options means calling SolveMaze (m,s,g) several times. Reachable cells are defined as any cell in one of the four cardinal directions (north, west, south, east), except where • You can not go to a cell containing a 'l' • You can not go west of the left most cell of any row, . You can not go east of the right most cell of any row,

• You can not go north of the top most cell of any row, • You can not go south of the bottom most cell of any row, • You can not occupy a cell already occupied by your current path. Examples You are given a series of mazes to solve. • maze1.txt Start (0.3) Goal (4,5) • maze2.txt Start (0,0) Goal (8,9) • maze3.txt Start (3,0) Goal (23.30) The three mazes provided may or may not have a path from start to goal. You can also create your own for testing purposes What to Hand In • A Python program named a8q4.py containing your recursive function SolveMaze(). Be sure to include your name, NSID. student number, course number and laboratory section at the top of all documents. Evaluation . 3 marks: Correctly reads in the maze data from a text file, and produces a list of lists using the data. • 3 marks: Using tuples to represent position, including start and goal. • 6 marks: Function is recursive, and correctly displays a path from start to goal, if one exists. For Fun (Optional, Not Worth Marks) 1. Modify your code so that it will find ALL paths that meet the requirements.

Maze1 - Notepad File Edit Edit Format 1 1 1 0 1 0 1 0 0 0 1 0 1 0 1 0 0 0 1 0 0 0 1 0 1 0 0 0 1 0

Maze2 - Notepad File Edit Format View 0100010000 0 1 0 1 0 1 0 1 1 0 0 0 0 1 0 1 0 0 0 0 110 11111 0 1 1 1 0 1 1 1 1 1 0 1 0 1 0 1 000 000 o101 0 1 0 0 0 1 0 1 1 1 0 1 0 1 0 1 0 1 0 0 0 0 0 0 0 1 0 0 0 1 0 1 0 1 1 1 1 0 0 1 0 0

Maze3 - Notepad File Edit Format View Help 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1о1оооооооооооо1ооооооо1о1 ооо1 0 1000 1 101 01110 111110101 01111101010101 0 0 0 1 0 0 0 1 0 0 0 0 0 1 0 1 0 1 0 0 0 1 0 1 0 0 0 1 0 1 0 1 0 eee 1 eeeee 0 0 0001 0 0 0 0 1 0 1 0 1 0 1 1 1 1 1 0 1 0 1 1 1 1 1 0 1 0 1 1 1 1 1 0 1 0 1 0 1 1 1 1 0 1 1 0 1e0o1e1e0o1 оооооооо1ооооо1е1е1 0 0 1 1 1 1 1 1 0 1 0 1 0 1 1 1 1 1 0 1 0 1 1 1 0 1 1 1 0 1 0 1 0 1 1 0 1 1 1 0 1 1 1 0 1 0 1 1оооооо1 ооо1ооооо1ооооо1ооо1о1 0 0 0 0 0 0 0 0 0 0 0 0 1 10101110 11111 0 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 0 1 1 1 1 1 1 1 1 1 1 0 1 1 0 1 0 0 0 1 0 1 0 0 0 1 0 0 0 0 0 1 0 0 0 1 0 0 0 1 0 1 0 1 0 000 1 0 0 0 0 1 000 1 10111 01110101 011101110101110101 0 1 0 0 0 1 0 0 0 0 0 1 0 1 0 0 0 1 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 01 0000 0 000 0 0 0 0 0 0001 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 0 1 1 1 1 0 1 1ооо1 ооооо1 ооо1оооооооооооо1о1 01 0 0 0 0 10111 0111010101 011111111111 0 1 0 1 0 0 0 1о1ооо1 ооо1о1 ооо1 ооооооооо1 ооо1 0 0 0 0 0 0 0 0 1 1 1 0 1 0 1 1 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 1 1 0 1 0 1 1 1 0 1 1 1 1 1 1 1 1 0 1 1 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 1 0 0 0 1 0 1 0 0 0 1 0 0 0 1 1 ооо1 eee1 0 eeee 10001 000 1 1 0 1 1 1 0 1 0 1 0 1 1 1 1 1 0 1 1 1 0 1 0 1 0 1 1 1 1 1 0 1 0 0 0 0 0 0 0 1ооо1е1е1е1 ооо1 ооо1о1о1ооооооо1 0 0 0 0 0 0 01 0 1110101010101 01110101 0111110111 0 1ооо1о1о1ооо1ооооо1ооооо1ооооо1 0 0 0 0 0 0 0 0 0 0 0 1 1 0 1 1 1 0 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1e1e1e0o1ооооооооооо1ооо1оооо 1 0 1 0 1 1 1 0 1 1 1 0 1 0 1 0 1 0 1 0 1 0 1 1 1 0 1 0 1 1 1 0 0 0 0 0 0 0 0 101000101000101010 0010100010001 1011101010 111 0 1 0 1 1 1 1 1 0 1 0 1 1 1 1 1 0 1 1 0 0 1 1 1 0 1 1 1ооооо1о1о1о1ооооооо1ооо1ооооо1 0 eee1 0 0 000 0 0 0 0 eee1 eeee1 11111110101 011111110 11111 0 1 0 1 1 1 0 0 1ооооооооооооооооо1ооооооо1 ооо1 0 0 0 0 0 1 1111111111111111111111111111111