Find route through maze

Find route through maze

For this assignment, you must use recursion to determine the solution to the maze. No other functions are required to be recursive. You also must create and call the three functions described in “Requirements”. All other design decisions are up to you.

You may NOT change the maze once it’s read in. Do not add “walls” to the maze, or otherwise update the information.

For this assignment, you do need to worry about “input validation.” You may assume that the user will enter the correct type of input, but the input may be negative, outside of the allowable range, or “bogus” (in the case of strings).

If the user enters a different type of data than what you asked for, your program may crash. This is acceptable.

It is also acceptable if your program crashes when a filename is entered that either does not exist, or has the wrong formatting for the minesweeper board.

Details

For this project, you will harness the computing power of Python to solve a maze, using a recursive search algorithm. You will need to understand algorithms, Python data structures, file I/O, and recursion to complete this project.

The maze will be rectangular, comprised of square spaces. The Maze Solver can move freely between two adjacent squares, as long as the movement is horizontal or vertical (no diagonal moves), and the way is not blocked by a wall. The dimensions, finishing square, and configuration of each maze are provided in a separate file. The starting square from which the maze solution is attempted is chosen by the user.

Your Maze Solver will start from the user’s choice of starting position, and will search out a path to the finish square. It can travel right, down, left, or up, as long as it doesn’t go through any walls. When it finds a solution, it will print out the successful path. If there is no successful path, it must print out that there is no solution.

Your Maze Solver must use a recursive algorithm. Starting from the start square, your algorithm will scan for all the adjacent squares it can legally travel to in the next step. For each candidate “next square,” it will first check that it has not already been there. If not, it will try adding that square to the path built so far, and will use recursion to find a path from that new square to the end. If that recursion fails, it moves on to the next candidate. If all “next square” candidates fail, this instance of the recursion itself fails.

This is what is known as a “brute force” method in computer science: try every possible combination until you either find an answer, or run out of options and give up. Although this method might seem very silly and slow, your Python program will beat you every time, simply because its speed at solving problems like this is much faster than yours.

Input File:

The input files will all have the following format:

  •  Line 1: two integers, specifying the number of rows and columns in the maze
  •  Line 2: two integers, specifying the row and column position of the “finish”
  •  Remaining lines: The remainder of the lines specify the wall layout for

each of the squares in the maze, starting with the top left square, moving across the entire top row, then continuing from the left-most square on the second row, and so on.
Each line specifies the wall layout for one square using four integers, describing the walls in order: right, bottom, left, and top.

A “1” means there is a wall, and a “0” means there is no wall. So a square that is specified as “1 0 0 1” has a wall on the right, is open on the bottom, is open on the left, and has a wall on the top.

Notice that the way we specify the maze repeats a lot of information: most of the walls in the maze are described in the specification for both of the squares that touch it. (The only exception are the walls that make up the edge, which only touch a single square.) This makes the specification for the squares completely independent, which will actually make it easier for you to construct and use the maze data structure when your Maze Solver is searching for a solution.

You can count on the data file being consistent and correct. (In other words, if a square says it has a right wall, the square to the right of it is guaranteed to say that it has a left wall.) You can also count on it being completely boxed in, with walls around the outside.

After your program reads in and “constructs” the maze, it will initialize a few other things, ask the user for their starting point, and initiate a recursive search. At the end, it will print out its results: if a path was found, it will print out the steps taken to reach the end; otherwise, it will print out that no solution was found from that starting point.

Data Structures:

To represent your maze, you should use a 3-dimensional list, also known as a list-of-lists-of-lists. This might sound intimidating, but you already know enough to deal with this confidently.

As an example, if you have a Python list named “square_0”, which has four numbers in it (representing the 4 walls), and you have another one much like it named “square_1”, and yet another list “square_2”, you can then make a list-of-lists called “row_0” with this code:

    square_0 = [1, 1, 1, 0]     square_1 = [0, 1, 0, 1]     square_2 = [1, 0, 1, 0]

    row_0 = []     row_0.append(square_0)     row_0.append(square_1)     row_0.append(square_2)

And if you did that a few more times to create more rows, you can then make a list-of-lists-of-lists called (for example) “maze”, by doing something like:

maze = []     maze.append(row_0)     maze.append(row_1)     maze.append(row_2)

Except, of course, you would use loops to put this together from the input file.

