Jump to content




Recent Topics

Recent Status Updates

  • Photo
      18 Aug
    KodeKool

    When faced with a wall of errors and no hope to fix them, remember the following "Programs always do what you tell them to, and seldom what you want them to, but eventually you'll run out of things that can go wrong and it'll just work. and that's the secret to good programming."

    Show comments (2)
View All Updates

Developed by Kemal Taskin
Photo
- - - - -

Recursive maze solving(need help badly)

java recursion backtracking

Best Answer zerolink, 06 March 2013 - 02:31 PM

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) {
            correctPath.add(new Maze.Door(row, column, maze.NO_DIRECTION, Color.red));
            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);
                correctPath.add(new Maze.Door(row, column, maze.NO_DIRECTION, Color.red));
            }
        }
        if (!maze.isClosed(row, column, Maze.EAST)) {
            if (solveMaze(row, finishRow, column + 1, finishCol, maze, marked) != null) {
                System.out.println(Maze.EAST);
                correctPath.add(new Maze.Door(row, column, maze.NO_DIRECTION, Color.red));
            }
        }
        if (!maze.isClosed(row, column, Maze.SOUTH)) {
            if (solveMaze(row + 1, finishRow, column, finishCol, maze, marked) != null) {
                System.out.println(Maze.SOUTH);
                correctPath.add(new Maze.Door(row, column, maze.NO_DIRECTION, Color.red));
            }
        }
        if (!maze.isClosed(row, column, Maze.WEST)) {
            if (solveMaze(row, finishRow, column - 1, finishCol, maze, marked) != null) {
                System.out.println(Maze.WEST);
                correctPath.add(new Maze.Door(row, column, maze.NO_DIRECTION, Color.red));
            }
        }
        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

#1 zerolink

zerolink

    CC Newcomer

  • Member
  • PipPip
  • 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) {
            correctPath.add(new Maze.Door(row, column, maze.NO_DIRECTION, Color.red));
            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;
         correctPath.add(new Maze.Door(row, column, maze.NO_DIRECTION, Color.red));
         return solveMaze(row - 1, finishRow, column, finishCol, maze, marked);
         }
         if (!door && lastDoor == 1) {
         marked[row][column] = true;
         correctPath.add(new Maze.Door(row, column, maze.NO_DIRECTION, Color.red));
         return solveMaze(row, finishRow, column + 1, finishCol, maze, marked);
         }
         if (!door && lastDoor == 2) {
         marked[row][column] = true;
         correctPath.add(new Maze.Door(row, column, maze.NO_DIRECTION, Color.red));
         return solveMaze(row + 1, finishRow, column, finishCol, maze, marked);
         }
         if (!door && lastDoor == 3) {
         marked[startRow][startCol] = true;
         correctPath.add(new Maze.Door(startRow, startCol, maze.NO_DIRECTION, Color.red));
         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
  • 4,495 posts

Posted 05 March 2013 - 08:13 PM

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


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


#3 zerolink

zerolink

    CC Newcomer

  • Member
  • PipPip
  • 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
  • 4,495 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;
            correctPath.add(new Maze.Door(row, column, maze.NO_DIRECTION, Color.red));
            return solveMaze(row - 1, finishRow, column, finishCol, maze, marked);
             
        case 1:
            marked[row][column] = true;
            correctPath.add(new Maze.Door(row, column, maze.NO_DIRECTION, Color.red));
            return solveMaze(row, finishRow, column + 1, finishCol, maze, marked);
        case 2:
            marked[row][column] = true;
            correctPath.add(new Maze.Door(row, column, maze.NO_DIRECTION, Color.red));
            return solveMaze(row + 1, finishRow, column, finishCol, maze, marked);
            
        case 3:
            marked[startRow][startCol] = true;
            correctPath.add(new Maze.Door(startRow, startCol, maze.NO_DIRECTION, Color.red));
            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!'


#5 zerolink

zerolink

    CC Newcomer

  • Member
  • PipPip
  • 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) {
            correctPath.add(new Maze.Door(row, column, maze.NO_DIRECTION, Color.red));
            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);
                correctPath.add(new Maze.Door(row, column, maze.NO_DIRECTION, Color.red));
            }
        }
        if (!maze.isClosed(row, column, Maze.EAST)) {
            if (solveMaze(row, finishRow, column + 1, finishCol, maze, marked) != null) {
                System.out.println(Maze.EAST);
                correctPath.add(new Maze.Door(row, column, maze.NO_DIRECTION, Color.red));
            }
        }
        if (!maze.isClosed(row, column, Maze.SOUTH)) {
            if (solveMaze(row + 1, finishRow, column, finishCol, maze, marked) != null) {
                System.out.println(Maze.SOUTH);
                correctPath.add(new Maze.Door(row, column, maze.NO_DIRECTION, Color.red));
            }
        }
        if (!maze.isClosed(row, column, Maze.WEST)) {
            if (solveMaze(row, finishRow, column - 1, finishCol, maze, marked) != null) {
                System.out.println(Maze.WEST);
                correctPath.add(new Maze.Door(row, column, maze.NO_DIRECTION, Color.red));
            }
        }
        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.