Maze Navigation using Recursion And Backtracking

[Ryang027]

The task is simple, create a Maze class that can navigate any MxN maze, with a starting position of (0,0) and an exit at (m,n). Each space visited must be marked with a 3, and then when finished, the correct path should be labeled as a 7.

Here is my Maze class.

import java.util.*;
import java.io.*;

public class Maze
{
private int rows, cols;
private char path;
private char wall;
private char[][] maze;

//Constructor
public Maze(int r, int c, char p, char w)
{
rows = r;
cols = c;
path = p;
wall = w;
maze = new char[rows][cols];
}//end Constructor

//Fills the maze by reading in a data file
public void fillMaze() throws FileNotFoundException
{
Scanner scan = new Scanner(System.in);

System.out.println("Enter the name of the maze file including the extension: ");
String name = scan.next();
File file = new File(name);

Scanner infile = new Scanner(file);

//int total = this.rows + this.cols;

for(int x=0; x<this.rows; x++)
{
for(int y=0; y<this.cols; y++)
this.maze[x][y] = infile.next().charAt(0);
}


}//End fillMaze

//Prints the maze
public void printMaze()
{
for(int x=0; x<this.rows; x++)
{
for(int y=0; y<this.cols; y++)
System.out.print(maze[x][y] + " " );
System.out.println();
}
}//End printMaze

//Traverses the maze
public Boolean traverseMaze(int row, int col)
{
Boolean move = false;

//If attempted move is outside the maze
if(row<0 || row>this.rows-1 || col<0 || col>this.cols-1)
return false;

//If current position is at the end of the maze
if(row == this.rows && col == this.cols)
{
move = true;
this.maze[row][col] = '7';
return move;
}

//If attempted move is a wall
if(this.maze[row][col] == this.wall)
return false;

//If already visited
if(this.maze[row][col] == '3')
return false;


this.maze[row][col] = '3';


move = traverseMaze(row+1, col); // down
move = traverseMaze(row, col+1); // right
move = traverseMaze(row-1, col); //up
move = traverseMaze(row, col-1); //left

this.maze[row][col] = '7';

return move;
}//end traverseMaze
}



Then here is the maze before and after the navigation.

B A A A A A A A A A A A A A A
B A B B B A A A A A A A A A A
B A B A B B A B B B B B A A A
B B B A A B A A A B A A A A A
B A A A A B A A A B A A A A A
B A A A A B A A A B A A A A A
B A A A A B B B B B B B B A A
B A A A A A B A A A A A B A A
B B B A A A B A A A A A B A A
A A B A A B B A A A A A B A A
A A B A A B A A A A A A B A A
A A B A A B B B A B A A B A A
A A A A B B A B A B A A B A A
A A A A B A A B B B A A B B A
A A A A B A A A A A A A A B A
A A A B B A A A A A A A A B A
A A A A A A A A A A A A A B B
A A A A A A A A A A A A A A B

7 A A A A A A A A A A A A A A
7 A 7 7 7 A A A A A A A A A A
7 A 7 A 7 7 A 7 7 7 7 7 A A A
7 7 7 A A 7 A A A 7 A A A A A
7 A A A A 7 A A A 7 A A A A A
7 A A A A 7 A A A 7 A A A A A
7 A A A A 7 7 7 7 7 7 7 7 A A
7 A A A A A 7 A A A A A 7 A A
7 7 7 A A A 7 A A A A A 7 A A
A A 7 A A 7 7 A A A A A 7 A A
A A 7 A A 7 A A A A A A 7 A A
A A 7 A A 7 7 7 A 7 A A 7 A A
A A A A 7 7 A 7 A 7 A A 7 A A
A A A A 7 A A 7 7 7 A A 7 7 A
A A A A 7 A A A A A A A A 7 A
A A A 7 7 A A A A A A A A 7 A
A A A A A A A A A A A A A 7 7
A A A A A A A A A A A A A A 7


As you can see, the program successfully navigates the maze, but changes every possible path space to a 7, instead of just the solution. Any ideas on how to fix this? Thanks in advance!

[keang]

First of all your test to see if you are at the end of the maze will always fail as you should be checking

if ( row == this.rows-1 && col == this.cols-1 )

.
The other problem is you aren't handling the backtracking. If any recursive call to traverseMaze() returns true you should immediately set the cell index you passed in to the recursive call to '7' and return true - do not continue checking other cells.

[Ryang027]

Thank you very much, that's exactly what I needed. For some reason I thought I tried setting the value to 7 whenever move came back true before, but I guess not in the manner you said.

Ps - sorry for not using the code tags...didn't read that thread until after my post haha.