You could then do cool things like test for a wall on a specific side in a specific square via:

if maze[1][2][TOP] == 1  # row 1, col 2

By the way, you could also have split the above into two steps by doing something like:

row = 1 col = 2 square = maze

[row]

[col] if square[TOP] == 0:

    # explore in the top direction because it’s open 

Recursive Algorithm:

What is your base case? Is there more than one base case?

Think very carefully about what information your recursive algorithm will need at each step of the way.

  • ·  Does it need a copy of the maze?
  • ·  Does it need to know the starting point?
  • ·  Does it need to know the current point?
  • ·  Does it need to know the finish point?
  • ·  Does it need to know the path so far?
  • ·  Does it need to know the number of rows?
  • ·  Does it need to know the number of columns?

The answer is not “yes” to all of these, but your recursive function will need at least a few of these at every step.

Requirements:

Your program must have the following functions. You may include additional ones that you think are necessary:

main()

This should handle the calls to most of the other functions.

readMaze(filename)

This function should read in the maze specification from the filename specified, and return a maze data structure. You are not required to use a 3-dimensional list, but we think it is the best option. The maze data structure should be designed to make it simple to determine what the row and column dimensions are. searchMaze(maze, ???)

This function takes a maze data structure as created by readMaze(), along with some additional information that you will need to decide. This function must be recursive. After it completes and all of the recursion has ended, searchMaze() should return either a complete solution path (if it found one) or None if there was no solution.

Input Validation:

You will need to validate the following things:
· When asked to enter the starting point, the user might enter any whole number. If the row or column entered is not valid, it must reprompt, telling them what the valid options are.

Sample Maze Files:

We have provided sample files for you. The first is used in the sample output, and is simple. The second one is more of a “challenge” for your Maze Solver.

cp /afs/umbc.edu/users/k/k/k38/pub/cs201/maze1.txt . cp /afs/umbc.edu/users/k/k/k38/pub/cs201/maze2.txt .

Sample Output:We also highly recommend creating your own simple test mazes, like a simple 1×4 “corridor”, or a 2×4 maze with a single turn.

Here is some sample output, with the user input in blue.  

0,0 0,1 0,2 0,3
1,0 1,1 1,2 1,3
2,0 2,1 2,2 2,3

 bash-4.1$ python proj2.py Welcome to the Maze Solver!

Please enter the filename of the maze: maze1.txt

Please enter the starting row: 9

Invalid, enter a number between 0 and 2 (inclusive): 22

Invalid, enter a number between 0 and 2 (inclusive): 0

Please enter the starting column: -1

Invalid enter a number between 0 and 3 (inclusive): 1

Solution found!

(0, 1)

(0, 2)

 (0, 3)

(1, 3)

(1, 2)

(1, 1)

(1, 0)

(2, 0)

(2, 1)

(2, 2)

(2, 3)

bash-4.1$ python proj2.py Welcome to the Maze Solver!

Please enter the filename of the maze: maze1.txt

Please enter the starting row: 0

Please enter the starting column: 0

No solution found!

0,0 0,1 0,2 0,3
1,0 1,1 1,2 1,3
2,0 2,1 2,2 2,3

Debugging:

We highly recommend the use of debug statements when you’re working on this project. Debug statements are simple print statements in your code that give you a bit more information on what exactly is going on.

For example, you might want to know in which direction your Maze Solver is moving:

print(“Currently moving to the right”) Or you might want to know what the path looks like so far:

print(“The current path is:”, path)

bash-4.1$ python proj2.py Welcome to the Maze Solver!

Please enter the filename of the maze: maze1.txt

Please enter the starting row: 0

Please enter the starting column: 0

     DEBUG: Looking at row 0 and column 0   

     DEBUG: Can’t go right     

     DEBUG: Can’t go bottom     

     DEBUG: Can’t go left

     DEBUG: Can’t go top

No solution found!

The debug statements are in green for clarity. We’ve turned the background a light yellow to differentiate this from normal sample output.

bash-4.1$ python proj2.py Welcome to the Maze Solver! Please enter the filename of the maze: maze1.txt

Please enter the starting row: 0

