Solving Maze

Problem Statement:
(Rat in a Maze)
       A maze with '0's and '1's , find a contiguous path from top left to bottom right corner of the maze. The path can only be traversed in the right or bottom direction with respect to every cell of the matrix.

The output matrix for the corresponding maze will be

Solution:

This problem is commonly called as "Rat in a Maze" , the problem deals with backtracking of the path.  A '0' in the maze indicates a wall and a '1' indicates existence of path.

This problem can be solved iteratively but we will propose a recursive approach here.
Our goal is to find a recursive approach that simplifies the problem starting from smaller to bigger problem.  Once you have made the simplification for the smaller problem, you use the same process to solve each of the resulting sub-problems.

Possible move from every cell is
1. Down
2. Right
3. Left
4. Up

For every cell in the maze , maze[row][col]= 0/1

Pls refer to the Source Code

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55

/** * Recursive subroutine for the path * @param maze * : input maze * @param solution * : solution of maze * @param row * : current row * @param col * : current col */ private void solveMaze(int maze[][], int solution[][], int row, int col) { // exit gate reached if (row == rowLen && col == colLen) { solution[row][col] = 1; printSolution(solution); this.isSolvale = true; } // Move Down if (row < rowLen) { if (maze[row + 1][col] == 1) { solution[row][col] = 1; solveMaze(maze, solution, row + 1, col); solution[row][col] = 0; } } // Move Right if (col < colLen) { if (maze[row][col + 1] == 1) { solution[row][col] = 1; solveMaze(maze, solution, row, col + 1); solution[row][col] = 0; } } } private void printSolution(int[][] solution) { int rLen = solution.length; int cLen = solution[0].length; System.out.println("The Path matrix is : "); for (int i = 0; i < rLen; i++) { for (int j = 0; j < cLen; j++) System.out.print(solution[i][j] + "\t"); System.out.println(); } }

References: https://www.youtube.com/watch?v=keb6rP07Yqg