Problem with maze solving backtracking algorithm with setting visited rooms

Question

i seek if somebody could help me out with my room searching algorithm
I'm trying to implement a backtracking algorhitm for maze solving. I'm stuck in the place where i should memorize the rooms which i have already visited.
The maze is made up from rooms and each room has 4 sides - north, east, south and west. Each room is linked to next room by making a door to desired side, i.e room1.createNorth(roomName) which creates a new room up north and a new room has southern door to link back to the first as you can see in my Room class.

Here is my chopped room class, which represents each room in a maze. I removed south, west and east directions which are identical to my methods which deal with northern side.

public class Room {

    private String name;
    private Room north;
    private Room east;
    private Room west;
    private Room south;
    private boolean isExit = false;
    private Maze maze;

    /**
     * @return name room
     */
    public String getName() {
        return this.name;
    }

    /**
     * Sets room name
     * 
     * @param name
     */
    public void setName(String name) {
        this.name = name;
    }

    /**
     * Gets northern room if any
     * 
     * @return pointer to northern room if any, otherwise <code>null</code>
     */
    public Room getNorth() {
        return this.north;
    }

    /**
     * Sets the door to the next room to the north in that room and in the other
     * room sets southern door as connecting back to that room
     * 
     * @param otherRoom
     */
    public void setNorth(Room otherRoom) {
        this.north = otherRoom;
        otherRoom.south = this;
    }

    /**
     * creates a new room to the north and connects back to this room
     * 
     * @param name
     *            of the room
     * @return created room
     */
    public Room createNorth(String name) {
        Room otherRoom = null;

        // create new room in that direction ONLY if there is no room yet
        if (this.getNorth() == null) { // get northern direction, if it's null,
                                        // then it's okay to create there
            otherRoom = new Room(); // create!
            this.setNorth(otherRoom); // set the door
            otherRoom.setName(name); // set the name

        } else { // there is a room in that direction, so don't create a new
                    // room and drop a warning
            System.out.println("There is already a room in northern direction");
        }

        return otherRoom;
    }

    /**
     * Asdf
     * 
     * @return maze
     */
    public Maze getMaze() {
        return this.maze;
    }

    /**
     * Set maze
     * 
     * @param maze
     */
    public void setMaze(Maze maze) {
        this.maze = maze;
    }

    /**
     * @param roomName path to this room must be found
     */
    public void findPathTo(String roomName) {
        Room soughtRoom = this.getMaze().getEntry();

        while (!(soughtRoom.getName().equalsIgnoreCase(roomName))) {

//          here should be also a method such as setRoomAsVisited()

            if (this.getWest() != null) {
                soughtRoom = this.getWest();
                this.getMaze().getPaths().push(soughtRoom);
            }
            else if (this.getNorth() != null) {
                soughtRoom = this.getNorth();
                this.getMaze().getPaths().push(soughtRoom);
            }
            else if (this.getEast() != null) {
                soughtRoom = this.getEast();
                this.getMaze().getPaths().push(soughtRoom);
            }
            else if (this.getSouth() != null) {
                soughtRoom = this.getSouth();
                this.getMaze().getPaths().push(soughtRoom);
            }
            else {
                if (this.getMaze().getPaths().isEmpty()) {
                    break; // no more path for backtracking, exit (no solution found)
                }
                // dead end, go back!
                soughtRoom = this.getMaze().getPaths().pop();
            }
            System.out.println(this.getMaze().getPaths().toString());
        }


    }

    @Override
    public String toString() {
        return "Room name is " + this.getName();
    }
}

Maze looks like this: http://i.stack.imgur.com/2KePs.jpg where S is the start point

My Maze class

public class Maze {

    Room room;

/**
 * helper collection path stack for findPathTo() method
 */
private Stack<Room> paths = new Stack<Room>();

/**
 * @return path for exit
 */
public Stack<Room> getPaths() {
    return this.paths;
}

    /**
     * Singleton method for first room in the maze which is entry room
     * 
     * @return room if no room is created then creates new, otherwise returns
     *         already created room
     */
    public Room getEntry() {
        if (this.room == null) {
            this.room = new Room();
            return this.room;
        }
        return this.room;
    }
}