Please enter the starting column: 1

     DEBUG: Path currently [[0, 1]]

      DEBUG: Looking at row 0 and column 1

      DEBUG: Moving right

      DEBUG: Path currently [[0, 1], [0, 2]]

      DEBUG: Looking at row 0 and column 2

      DEBUG: Moving right

      DEBUG: Path currently [[0, 1], [0, 2], [0, 3]]

      DEBUG: Looking at row 0 and column 3

      DEBUG: Can’t go right

      DEBUG: Moving bottom

      DEBUG: Path currently [[0, 1], [0, 2], [0, 3], [1,

3]]

      DEBUG: Looking at row 1 and column 3

      DEBUG: Can’t go right

      DEBUG: Can’t go bottom

      DEBUG: Moving left

      DEBUG: Path currently [[0, 1], [0, 2], [0, 3], [1,

3], [1, 2]]

      DEBUG: Looking at row 1 and column 2

      DEBUG: Can’t go bottom

      DEBUG: Moving left

      DEBUG: Path currently [[0, 1], [0, 2], [0, 3], [1,

3], [1, 2], [1, 1]]

      DEBUG: Looking at row 1 and column 1

      DEBUG: Can’t go bottom

      DEBUG: Moving left

      DEBUG: Path currently [[0, 1], [0, 2], [0, 3], [1,

3], [1, 2], [1, 1], [1, 0]]

      DEBUG: Looking at row 1 and column 0

      DEBUG: Moving bottom

[etc]

Maze1.txt

3 4

2 3

1 1 1 1

0 1 1 1

0 1 0 1

1 0 0 1

0 0 1 1

0 1 0 1

0 1 0 1

1 1 0 0

0 1 1 0

0 1 0 1

0 1 0 1

1 1 0 1

Maze2.txt

10 10

9 9

0 0 1 1

1 1 0 1

0 0 1 1

0 0 0 1

1 0 0 1

0 1 1 1

0 0 0 1

0 1 0 1

0 0 0 1

1 1 0 1

0 0 1 0

0 1 0 1

1 1 0 0

1 0 1 0

0 1 1 0

1 0 0 1

0 1 1 0

1 1 0 1

0 1 1 0

1 0 0 1

0 1 1 0

0 0 0 1

1 1 0 1

1 0 1 0

0 1 1 1

0 1 0 0

0 1 0 1

0 1 0 1

0 1 0 1

1 0 0 0

0 1 1 1

1 1 0 0

0 0 1 1

1 0 0 0

0 0 1 1

0 1 0 1

1 0 0 1

0 0 1 1

1 0 0 1

1 0 1 0

0 0 1 1

1 0 0 1

1 0 1 0

1 0 1 0

1 1 1 0

1 0 1 1

1 0 1 0

1 0 1 0

0 1 1 0

1 1 0 0

1 0 1 0

0 1 1 0

1 0 0 0

1 1 1 0

0 0 1 1

1 0 0 0

1 0 1 0

1 0 1 0

0 0 1 1

1 0 0 1

1 0 1 0

0 1 1 1

1 1 0 0

0 0 1 1

1 1 0 0

0 1 1 0

1 1 0 0

1 0 1 0

1 0 1 0

1 1 1 0

0 1 1 0

1 0 0 1

0 0 1 1

1 1 0 0

0 1 1 1

0 1 0 1

1 0 0 1

1 0 1 0

0 1 1 0

1 0 0 1

0 0 1 1

1 1 0 0

0 1 1 0

0 1 0 1

1 0 0 1

0 0 1 1

1 1 0 0

0 1 1 0

0 1 0 1

1 0 0 0

0 1 1 0

0 1 0 1

0 1 0 1

0 1 0 1

1 1 0 0

0 1 1 0

0 1 0 1

0 1 0 1

0 1 0 1

1 1 0 0

ALIVE_CELL = ‘A’

DEAD_CELL  = ‘.’

MIN_LIVING_NEIGHBORS = 2

MAX_LIVING_NEIGHBORS = 3

NUM_NEIGHBORS_TO_BECOME_ALIVE = 3

######################################################################

# getInteger() reprompts the user until they enter a number

#               greater than or equal to a minimum value

# Input:        prompt;   string displayed to user

#               minVal;   integer of lower accepted range

# Output:       newInt;   integer greater than or equal to minVal

defgetInteger(prompt, minVal):

haveNumber = False

while not haveNumber:

newInt = int(input(prompt))

ifnewInt<minVal:

