backtracking.rat_in_maze

Functions

run_maze(→ bool)	This method is recursive starting from (i, j) and going in one of four directions:
solve_maze(→ list[list[int]])	This method solves the "rat in maze" problem.

Module Contents

backtracking.rat_in_maze.run_maze(maze: list[list[int]], i: int, j: int, destination_row: int, destination_column: 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: A two dimensional matrix of zeros and ones. i, j : coordinates of matrix solutions: A two dimensional matrix of solutions.

Returns:

Boolean if path is found True, Otherwise False.

backtracking.rat_in_maze.solve_maze(maze: list[list[int]], source_row: int, source_column: int, destination_row: int, destination_column: int) → list[list[int]]

This method solves the “rat in maze” problem. Parameters :

• maze: A two dimensional matrix of zeros and ones.

• source_row: The row index of the starting point.

• source_column: The column index of the starting point.

• destination_row: The row index of the destination point.

• destination_column: The column index of the destination point.

Returns:

• solution: A 2D matrix representing the solution path if it exists.

Raises:

• ValueError: If no solution exists or if the source or

  destination coordinates are invalid.

Description:

This method navigates through a maze represented as an n by n matrix, starting from a specified source cell and aiming to reach a destination cell. The maze consists of walls (1s) and open paths (0s). By providing custom row and column values, the source and destination cells can be adjusted.

>>> 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,0,0,len(maze)-1,len(maze)-1)    
[[0, 1, 1, 1, 1],
[0, 0, 0, 0, 1],
[1, 1, 1, 0, 1],
[1, 1, 1, 0, 0],
[1, 1, 1, 1, 0]]

Note:

In the output maze, the zeros (0s) represent one of the possible paths from the source to the destination.

>>> 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,0,0,len(maze)-1,len(maze)-1)    
[[0, 1, 1, 1, 1],
[0, 1, 1, 1, 1],
[0, 1, 1, 1, 1],
[0, 1, 1, 1, 1],
[0, 0, 0, 0, 0]]

>>> maze = [[0, 0, 0],
...         [0, 1, 0],
...         [1, 0, 0]]
>>> solve_maze(maze,0,0,len(maze)-1,len(maze)-1)    
[[0, 0, 0],
[1, 1, 0],
[1, 1, 0]]

>>> maze = [[1, 0, 0],
...         [0, 1, 0],
...         [1, 0, 0]]
>>> solve_maze(maze,0,1,len(maze)-1,len(maze)-1)    
[[1, 0, 0],
[1, 1, 0],
[1, 1, 0]]

>>> maze = [[1, 1, 0, 0, 1, 0, 0, 1],
...         [1, 0, 1, 0, 0, 1, 1, 1],
...         [0, 1, 0, 1, 0, 0, 1, 0],
...         [1, 1, 1, 0, 0, 1, 0, 1],
...         [0, 1, 0, 0, 1, 0, 1, 1],
...         [0, 0, 0, 1, 1, 1, 0, 1],
...         [0, 1, 0, 1, 0, 1, 1, 1],
...         [1, 1, 0, 0, 0, 0, 0, 1]]
>>> solve_maze(maze,0,2,len(maze)-1,2)  
[[1, 1, 0, 0, 1, 1, 1, 1],
[1, 1, 1, 0, 0, 1, 1, 1],
[1, 1, 1, 1, 0, 1, 1, 1],
[1, 1, 1, 0, 0, 1, 1, 1],
[1, 1, 0, 0, 1, 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]]
>>> maze = [[1, 0, 0],
...         [0, 1, 1],
...         [1, 0, 1]]
>>> solve_maze(maze,0,1,len(maze)-1,len(maze)-1)
Traceback (most recent call last):
    ...
ValueError: No solution exists!

>>> maze = [[0, 0],
...         [1, 1]]
>>> solve_maze(maze,0,0,len(maze)-1,len(maze)-1)
Traceback (most recent call last):
    ...
ValueError: No solution exists!

>>> maze = [[0, 1],
...         [1, 0]]
>>> solve_maze(maze,2,0,len(maze)-1,len(maze)-1)
Traceback (most recent call last):
    ...
ValueError: Invalid source or destination coordinates

>>> maze = [[1, 0, 0],
...         [0, 1, 0],
...         [1, 0, 0]]
>>> solve_maze(maze,0,1,len(maze),len(maze)-1)
Traceback (most recent call last):
    ...
ValueError: Invalid source or destination coordinates