Here is my main class public class Main {

    public static void main(String[] args) {

        Maze maze = new Maze();
        maze.getEntry().setName("A4"); // set first room's name A4
        // labyrinth creation
        maze.getEntry().createEast("B4").createNorth("B3").createWest("A3");
        maze.getEntry().getEast().getNorth().createNorth("B2").createWest("A2")
                .createNorth("A1");
        maze.getEntry().getEast().getNorth().getNorth().createNorth("B1");
        maze.getEntry().getEast().getNorth().getNorth().createEast("C2")
                .createNorth("C1").createEast("D1");
        maze.getEntry().getEast().createEast("C4").createEast("D4");
        maze.getEntry().getEast().getEast().createNorth("C3").createEast("D3")
                .createNorth("D2").setExit(true);

        System.out.println("=====Test findPathTo method======");
        maze.getEntry().setMaze(maze); // set maze instance to our entrance room
        maze.getEntry().findPathTo("B4");

        System.out.println("=====End of testing findPathTo method======");

    }

}

The problem is in my findPathTo(roomName) method, which finds the route to the room. If i enter the room D4 then my algorithm moves only once to east to "B4" room from "A4" and there it just loops infinitely and the stack just grows with room "B4" only. Why doesn't it move ahead for example to next room "B3" or "C4" ?

EDIT: here is the working code

public void findPathTo(String roomName) {

        Room soughtRoom = this.getMaze().getEntry();

        while (!(soughtRoom.getName().equalsIgnoreCase(roomName))) {

            if (soughtRoom.getWest() != null && soughtRoom.getWest().isVisited != true) {
                this.getMaze().getPaths().push(soughtRoom);
                soughtRoom = soughtRoom.getWest();
                soughtRoom.isVisited = true;

            }
            else if (soughtRoom.getNorth() != null && soughtRoom.getNorth().isVisited != true) {
                this.getMaze().getPaths().push(soughtRoom);
                soughtRoom = soughtRoom.getNorth();
                soughtRoom.isVisited = true;

            }
            else if (soughtRoom.getEast() != null && soughtRoom.getEast().isVisited != true) {
                this.getMaze().getPaths().push(soughtRoom);
                soughtRoom = soughtRoom.getEast();
                soughtRoom.isVisited = true;

            }
            else if (soughtRoom.getSouth() != null && soughtRoom.getSouth().isVisited != true) {
                this.getMaze().getPaths().push(soughtRoom);
                soughtRoom = soughtRoom.getSouth();
                soughtRoom.isVisited = true;

            }
            else {
                if (this.getMaze().getPaths().isEmpty()) {
                    System.out.println("No solutions found :(");
                    break; // no more path for backtracking, exit (no solution found)
                }
                // dead end, go back!
                soughtRoom = this.getMaze().getPaths().pop();
            }
            System.out.println("Path rooms: " + this.getMaze().getPaths().toString());
        }
    }

Answer 1

There are several ways of doing this.

One would be to keep a "isVisited" boolean flag in each room object that you set/unset as your tracking and backtracking proceeds. This means taht you can only single-thread-search your maze (this may or may not matter).

Another would be to keep a list of visited rooms that you compare to (advantage here is that it should be relatively easy to just "push" a new room onto the list and have it popped automatically if you use the call-stack to pass this list).

You could also use a per-search hashtable of room to an isVisible, this allows for (possibly) faster lookups than searching a list, allows for multi-threading (as in "more than one thread can search the maze", not "more than one thread can participate in the same search").

There's also probably a few things I haven't thought of, but all three of these should be pretty straight-forward to implement.

Answer 2

A quick and highly unoptimized approach:

For each visited room, store the possible directions (make an enum Direction and a Set<Direction> for example) and remove the one you came from as well as the direction you took from the previous room. Thus, moving from A4 to B4 you'd remove EAST from A4 and WEST from B4. If you have to track back, just unwind the stack until you find a room with an unvisited direction (the list of possible directions is not empty) and try the next one. If the stack becomes empty at this point, you tried all possibilities without finding the target room.

As I said this is highly unoptimized, but it should work.

Answer 3

Some comments:

Your code is missing some functions you are using. There is no getPaths() method in your maze class. If you post code online, try to make sure it is easily compilable and testable. In your case I would have to guess, that getPaths() returns some kind of stack on which you try to store possible paths to be explored, but there is no way to be sure, what it actually does.

Also try to simplify the code before posting. Your maze is rather complicated and one would have to draw it, to see if your constructed maze matches the one on the picture. Try if you can reproduce the problem with a much simpler maze (2 or 3 rooms maybe). Also simplifying will often give you many hints as to where the problem might be. While you are simplifying there will be a point at which the problem will suddenly disappear. This tells you a lot about the actual bug.

Some Ideas on what might be wrong with your Code: At each direction you set soughtRoom to the one in that direction. I am assuming soughtRoom is the room your search is currently at. Then you push that room on the stack. However for a backtracking you need to store at each branch all the information that brings you back to a previous state. If you first set the current room and then push it, the information from the previous state is lost. Try it the other way round and see what happens.