iframe-proxy | Sunbelt Computer Software

History

118 lines (103 loc) · 3.17 KB

Raw

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

from typing import List

def solve_maze(maze: List[List[int]]) -> bool:

"""

This method solves the "rat in maze" problem.

In this problem we have some n by n matrix, a start point and an end point.

We want to go from the start to the end. In this matrix zeroes represent walls

and ones paths we can use.

Parameters :

maze(2D matrix) : maze

Returns:

Return: True if the maze has a solution or False if it does not.

>>> maze = [[0, 1, 0, 1, 1],

... [0, 0, 0, 0, 0],

... [1, 0, 1, 0, 1],

... [0, 0, 1, 0, 0],

... [1, 0, 0, 1, 0]]

>>> solve_maze(maze)

[1, 0, 0, 0, 0]

[1, 1, 1, 1, 0]

[0, 0, 0, 1, 0]

[0, 0, 0, 1, 1]

[0, 0, 0, 0, 1]

True

>>> maze = [[0, 1, 0, 1, 1],

... [0, 0, 0, 0, 0],

... [0, 0, 0, 0, 1],

... [0, 0, 0, 0, 0],

... [0, 0, 0, 0, 0]]

>>> solve_maze(maze)

[1, 0, 0, 0, 0]

[1, 1, 1, 1, 1]

True

>>> maze = [[0, 0, 0],

... [0, 1, 0],

... [1, 0, 0]]

>>> solve_maze(maze)

[1, 1, 1]

[0, 0, 1]

True

>>> maze = [[0, 1, 0],

... [0, 1, 0],

... [1, 0, 0]]

>>> solve_maze(maze)

No solution exists!

False

>>> maze = [[0, 1],

... [1, 0]]

>>> solve_maze(maze)

No solution exists!

False

"""

size = len(maze)

# We need to create solution object to save path.

solutions = [[0 for _ in range(size)] for _ in range(size)]

solved = run_maze(maze, 0, 0, solutions)

if solved:

print("\n".join(str(row) for row in solutions))

else:

print("No solution exists!")

return solved

def run_maze(maze: List[List[int]], i: int, j: int, solutions: List[List[int]]) -> bool:

"""

This method is recursive starting from (i, j) and going in one of four directions:

up, down, left, right.

If a path is found to destination it returns True otherwise it returns False.

Parameters:

maze(2D matrix) : maze

i, j : coordinates of matrix

solutions(2D matrix) : solutions

Returns:

Boolean if path is found True, Otherwise False.

"""

size = len(maze)

# Final check point.

if i == j == (size - 1):

solutions[i][j] = 1

return True

lower_flag = (not (i < 0)) and (not (j < 0)) # Check lower bounds

upper_flag = (i < size) and (j < size) # Check upper bounds

if lower_flag and upper_flag:

# check for already visited and block points.

block_flag = (not (solutions[i][j])) and (not (maze[i][j]))

if block_flag:

# check visited

solutions[i][j] = 1

# check for directions

if (

run_maze(maze, i + 1, j, solutions)

or run_maze(maze, i, j + 1, solutions)

or run_maze(maze, i - 1, j, solutions)

or run_maze(maze, i, j - 1, solutions)

return True

solutions[i][j] = 0

return False

if __name__ == "__main__":

import doctest

doctest.testmod()

Sunbelt Computer Software

PL/B Language Development and Support

Navigation Menu

Sunbelt Computer Software

PL/B Language Development and Support

FilesExpand file tree

rat_in_maze.py

Latest commit

History

rat_in_maze.py

File metadata and controls