Use recursive backtracking to solve rat in a maze problem

Last updated on September 3, 2023 pm

Problem and background

Given a maze[][] of n * m matrix, a rat has to find a path from source to destination.

Use a recursive method to find the exit route of the maze.

Backtracking is a versatile algorithm used to find solutions for computational problems, particularly constraint satisfaction problems. It works by progressively generating potential solutions and discarding them (“backtracking”) as soon as it becomes clear that they cannot lead to a correct answer.

/** * find a route simply without considering the shortest route * * @param map maze * @param i current location x * @param j current location y * @return if the current location is the exit */ publicstaticbooleansetWay(int[][] map, int i, int j) { // 1. started from (1,1) // 2. exit at (6,5) // 3. value 0 represents unexplored path, 1 represents walls, // 2 represents a clear path, and 3 represents a dead end. // 4. When exploring the maze, we follow the order of // down -> right -> up -> left if (map[6][4] == 2) { returntrue; //find the exit } else { if (map[i][j] == 0) { // unexplored path map[i][j] = 2; // assuming that this point is accessible.

if (setWay(map, i + 1, j)) { //down returntrue; } elseif (setWay(map, i, j + 1)) { //right returntrue; } elseif (setWay(map, i - 1, j)) { //up returntrue; } elseif (setWay(map, i, j - 1)) { //left returntrue; } else { //it is a dead end map[i][j] = 3; returnfalse; } } else { // 1, 2 or 3, means explored returnfalse; } } }

show the situation of maze

1 2 3 4 5 6 7 8 9

publicstaticvoidshowMap(int[][] map){ //output the maze for (inti=0; i < 8; i++) { for (intj=0; j < 7; j++) { System.out.print(map[i][j] + " "); } System.out.println(); } }