python · Ayushparikh-code · May 26, 2021 · May 26, 2021 · May 28, 2021 · May 28, 2021
diff --git a/Misc/NEWS.d/next/Tools-Demos/2021-08-29-17-56-41.bpo-45047.65rFIn.rst b/Misc/NEWS.d/next/Tools-Demos/2021-08-29-17-56-41.bpo-45047.65rFIn.rst
@@ -0,0 +1 @@
+Rat in a Maze Problem
diff --git a/Tools/demo/RatinMaze.py b/Tools/demo/RatinMaze.py
@@ -0,0 +1,110 @@
+def solve_maze(maze: list) -> 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, 0, 0, 0, 0]
+    [1, 0, 0, 0, 0]
+    [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]
+    [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, i, j, solutions):
+    """
+    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()