•

Check out our Community Blogs

Register and join over 40,000 other developers!

### Recent Blog Entries

• phi

I love this community !

• JackJames

hi i am jack i am seo expert jack james would love you to read new post

# Recursive maze solving(need help badly)

java recursion backtracking

Well, after emailing my professor and listening to his advice (which consisted mainly of him telling me I'm not thinking recursively and to look at an unrelated program he did) I rewrote my code to the following:

```public class MazeSolution implements MazeSolver {

boolean[][] marked;
ArrayList<Maze.Door> correctPath = new ArrayList<>();

public ArrayList<Maze.Door> solveMaze(int startRow, int finishRow, int startCol, int finishCol, Maze maze) {
marked = new boolean[maze.getRows()][maze.getColumns()];
return solveMaze(startRow, finishRow, startCol, finishCol, maze, marked);
}

public ArrayList<Maze.Door> solveMaze(int startRow, int finishRow, int startCol, int finishCol, Maze maze, boolean[][] marked) {
int row = startRow;
int column = startCol;

if (row == finishRow && column == finishCol) {
return correctPath;
}
if (marked[row][column]) {
return null;
}
marked[row][column] = true;
if (!maze.isClosed(row, column, Maze.NORTH)) {
if (solveMaze(row - 1, finishRow, column, finishCol, maze, marked) != null) {
System.out.println(Maze.NORTH);
}
}
if (!maze.isClosed(row, column, Maze.EAST)) {
if (solveMaze(row, finishRow, column + 1, finishCol, maze, marked) != null) {
System.out.println(Maze.EAST);
}
}
if (!maze.isClosed(row, column, Maze.SOUTH)) {
if (solveMaze(row + 1, finishRow, column, finishCol, maze, marked) != null) {
System.out.println(Maze.SOUTH);
}
}
if (!maze.isClosed(row, column, Maze.WEST)) {
if (solveMaze(row, finishRow, column - 1, finishCol, maze, marked) != null) {
System.out.println(Maze.WEST);
}
}
return null;
}
// end getPath
} // end MazeSolution

```

It's still not working right, but it's a step in the right direction. The problem now is making it continue down the correct path and try another path when null is returned.

Go to the full post

This topic has been archived. This means that you cannot reply to this topic.
4 replies to this topic

CC Newcomer

• Member
• 10 posts

Posted 05 March 2013 - 06:12 PM

Good evening everyone

I've been working on this programming assignment for quite a bit and can't seem to get a certain recursive method to work.
Before posting the code (since theprogram is pretty long) here's all the info you might ask me for(thanks in advance!):

It is a program design to find and
highlight a solution to a maze.

A maze is composed of a grid of rooms
held in a 2D array.

Each room has at least one open door,
and several walls.

If a wall is in place, I can't continue
down that path.

The requirements are:

I must have a method that gives me an
array of doors (a sub class of the Maze class) that are highlighted
and show a path that is displayed when the program is run.

I have to use a boolean array to mark
my path to make sure I don't go in circles.

Each wall has an int designating it,
the North wall is 0, east is 1, etc.

So far, this is my code:

```public class MazeSolution implements MazeSolver {

boolean[][] marked;
static int lastDoor = -1;
ArrayList<Maze.Door> correctPath = new ArrayList<>();

public ArrayList<Maze.Door> solveMaze(int startRow, int finishRow, int startCol, int finishCol, Maze maze) {
marked = new boolean[maze.getRows()][maze.getColumns()];
return solveMaze(startRow, finishRow, startCol, finishCol, maze, marked);
} // end getPath

public ArrayList<Maze.Door> solveMaze(int startRow, int finishRow, int startCol, int finishCol, Maze maze, boolean[][] marked) {
int row = startRow;
int column = startCol;
boolean door = true;
if (row == finishRow && column == finishCol) {
return correctPath;
}
for (int wall = 0; wall < 4; wall++) {
boolean wallExists = maze.isClosed(row, column, wall);
if (!wallExists) {
if (wall == 0) {
if (!marked[row - 1][column]) {
lastDoor = wall;
door = wallExists;
}
}
if (wall == 1) {
if (!marked[row][column + 1]) {
lastDoor = wall;
door = wallExists;
}
}
if (wall == 2) {
if (!marked[row + 1][column]) {
lastDoor = wall;
door = wallExists;
}
if (wall == 3) {
if (!marked[row][column - 1]) {
lastDoor = wall;
door = wallExists;
}
}
}
}

System.out.println(lastDoor + "\t" + door + "\t");
if (door) {
System.out.println(lastDoor + "::" + door);
marked[row][column] = true;
int doorLocale = lastDoor;
if (doorLocale == 0) {
return solveMaze(row + 1, finishRow, column, finishCol, maze, marked);
}
if (doorLocale == 1) {
return solveMaze(row, finishRow, column - 1, finishCol, maze, marked);
}
if (doorLocale == 2) {
return solveMaze(row - 1, finishRow, column, finishCol, maze, marked);
}
if (doorLocale == 3) {
return solveMaze(row, finishRow, column+1, finishCol, maze, marked);
}
}

if (!door && lastDoor == 0) {
marked[row][column] = true;
return solveMaze(row - 1, finishRow, column, finishCol, maze, marked);
}
if (!door && lastDoor == 1) {
marked[row][column] = true;
return solveMaze(row, finishRow, column + 1, finishCol, maze, marked);
}
if (!door && lastDoor == 2) {
marked[row][column] = true;
return solveMaze(row + 1, finishRow, column, finishCol, maze, marked);
}
if (!door && lastDoor == 3) {
marked[startRow][startCol] = true;
return solveMaze(row, finishRow, column - 1, finishCol, maze, marked);
}
}
return null;
}
}
```

Can someone help me figure out why my code isn't working? I've been stuck on this for days and can't see what's wrong.

Thank you!

Edited by zerolink, 05 March 2013 - 06:13 PM.

### #2 dargueta

dargueta

I chown trolls.

• Moderator
• 4854 posts

Posted 05 March 2013 - 08:13 PM

What's your code doing that it shouldn't?

sudo rm -rf / && echo \$'Sanitize your inputs!'

CC Newcomer

• Member
• 10 posts

Posted 06 March 2013 - 04:09 AM

What it should be doing is backtracking when it hits a dead end. But instead it just calls it quits. The only advice my teacher gave me is to get-rid of the for loop and that I don't need acknowledge tracking. Someone told me I should make sure it returns null when it reaches a dead end because it will go backwards through the stack until it can find another path to take, but in my code returning null just terminates the entire program (as it should).

### #4 dargueta

dargueta

I chown trolls.

• Moderator
• 4854 posts

Posted 06 March 2013 - 01:11 PM

I think the problem might be where you've placed your return null. I reworked your code a bit to make it more readable and alter the logic a tad:

```if (door)
{
System.out.println(lastDoor + "::" + door);
marked[row][column] = true;

switch (lastDoor)
{
case 0:
return solveMaze(row + 1, finishRow, column, finishCol, maze, marked);

case 1:
return solveMaze(row, finishRow, column - 1, finishCol, maze, marked);

case 2:
return solveMaze(row - 1, finishRow, column, finishCol, maze, marked);
case 3:
return solveMaze(row, finishRow, column+1, finishCol, maze, marked);

default:
return null;
}
}
else
{
switch(lastDoor)
{
case 0:
marked[row][column] = true;
return solveMaze(row - 1, finishRow, column, finishCol, maze, marked);

case 1:
marked[row][column] = true;
return solveMaze(row, finishRow, column + 1, finishCol, maze, marked);
case 2:
marked[row][column] = true;
return solveMaze(row + 1, finishRow, column, finishCol, maze, marked);

case 3:
marked[startRow][startCol] = true;
return solveMaze(row, finishRow, column - 1, finishCol, maze, marked);

default:
return null;
}
}

```

Edited by dargueta, 06 March 2013 - 01:12 PM.

sudo rm -rf / && echo \$'Sanitize your inputs!'

CC Newcomer

• Member
• 10 posts

Posted 06 March 2013 - 02:31 PM   Best Answer

Well, after emailing my professor and listening to his advice (which consisted mainly of him telling me I'm not thinking recursively and to look at an unrelated program he did) I rewrote my code to the following:

```public class MazeSolution implements MazeSolver {

boolean[][] marked;
ArrayList<Maze.Door> correctPath = new ArrayList<>();

public ArrayList<Maze.Door> solveMaze(int startRow, int finishRow, int startCol, int finishCol, Maze maze) {
marked = new boolean[maze.getRows()][maze.getColumns()];
return solveMaze(startRow, finishRow, startCol, finishCol, maze, marked);
}

public ArrayList<Maze.Door> solveMaze(int startRow, int finishRow, int startCol, int finishCol, Maze maze, boolean[][] marked) {
int row = startRow;
int column = startCol;

if (row == finishRow && column == finishCol) {
return correctPath;
}
if (marked[row][column]) {
return null;
}
marked[row][column] = true;
if (!maze.isClosed(row, column, Maze.NORTH)) {
if (solveMaze(row - 1, finishRow, column, finishCol, maze, marked) != null) {
System.out.println(Maze.NORTH);
}
}
if (!maze.isClosed(row, column, Maze.EAST)) {
if (solveMaze(row, finishRow, column + 1, finishCol, maze, marked) != null) {
System.out.println(Maze.EAST);
}
}
if (!maze.isClosed(row, column, Maze.SOUTH)) {
if (solveMaze(row + 1, finishRow, column, finishCol, maze, marked) != null) {
System.out.println(Maze.SOUTH);
}
}
if (!maze.isClosed(row, column, Maze.WEST)) {
if (solveMaze(row, finishRow, column - 1, finishCol, maze, marked) != null) {
System.out.println(Maze.WEST);
}
}
return null;
}
// end getPath
} // end MazeSolution

```

It's still not working right, but it's a step in the right direction. The problem now is making it continue down the correct path and try another path when null is returned.

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download