this method solves the rat in maze problem parameters maze a two dimensional matrix of zeros and ones sourcerow the row index of the starting point sourcecolumn the column index of the starting point destinationrow the row index of the destination point destinationcolumn 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 solvemazemaze 0 0 lenmaze1 lenmaze1 doctest normalizewhitespace 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 solvemazemaze 0 0 lenmaze1 lenmaze1 doctest normalizewhitespace 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 solvemazemaze 0 0 lenmaze1 lenmaze1 doctest normalizewhitespace 0 0 0 1 1 0 1 1 0 maze 1 0 0 0 1 0 1 0 0 solvemazemaze 0 1 lenmaze1 lenmaze1 doctest normalizewhitespace 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 solvemazemaze 0 2 lenmaze1 2 doctest normalizewhitespace 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 solvemazemaze 0 1 lenmaze1 lenmaze1 traceback most recent call last valueerror no solution exists maze 0 0 1 1 solvemazemaze 0 0 lenmaze1 lenmaze1 traceback most recent call last valueerror no solution exists maze 0 1 1 0 solvemazemaze 2 0 lenmaze1 lenmaze1 traceback most recent call last valueerror invalid source or destination coordinates maze 1 0 0 0 1 0 1 0 0 solvemazemaze 0 1 lenmaze lenmaze1 traceback most recent call last valueerror invalid source or destination coordinates check if source and destination coordinates are invalid we need to create solution object to save path 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 final check point check for already visited and block points check visited check for directions 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 doctest normalize_whitespace 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 doctest normalize_whitespace 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 doctest normalize_whitespace 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 doctest normalize_whitespace 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 doctest normalize_whitespace 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 check if source and destination coordinates are invalid we need to create solution object to save path 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 final check point check lower bounds check upper bounds check for already visited and block points check visited check for directions
from __future__ import annotations


def solve_maze(
    maze: list[list[int]],
    source_row: int,
    source_column: int,
    destination_row: int,
    destination_column: int,
) -> list[list[int]]:
    
    size = len(maze)
    
    if not (0 <= source_row <= size - 1 and 0 <= source_column <= size - 1) or (
        not (0 <= destination_row <= size - 1 and 0 <= destination_column <= size - 1)
    ):
        raise ValueError("Invalid source or destination coordinates")
    
    solutions = [[1 for _ in range(size)] for _ in range(size)]
    solved = run_maze(
        maze, source_row, source_column, destination_row, destination_column, solutions
    )
    if solved:
        return solutions
    else:
        raise ValueError("No solution exists!")


def run_maze(
    maze: list[list[int]],
    i: int,
    j: int,
    destination_row: int,
    destination_column: int,
    solutions: list[list[int]],
) -> bool:
    
    size = len(maze)
    
    if i == destination_row and j == destination_column and maze[i][j] == 0:
        solutions[i][j] = 0
        return True

    lower_flag = (not i < 0) and (not j < 0)  
    upper_flag = (i < size) and (j < size)  

    if lower_flag and upper_flag:
        
        block_flag = (solutions[i][j]) and (not maze[i][j])
        if block_flag:
            
            solutions[i][j] = 0

            
            if (
                run_maze(maze, i + 1, j, destination_row, destination_column, solutions)
                or run_maze(
                    maze, i, j + 1, destination_row, destination_column, solutions
                )
                or run_maze(
                    maze, i - 1, j, destination_row, destination_column, solutions
                )
                or run_maze(
                    maze, i, j - 1, destination_row, destination_column, solutions
                )
            ):
                return True

            solutions[i][j] = 1
            return False
    return False


if __name__ == "__main__":
    import doctest

    doctest.testmod(optionflags=doctest.NORMALIZE_WHITESPACE)