Skip to content

Commit d63813e

Browse files
hahaonghahaong
authored
Add maze recursion algorithm (TheAlgorithms#3204)
1 parent d82a200 commit d63813e

File tree

2 files changed

+236
-0
lines changed

2 files changed

+236
-0
lines changed

‎src/main/java/com/thealgorithms/backtracking/MazeRecursion.java‎

Lines changed: 158 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,158 @@
1+
package com.thealgorithms.backtracking;
2+
3+
public class MazeRecursion {
4+
5+
public static void mazeRecursion() {
6+
// First create a 2 dimensions array to mimic a maze map
7+
int[][] map = new int[8][7];
8+
int[][] map2 = new int[8][7];
9+
10+
// We use 1 to indicate wall
11+
// Set the ceiling and floor to 1
12+
for (int i = 0; i < 7; i++) {
13+
map[0][i] = 1;
14+
map[7][i] = 1;
15+
}
16+
17+
// Then we set the left and right wall to 1
18+
for (int i = 0; i < 8; i++) {
19+
map[i][0] = 1;
20+
map[i][6] = 1;
21+
}
22+
23+
// Now we have created a maze with its wall initialized
24+
25+
// Here we set the obstacle
26+
map[3][1] = 1;
27+
map[3][2] = 1;
28+
29+
// Print the current map
30+
System.out.println("The condition of the map： ");
31+
for (int i = 0; i < 8; i++) {
32+
for (int j = 0; j < 7; j++) {
33+
System.out.print(map[i][j] + " ");
34+
}
35+
System.out.println();
36+
}
37+
38+
// clone another map for setWay2 method
39+
for (int i = 0; i < map.length; i++) {
40+
for (int j = 0; j < map[i].length; j++) {
41+
map2[i][j] = map[i][j];
42+
}
43+
}
44+
45+
// By using recursive backtracking to let your ball(target) find its way in the
46+
// maze
47+
// The first parameter is the map
48+
// Second parameter is x coordinate of your target
49+
// Thrid parameter is the y coordinate of your target
50+
setWay(map, 1, 1);
51+
setWay2(map2, 1, 1);
52+
53+
// Print out the new map1, with the ball footprint
54+
System.out.println("After the ball goes through the map1，show the current map1 condition");
55+
for (int i = 0; i < 8; i++) {
56+
for (int j = 0; j < 7; j++) {
57+
System.out.print(map[i][j] + " ");
58+
}
59+
System.out.println();
60+
}
61+
62+
// Print out the new map2, with the ball footprint
63+
System.out.println("After the ball goes through the map2，show the current map2 condition");
64+
for (int i = 0; i < 8; i++) {
65+
for (int j = 0; j < 7; j++) {
66+
System.out.print(map2[i][j] + " ");
67+
}
68+
System.out.println();
69+
}
70+
}
71+
72+
73+
74+
// Using recursive path finding to help the ball find its way in the maze
75+
// Description：
76+
// 1. map (means the maze)
77+
// 2. i, j (means the initial coordinate of the ball in the maze)
78+
// 3. if the ball can reach the end of maze, that is position of map[6][5],
79+
// means the we have found a path for the ball
80+
// 4. Additional Information： 0 in the map[i][j] means the ball has not gone
81+
// through this position, 1 means the wall, 2 means the path is feasible, 3
82+
// means the ball has gone through the path but this path is dead end
83+
// 5. We will need strategy for the ball to pass through the maze for example:
84+
// Down -> Right -> Up -> Left, if the path doesn't work, then backtrack
85+
/**
86+
*
87+
* @Description
88+
* @author OngLipWei
89+
* @date Jun 23, 202111:36:14 AM
90+
* @param map The maze
91+
* @param i x coordinate of your ball(target)
92+
* @param j y coordinate of your ball(target)
93+
* @return If we did find a path for the ball，return true，else false
94+
*/
95+
public static boolean setWay(int[][] map, int i, int j) {
96+
if (map[6][5] == 2) {// means the ball find its path, ending condition
97+
return true;
98+
}
99+
if (map[i][j] == 0) { // if the ball haven't gone through this point
100+
// then the ball follows the move strategy : down -> right -> up -> left
101+
map[i][j] = 2; // we assume that this path is feasible first, set the current point to 2 first。
102+
if (setWay(map, i + 1, j)) { // go down
103+
return true;
104+
} else if (setWay(map, i, j + 1)) { // go right
105+
return true;
106+
} else if (setWay(map, i - 1, j)) { // go up
107+
return true;
108+
} else if (setWay(map, i, j - 1)) { // go left
109+
return true;
110+
} else {
111+
// means that the current point is the dead end, the ball cannot proceed, set
112+
// the current point to 3 and return false, the backtraking will start, it will
113+
// go to the previous step and check for feasible path again
114+
map[i][j] = 3;
115+
return false;
116+
}
117+
118+
} else { // if the map[i][j] != 0 , it will probably be 1,2,3, return false because the
119+
// ball cannot hit the wall, cannot go to the path that has gone though before,
120+
// and cannot head to deadend.
121+
return false;
122+
}
123+
124+
}
125+
126+
// Here is another move strategy for the ball: up->right->down->left
127+
public static boolean setWay2(int[][] map, int i, int j) {
128+
if (map[6][5] == 2) {// means the ball find its path, ending condition
129+
return true;
130+
}
131+
if (map[i][j] == 0) { // if the ball haven't gone through this point
132+
// then the ball follows the move strategy : up->right->down->left
133+
map[i][j] = 2; // we assume that this path is feasible first, set the current point to 2 first。
134+
if (setWay2(map, i - 1, j)) { // go up
135+
return true;
136+
} else if (setWay2(map, i, j + 1)) { // go right
137+
return true;
138+
} else if (setWay2(map, i + 1, j)) { // go down
139+
return true;
140+
} else if (setWay2(map, i, j - 1)) { // go left
141+
return true;
142+
} else {
143+
// means that the current point is the dead end, the ball cannot proceed, set
144+
// the current point to 3 and return false, the backtraking will start, it will
145+
// go to the previous step and check for feasible path again
146+
map[i][j] = 3;
147+
return false;
148+
}
149+
150+
} else { // if the map[i][j] != 0 , it will probably be 1,2,3, return false because the
151+
// ball cannot hit the wall, cannot go to the path that has gone though before,
152+
// and cannot head to deadend.
153+
return false;
154+
}
155+
156+
}
157+
158+
}

‎src/test/java/com/thealgorithms/backtracking/MazeRecursionTest.java‎

Lines changed: 78 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,78 @@
1+
package com.thealgorithms.backtracking;
2+
3+
import org.junit.jupiter.api.Test;
4+
import static org.junit.jupiter.api.Assertions.*;
5+
6+
/**
7+
* @author onglipwei
8+
* @create 2022-08-03 5:17 AM
9+
*/
10+
public class MazeRecursionTest {
11+
12+
@Test
13+
public void testMaze() {
14+
15+
16+
// First create a 2 dimensions array to mimic a maze map
17+
int[][] map = new int[8][7];
18+
int[][] map2 = new int[8][7];
19+
20+
// We use 1 to indicate wall
21+
// Set the ceiling and floor to 1
22+
for (int i = 0; i < 7; i++) {
23+
map[0][i] = 1;
24+
map[7][i] = 1;
25+
}
26+
27+
// Then we set the left and right wall to 1
28+
for (int i = 0; i < 8; i++) {
29+
map[i][0] = 1;
30+
map[i][6] = 1;
31+
32+
}
33+
34+
// Now we have created a maze with its wall initialized
35+
36+
// Here we set the obstacle
37+
map[3][1] = 1;
38+
map[3][2] = 1;
39+
40+
//clone another map for setWay2 method
41+
for (int i = 0; i < map.length;i++) {
42+
for (int j = 0; j < map[i].length;j++) {
43+
map2[i][j]=map[i][j];
44+
}
45+
}
46+
47+
MazeRecursion.setWay(map, 1, 1);
48+
MazeRecursion.setWay2(map2, 1, 1);
49+
50+
51+
int expectedMap[][] = new int[][]{
52+
{1,1,1,1,1,1,1},
53+
{1,2,0,0,0,0,1},
54+
{1,2,2,2,0,0,1},
55+
{1,1,1,2,0,0,1},
56+
{1,0,0,2,0,0,1},
57+
{1,0,0,2,0,0,1},
58+
{1,0,0,2,2,2,1},
59+
{1,1,1,1,1,1,1}
60+
};
61+
62+
int expectedMap2[][] = new int[][]{
63+
{1,1,1,1,1,1,1},
64+
{1,2,2,2,2,2,1},
65+
{1,0,0,0,0,2,1},
66+
{1,1,1,0,0,2,1},
67+
{1,0,0,0,0,2,1},
68+
{1,0,0,0,0,2,1},
69+
{1,0,0,0,0,2,1},
70+
{1,1,1,1,1,1,1}
71+
};
72+
73+
assertArrayEquals(map, expectedMap);
74+
assertArrayEquals(map2, expectedMap2);
75+
76+
}
77+
78+
}

0 commit comments

Comments
 (0)