print(‘That is not a valid value; please enter a number greater than or equal to ‘ + str(minVal))

else:

haveNumber = True

returnnewInt

######################################################################

# emptyBoard() creates a nRows x nCols board with all cells set to

#              a “dead” state

# Input:       nRows; integer, the number of board rows

#              nCols; integer, the number of board columns

# Output:      board; a list of lists representing

#                     rows of the newly created board

defemptyBoard(nRows, nCols):

board = []

for i in range(nRows):

board.append([DEAD_CELL] * nCols)

return board

######################################################################

# printBoard() prints a board on the screen

# Input:       board; a list of lists representing

#                     rows of the board

# Output:      none (print board)

defprintBoard(board):

for row in board:

print(“”.join(row))

######################################################################

# countAliveNeigbors() return the number of cells around the cell

#                      at location (iC, jC) that are “alive”

# Input:       board; a list of lists representing rows of the board

#              iC; integer cell row

#              jC; itteger cell column

# Output:      count; integer representing the number of neighboring

#                     cells that are “alive”

defcountAliveNeigbors(board, iC, jC):

nRows, nCols = len(board), len(board[0])

count = 0

for i in [-1, 0, 1]:

for j in [-1, 0, 1]:

if i == 0 and j == 0:

continue    # do not count itself

if 0 <= i + iC<nRows and 0 <= j + jC<nCols:

count += board[i + iC][j + jC] == ALIVE_CELL

return count

######################################################################

# nextIteration() calculates the state of the board according to

#                 the game rules for one step advance

# Input:        board;    a list of lists representing rows of

#                         the board

# Output:       newBoard; a list of lists with the board state on

#                         the next iteration step

defnextIteration(board):

nRows, nCols = len(board), len(board[0])

# create a new board with all cells “dead”

newBoard = emptyBoard(nRows, nCols)

for i in range(nRows):

for j in range(nCols):

numNeigbors = countAliveNeigbors(board, i, j)

if board[i][j] == ALIVE_CELL:

ifnumNeigbors>= MIN_LIVING_NEIGHBORS and numNeigbors<= MAX_LIVING_NEIGHBORS:

newBoard[i][j] = ALIVE_CELL   # “alive” cell keeps alive

elifnumNeigbors == NUM_NEIGHBORS_TO_BECOME_ALIVE:

newBoard[i][j] = ALIVE_CELL  # “dead” cell becomes alive

returnnewBoard

######################################################################

# turnOnCells() reprompts the user to enter coordinates of “alive”

#               cells for the initial configuration

#               until they enter ‘q’

# Input:        board;  a list of lists representing rows of

#                       the board

# Output:       board;  a list of lists representing rows of

#                       the board with alive cells set

defturnOnCells(board):

nRows, nCols = len(board), len(board[0])

enterCells = True

whileenterCells:

haveRow = False

while not haveRow:

print(”)

row = input(‘Please enter the row of a cell to turn on (or q to exit): ‘)

if row == ‘q’:

enterCells = False

break

row = int(row)

if row >= 0 and row <nRows:

haveRow = True

else:

print(‘That is not a valid value; please enter a number between 0 and ‘ + str(nRows – 1) + ‘ inclusive…’)

ifenterCells:

haveCol = False

while not haveCol:

col = input(‘Please enter a column for that cell: ‘)

col = int(col)

if col >= 0 and col <nCols:

haveCol = True

else:

print(‘That is not a valid value; please enter a number between 0 and ‘ + str(nCols – 1) + ‘ inclusive…’)

board

[row]

[col] = ALIVE_CELL

return board

######################################################################

# main function

#

def main():

nRows = getInteger(‘Please enter number of rows: ‘, 1)

nCols = getInteger(‘Please enter number of rolumns: ‘, 1)

board = emptyBoard(nRows, nCols)

board = turnOnCells(board)

nIter = getInteger(‘How many iterations should I run? ‘, 0)

print(‘Starting Board:’)

print(”)

printBoard(board)

for i in range(nIter):

print(”)

print(“Iteration ” + str(i + 1) + “:”)

print(”)

board = nextIteration(board)

printBoard(board)

main() 

Solution

# constants for the square’s walls layout

RIGHT = 0

BOTTOM = 1

LEFT = 2

TOP = 3

######################################################################

# getInteger() reprompts the user until they enter a number

