backtracking.rat_in_maze
========================

.. py:module:: backtracking.rat_in_maze


Functions
---------

.. autoapisummary::

   backtracking.rat_in_maze.run_maze
   backtracking.rat_in_maze.solve_maze


Module Contents
---------------

.. py:function:: 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.


.. py:function:: 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)    # 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