Repository: TheAlgorithms/Java
Pull request #5576 (2024-10-05 05:10:50)

Add class documentation, improve comments in `MazeRecursion.java`
<!--
Thank you for your contribution!
In order to reduce the number of notifications sent to the maintainers, please:
- create your PR as draft, cf. https://docs.github.com/en/pull-requests/collaborating-with-pull-requests/proposing-changes-to-your-work-with-pull-requests/about-pull-requests#draft-pull-requests,
- make sure that all of the CI checks pass,
- mark your PR as ready for review, cf. https://docs.github.com/en/pull-requests/collaborating-with-pull-requests/proposing-changes-to-your-work-with-pull-requests/changing-the-stage-of-a-pull-request#marking-a-pull-request-as-ready-for-review
-->

<!-- For completed items, change [ ] to [x] -->

- [x] I have read [CONTRIBUTING.md](https://github.com/TheAlgorithms/Java/blob/master/CONTRIBUTING.md).
- [x] This pull request is all my own work -- I have not plagiarized it.
- [x] All filenames are in PascalCase.
- [x] All functions and variable names follow Java naming conventions.
- [x] All new algorithms have a URL in their comments that points to Wikipedia or other similar explanations.
- [x] All new code is formatted with `clang-format -i --style=file path/to/your/file.java`

codecov-commenter: ## [Codecov](https://app.codecov.io/gh/TheAlgorithms/Java/pull/5576?dropdown=coverage&src=pr&el=h1&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms) Report
Attention: Patch coverage is `45.45455%` with `12 lines` in your changes missing coverage. Please review.
> Project coverage is 53.96%. Comparing base [(`842ff52`)](https://app.codecov.io/gh/TheAlgorithms/Java/commit/842ff5294f5e97dfd1e4c09f9d9e01a89ac16e32?dropdown=coverage&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms) to head [(`ce9b917`)](https://app.codecov.io/gh/TheAlgorithms/Java/commit/ce9b917d7ff9fa90f880079bc9052471d3f33c0b?dropdown=coverage&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms).
> Report is 20 commits behind head on master.

| [Files with missing lines](https://app.codecov.io/gh/TheAlgorithms/Java/pull/5576?dropdown=coverage&src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms) | Patch % | Lines |
|---|---|---|
| [.../com/thealgorithms/backtracking/MazeRecursion.java](https://app.codecov.io/gh/TheAlgorithms/Java/pull/5576?src=pr&el=tree&filepath=src%2Fmain%2Fjava%2Fcom%2Fthealgorithms%2Fbacktracking%2FMazeRecursion.java&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms#diff-c3JjL21haW4vamF2YS9jb20vdGhlYWxnb3JpdGhtcy9iYWNrdHJhY2tpbmcvTWF6ZVJlY3Vyc2lvbi5qYXZh) | 45.45% | [10 Missing and 2 partials :warning: ](https://app.codecov.io/gh/TheAlgorithms/Java/pull/5576?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms) |

<details><summary>Additional details and impacted files</summary>


```diff
@@             Coverage Diff              @@
##             master    #5576      +/-   ##
============================================
+ Coverage     52.31%   53.96%   +1.65%     
- Complexity     3259     3387     +128     
============================================
  Files           526      535       +9     
  Lines         15205    15429     +224     
  Branches       2892     2942      +50     
============================================
+ Hits           7954     8327     +373     
+ Misses         6924     6749     -175     
- Partials        327      353      +26     
```

</details>

[:umbrella: View full report in Codecov by Sentry](https://app.codecov.io/gh/TheAlgorithms/Java/pull/5576?dropdown=coverage&src=pr&el=continue&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms).   
:loudspeaker: Have feedback on the report? [Share it here](https://about.codecov.io/codecov-pr-comment-feedback/?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms).

Hardvan: I modified the class to accept a maze as a parameter and return the solution instead of printing it. I also added JUnit tests to validate the functionality.

Patch:
diff --git a/src/main/java/com/thealgorithms/backtracking/MazeRecursion.java b/src/main/java/com/thealgorithms/backtracking/MazeRecursion.java
index f7eae01e..8247172e 100644
--- a/src/main/java/com/thealgorithms/backtracking/MazeRecursion.java
+++ b/src/main/java/com/thealgorithms/backtracking/MazeRecursion.java
@@ -1,152 +1,125 @@
 package com.thealgorithms.backtracking;
 
+/**
+ * This class contains methods to solve a maze using recursive backtracking.
+ * The maze is represented as a 2D array where walls, paths, and visited/dead
+ * ends are marked with different integers.
+ *
+ * The goal is to find a path from a starting position to the target position
+ * (map[6][5]) while navigating through the maze.
+ */
 public final class MazeRecursion {
+
     private MazeRecursion() {
     }
 
-    public static void mazeRecursion() {
-        // First create a 2 dimensions array to mimic a maze map
-        int[][] map = new int[8][7];
-        int[][] map2 = new int[8][7];
-
-        // We use 1 to indicate wall
-        // Set the ceiling and floor to 1
-        for (int i = 0; i < 7; i++) {
-            map[0][i] = 1;
-            map[7][i] = 1;
-        }
-
-        // Then we set the left and right wall to 1
-        for (int i = 0; i < 8; i++) {
-            map[i][0] = 1;
-            map[i][6] = 1;
-        }
-
-        // Now we have created a maze with its wall initialized
-
-        // Here we set the obstacle
-        map[3][1] = 1;
-        map[3][2] = 1;
-
-        // Print the current map
-        System.out.println("The condition of the map： ");
-        for (int i = 0; i < 8; i++) {
-            for (int j = 0; j < 7; j++) {
-                System.out.print(map[i][j] + " ");
-            }
-            System.out.println();
-        }
-
-        // clone another map for setWay2 method
-        for (int i = 0; i < map.length; i++) {
-            System.arraycopy(map[i], 0, map2[i], 0, map[i].length);
-        }
-
-        // By using recursive backtracking to let your ball(target) find its way in the
-        // maze
-        // The first parameter is the map
-        // Second parameter is x coordinate of your target
-        // Third parameter is the y coordinate of your target
-        setWay(map, 1, 1);
-        setWay2(map2, 1, 1);
-
-        // Print out the new map1, with the ball footprint
-        System.out.println("After the ball goes through the map1，show the current map1 condition");
-        for (int i = 0; i < 8; i++) {
-            for (int j = 0; j < 7; j++) {
-                System.out.print(map[i][j] + " ");
-            }
-            System.out.println();
+    /**
+     * This method solves the maze using the "down -> right -> up -> left"
+     * movement strategy.
+     *
+     * @param map The 2D array representing the maze (walls, paths, etc.)
+     * @return The solved maze with paths marked, or null if no solution exists.
+     */
+    public static int[][] solveMazeUsingFirstStrategy(int[][] map) {
+        if (setWay(map, 1, 1)) {
+            return map;
         }
+        return null;
+    }
 
-        // Print out the new map2, with the ball footprint
-        System.out.println("After the ball goes through the map2，show the current map2 condition");
-        for (int i = 0; i < 8; i++) {
-            for (int j = 0; j < 7; j++) {
-                System.out.print(map2[i][j] + " ");
-            }
-            System.out.println();
+    /**
+     * This method solves the maze using the "up -> right -> down -> left"
+     * movement strategy.
+     *
+     * @param map The 2D array representing the maze (walls, paths, etc.)
+     * @return The solved maze with paths marked, or null if no solution exists.
+     */
+    public static int[][] solveMazeUsingSecondStrategy(int[][] map) {
+        if (setWay2(map, 1, 1)) {
+            return map;
         }
+        return null;
     }
 
     /**
-     * Using recursive path finding to help the ball find its way in the maze
-     * Description：
-     * 1. map (means the maze)
-     * 2. i, j (means the initial coordinate of the ball in the maze)
-     * 3. if the ball can reach the end of maze, that is position of map[6][5],
-     * means the we have found a path for the ball
-     * 4. Additional Information： 0 in the map[i][j] means the ball has not gone
-     * through this position, 1 means the wall, 2 means the path is feasible, 3
-     * means the ball has gone through the path but this path is dead end
-     * 5. We will need strategy for the ball to pass through the maze for example:
-     * Down -> Right -> Up -> Left, if the path doesn't work, then backtrack
+     * Attempts to find a path through the maze using a "down -> right -> up -> left"
+     * movement strategy. The path is marked with '2' for valid paths and '3' for dead ends.
      *
-     * @author OngLipWei
-     * @version Jun 23, 2021 11:36:14 AM
-     * @param map The maze
-     * @param i   x coordinate of your ball(target)
-     * @param j   y coordinate of your ball(target)
-     * @return If we did find a path for the ball，return true，else false
+     * @param map The 2D array representing the maze (walls, paths, etc.)
+     * @param i   The current x-coordinate of the ball (row index)
+     * @param j   The current y-coordinate of the ball (column index)
+     * @return True if a path is found to (6,5), otherwise false
      */
-    public static boolean setWay(int[][] map, int i, int j) {
-        if (map[6][5] == 2) { // means the ball find its path, ending condition
+    private static boolean setWay(int[][] map, int i, int j) {
+        if (map[6][5] == 2) {
             return true;
         }
-        if (map[i][j] == 0) { // if the ball haven't gone through this point
-            // then the ball follows the move strategy : down -> right -> up -> left
-            map[i][j] = 2; // we assume that this path is feasible first, set the current point to 2
-                           // first。
-            if (setWay(map, i + 1, j)) { // go down
+
+        // If the current position is unvisited (0), explore it
+        if (map[i][j] == 0) {
+            // Mark the current position as '2'
+            map[i][j] = 2;
+
+            // Move down
+            if (setWay(map, i + 1, j)) {
                 return true;
-            } else if (setWay(map, i, j + 1)) { // go right
+            }
+            // Move right
+            else if (setWay(map, i, j + 1)) {
                 return true;
-            } else if (setWay(map, i - 1, j)) { // go up
+            }
+            // Move up
+            else if (setWay(map, i - 1, j)) {
                 return true;
-            } else if (setWay(map, i, j - 1)) { // go left
+            }
+            // Move left
+            else if (setWay(map, i, j - 1)) {
                 return true;
-            } else {
-                // means that the current point is the dead end, the ball cannot proceed, set
-                // the current point to 3 and return false, the backtracking will start, it will
-                // go to the previous step and check for feasible path again
-                map[i][j] = 3;
-                return false;
             }
-        } else { // if the map[i][j] != 0 , it will probably be 1,2,3, return false because the
-            // ball cannot hit the wall, cannot go to the path that has gone though before,
-            // and cannot head to deadened.
+
+            map[i][j] = 3; // Mark as dead end (3) if no direction worked
             return false;
         }
+        return false;
     }
 
-    // Here is another move strategy for the ball: up->right->down->left
-    public static boolean setWay2(int[][] map, int i, int j) {
-        if (map[6][5] == 2) { // means the ball find its path, ending condition
+    /**
+     * Attempts to find a path through the maze using an alternative movement
+     * strategy "up -> right -> down -> left".
+     *
+     * @param map The 2D array representing the maze (walls, paths, etc.)
+     * @param i   The current x-coordinate of the ball (row index)
+     * @param j   The current y-coordinate of the ball (column index)
+     * @return True if a path is found to (6,5), otherwise false
+     */
+    private static boolean setWay2(int[][] map, int i, int j) {
+        if (map[6][5] == 2) {
             return true;
         }
-        if (map[i][j] == 0) { // if the ball haven't gone through this point
-            // then the ball follows the move strategy : up->right->down->left
-            map[i][j] = 2; // we assume that this path is feasible first, set the current point to 2
-                           // first。
-            if (setWay2(map, i - 1, j)) { // go up
+
+        if (map[i][j] == 0) {
+            map[i][j] = 2;
+
+            // Move up
+            if (setWay2(map, i - 1, j)) {
                 return true;
-            } else if (setWay2(map, i, j + 1)) { // go right
+            }
+            // Move right
+            else if (setWay2(map, i, j + 1)) {
                 return true;
-            } else if (setWay2(map, i + 1, j)) { // go down
+            }
+            // Move down
+            else if (setWay2(map, i + 1, j)) {
                 return true;
-            } else if (setWay2(map, i, j - 1)) { // go left
+            }
+            // Move left
+            else if (setWay2(map, i, j - 1)) {
                 return true;
-            } else {
-                // means that the current point is the dead end, the ball cannot proceed, set
-                // the current point to 3 and return false, the backtracking will start, it will
-                // go to the previous step and check for feasible path again
-                map[i][j] = 3;
-                return false;
             }
-        } else { // if the map[i][j] != 0 , it will probably be 1,2,3, return false because the
-            // ball cannot hit the wall, cannot go to the path that has gone through before,
-            // and cannot head to deadend.
+
+            map[i][j] = 3; // Mark as dead end (3) if no direction worked
             return false;
         }
+        return false;
     }
 }


Test patch:
diff --git a/src/test/java/com/thealgorithms/backtracking/MazeRecursionTest.java b/src/test/java/com/thealgorithms/backtracking/MazeRecursionTest.java
index edaca14a..b8e77fb3 100644
--- a/src/test/java/com/thealgorithms/backtracking/MazeRecursionTest.java
+++ b/src/test/java/com/thealgorithms/backtracking/MazeRecursionTest.java
@@ -11,41 +11,35 @@ import org.junit.jupiter.api.Test;
 public class MazeRecursionTest {
 
     @Test
-    public void testMaze() {
-        // First create a 2 dimensions array to mimic a maze map
+    public void testSolveMazeUsingFirstAndSecondStrategy() {
         int[][] map = new int[8][7];
         int[][] map2 = new int[8][7];
 
-        // We use 1 to indicate wall
+        // We use 1 to indicate walls
         // Set the ceiling and floor to 1
         for (int i = 0; i < 7; i++) {
             map[0][i] = 1;
             map[7][i] = 1;
         }
-
-        // Then we set the left and right wall to 1
+        // Set the left and right wall to 1
         for (int i = 0; i < 8; i++) {
             map[i][0] = 1;
             map[i][6] = 1;
         }
-
-        // Now we have created a maze with its wall initialized
-
-        // Here we set the obstacle
+        // Set obstacles
         map[3][1] = 1;
         map[3][2] = 1;
 
-        // clone another map for setWay2 method
+        // Clone the original map for the second pathfinding strategy
         for (int i = 0; i < map.length; i++) {
-            for (int j = 0; j < map[i].length; j++) {
-                map2[i][j] = map[i][j];
-            }
+            System.arraycopy(map[i], 0, map2[i], 0, map[i].length);
         }
 
-        MazeRecursion.setWay(map, 1, 1);
-        MazeRecursion.setWay2(map2, 1, 1);
-
-        int[][] expectedMap = new int[][] {
+        // Solve the maze using the first strategy
+        int[][] solvedMap1 = MazeRecursion.solveMazeUsingFirstStrategy(map);
+        // Solve the maze using the second strategy
+        int[][] solvedMap2 = MazeRecursion.solveMazeUsingSecondStrategy(map2);
+        int[][] expectedMap1 = new int[][] {
             {1, 1, 1, 1, 1, 1, 1},
             {1, 2, 0, 0, 0, 0, 1},
             {1, 2, 2, 2, 0, 0, 1},
@@ -55,7 +49,6 @@ public class MazeRecursionTest {
             {1, 0, 0, 2, 2, 2, 1},
             {1, 1, 1, 1, 1, 1, 1},
         };
-
         int[][] expectedMap2 = new int[][] {
             {1, 1, 1, 1, 1, 1, 1},
             {1, 2, 2, 2, 2, 2, 1},
@@ -67,7 +60,8 @@ public class MazeRecursionTest {
             {1, 1, 1, 1, 1, 1, 1},
         };
 
-        assertArrayEquals(map, expectedMap);
-        assertArrayEquals(map2, expectedMap2);
+        // Assert the results
+        assertArrayEquals(expectedMap1, solvedMap1);
+        assertArrayEquals(expectedMap2, solvedMap2);
     }
 }