#               greater than or equal to a minimum value and less

#               than or eaqual to a maximum value

# Input:        prompt;   string displayed to user

#               minVal;   integer of lower accepted range

#               maxVal;   integer of upper accepted range

# Output:       newInt;   integer greater in the range minVal ..maxVal

defgetInteger(prompt, minVal, maxVal):

newInt = int(input(prompt))

prompt = ‘Invalid, enter a number between ‘ + str(minVal) + ‘ and ‘ + str(maxVal) + ‘ (inclusive): ‘

whilenewInt<minVal or newInt>maxVal:

newInt = int(input(prompt))

returnnewInt

######################################################################

# getString()  reprompts the user until they enter a non-empty

#               string

# Input:        prompt;   string displayed to user

# Output:       newStr;   a string entered by user

defgetString(prompt):

newStr = input(prompt)

whilenewStr == ”:

newStr = input(prompt)

returnnewStr

######################################################################

# readMaze()  reads in the maze specification from the filename

#               specified, and returns a maze data structure and

#               “finish” square location

# Input:        filename;    a string with the name of the file

#                            specifying the maze

# Output:       maze;        a 3-dimensional list containing

#                            the maze structure

#               finishRow;   an integer indicating the row of

#                            the “finish” square

#               finishCol;   an integer indicating the column of

#                            the “finish” square

defreadMaze(filename):

fp = open(filename)

first = fp.readline()  # the number of rows and columns in the maze

nRows, nCols = first.strip().split()

nRows, nCols = int(nRows), int(nCols) # convert str to int

second = fp.readline() # the row and column position of the “finish”

finishRow, finishCol = second.strip().split()

finishRow, finishCol = int(finishRow), int(finishCol)

maze, row = [], []

# read the rest of the file (wall layout)

for line in fp:

square = [int(x) for x in line.strip().split()]

row.append(square)

iflen(row) == nCols:  # we have a full row of squares

maze.append(row)

row = []          # go to the next row

fp.close()

return maze, finishRow, finishCol

######################################################################

# searchMaze()   takes a maze data structure along with some

#                additional information. After it completes and all

#                of the recursion has ended, it returns either

#                a complete solution path (if it found one)

#                or None if there was no solution.

# Input:        maze;        a 3-dimensional list containing

#                            the maze structure

#               startRow;    an integer indicating the row of

#                            the “start” square

#               finishCol;   an integer indicating the column of

#                            the “start” square

#               finishRow;   an integer indicating the row of

#                            the “finish” square

#               finishCol;   an integer indicating the column of

#                            the “finish” square

#               path;        a list of location tuples indicating

#                            the path taken so far

# Output:       path;    a list of location tuples or None

defsearchMaze(maze, startRow, startCol, finishRow, finishCol, path):

path.append((startRow, startCol))   # add visited squareto the path

if (startRow, startCol) == (finishRow, finishCol):  # base case

return path     # path is found

else:

current = maze[startRow][startCol]   # current square

directions = [RIGHT, TOP, LEFT, BOTTOM]

# inices of RIGHT, TOP, LEFT and BOTTOM directions

indices = [(startRow, startCol + 1), (startRow – 1, startCol),

(startRow, startCol – 1), (startRow + 1, startCol)]

# loop over all opssible direction fron the current square

for i in range(len(directions)):

direction = directions[i]

row, col = indices[i]

# there is no wall in the direction and the square in

# the direction is not visited yet

if current[direction] == 0 and (row, col) not in path:

pathCopy = [pair for pair in path]   # deep copy of path

# recursive call

newPath = searchMaze(maze, row, col, finishRow, finishCol, pathCopy)

ifnewPath is not None: # path is found

returnnewPath

return None    # dead end: path not found

######################################################################

# main function

#

def main():

print(‘Welcome to the Maze Solver! ‘)

filename = getString(‘Please enter the filename of the maze: ‘)

maze, finishRow, finishCol = readMaze(filename)

startRow = getInteger(‘Please enter the starting row: ‘, 0, len(maze))

startCol = getInteger(‘Please enter the starting column: ‘, 0, len(maze[0]))

path = searchMaze(maze, startRow, startCol, finishRow, finishCol, [])

if path is None:

print(‘No solution found!’)

else:

print(‘Solution found! ‘)

for square in path:

print(square)

main()