| 25 | return True |
| 26 | |
| 27 | def solveMazeUtil(maze, x, y, sol): |
| 28 | # if (x, y is goal) return True |
| 29 | if x == N - 1 and y == N - 1: |
| 30 | sol[x][y] = 1 |
| 31 | return True |
| 32 | |
| 33 | # Check if maze[x][y] is valid |
| 34 | if isSafe(maze, x, y) == True: |
| 35 | # mark x, y as part of solution path |
| 36 | sol[x][y] = 1 |
| 37 | |
| 38 | # Move forward in x direction |
| 39 | if solveMazeUtil(maze, x + 1, y, sol) == True: |
| 40 | return True |
| 41 | |
| 42 | # If moving in x direction doesn't give solution |
| 43 | # then Move down in y direction |
| 44 | if solveMazeUtil(maze, x, y + 1, sol) == True: |
| 45 | return True |
| 46 | |
| 47 | # If none of the above movements work then |
| 48 | # BACKTRACK: unmark x, y as part of solution path |
| 49 | sol[x][y] = 0 |
| 50 | return False |
| 51 | |
| 52 | # Main Program |
| 53 | if __name__ == "__main__": |