Solving a maze with HashMap

Question

I am struggling to find a way to solve a maze. The key for the HashMap is a room and the value is a list of rooms you can access from it.

Map<String, String> map ={Entrance=[R1], Room1=[R2,R4], R2=[R1,R3], R3=[R2,R4,Exit], R4=[R1,R3]}

each Rn is a room.

List<String> key = map.get("Entrance");
List<String> path = new List<>();
Stack<String> visited = new Stack<>();
visited.add("Entrance");
for (String x : key){
   if (!visited.contains(x))
      path.add(x);
   else
      return path;
}

I know I should be doing some sort of backtracking, but don't know where to go from here. I am not sure how to get it to return a list of rooms so it is a path to the exit.

This is one of those times when a piece of paper and pen is going to be of more help. You start in a room (entrance), it has a 1 or more exits. You need to ascertain if you've previously visited any of the rooms, if not, just pick one and jump in one and basically repeat until you get to a dead end. If you can't go any further, back track until you can find another room to visit, always avoiding the "visited" rooms — MadProgrammer, Dec 08 '21 at 03:26
Thanks, I am just not sure how I an supposed to implement it. — Ferret-2742, Dec 08 '21 at 03:30
AFTER you run through this with a pen and paper (like suggested above) I think you'll want to represent this as a graph, and then run graph algorithms on this graph, like Dijkstra's shortest path algorithm. There might not always be a solution. But look for "Dijkstra's Java" and "Dijkstra's Graph Java" on Google to find a solution you understand. — Brian Stinar, Dec 08 '21 at 03:31
You might also consider making use of something like [GeeksForGeeks, backtacking](https://www.geeksforgeeks.org/the-knights-tour-problem-backtracking-1/) examples. I implemented a variation of the "rat maze" recently and based on your example, it would appear to be a good match. Although it does make use of recursion, I was able to generate a basic result of your problem without it — MadProgrammer, Dec 08 '21 at 03:53
We can't solve this problem for you. The struggle (as painful as it is) will help you better understand how to solve other problems in the future. For example, in my test, I made use of a `LinkedList` to keep track of the "good" path, as it allowed me use it effectively use it as LIFO queue, as well as a `List` to keep track of all the rooms I'd visited. These are critical decision points you need to be able to make and understand — MadProgrammer, Dec 08 '21 at 03:56
Thanks, It is just that I don't have much time to do it. Am I correct in my code above just needs to be added to, or will I have to start over. — Ferret-2742, Dec 08 '21 at 04:13

score 1 · Answer 1 · answered Dec 08 '21 at 05:09

So what you, basically, have is something like...

            +----+----+
Entrance -> | R1 | R4 |
            +----+----+
            | R2 | R3 | -> Exit
            +----+----+

You need to find your way to R3 (where the exit is)

So, we can look at the problem, something like this.

We start at the entrance

+--------------+-----------------+------+---------+
| Current Room | Available Exits | Path | History |
+--------------+-----------------+------+---------+
| Entrance     | R1              |      |         |
+--------------+-----------------+------+---------+

Add the current room to the history

+--------------+-----------------+------+----------+
| Current Room | Available Exits | Path | History  |
+--------------+-----------------+------+----------+
| Entrance     | R1              |      | Entrance |
+--------------+-----------------+------+----------+

Does it contain Exit? No, then let's find a room to goto, in this case, R1 is our only choice, let's got to R1. Add Entrance to our path

+--------------+------------------+----------+----------+
| Current Room | Available Exits  |   Path   | History  |
+--------------+------------------+----------+----------+
| R1           | Entrance, R2, R4 | Entrance | Entrance |
+--------------+------------------+----------+----------+

Does it contain Exit? No. Okay, we need to remove all rooms we've already visited. That leaves us with R2 and R4, doesn't matter which we pick.

Add the current room to the history and the path

+--------------+------------------+-------------+-------------+
| Current Room | Available Exits  |    Path     |   History   |
+--------------+------------------+-------------+-------------+
| R1           | Entrance, R2, R4 | Entrance,R1 | Entrance,R1 |
+--------------+------------------+-------------+-------------+

And let's go to R4

+--------------+-----------------+-------------+-------------+
| Current Room | Available Exits |    Path     |   History   |
+--------------+-----------------+-------------+-------------+
| R4           | R1, R3          | Entrance,R1 | Entrance,R1 |
+--------------+-----------------+-------------+-------------+

Does it contain Exit? No. We've already been too R1, so that leaves us with R3.

Add R4 to our path and history

+--------------+-----------------+----------------+----------------+
| Current Room | Available Exits |      Path      |    History     |
+--------------+-----------------+----------------+----------------+
| R4           | R1, R3          | Entrance,R1,R4 | Entrance,R1,R4 |
+--------------+-----------------+----------------+----------------+

And let's go to R3

+--------------+-----------------+----------------+----------------+
| Current Room | Available Exits |      Path      |    History     |
+--------------+-----------------+----------------+----------------+
| R3           | R2, R4, Exit    | Entrance,R2,R4 | Entrance,R2,R4 |
+--------------+-----------------+----------------+----------------+

Does it contain Exit? YES!!!

Add it to our path and lets scamper!!

+--------------+-----------------+---------------------+---------------------+
| Current Room | Available Exits |        Path         |       History       |
+--------------+-----------------+---------------------+---------------------+
| R3           | R2, R4, Exit    | Entrance,R2,R4,Exit | Entrance,R2,R4,Exit |
+--------------+-----------------+---------------------+---------------------+

So, your path through the "maze" went Entrance -> R2 -> R4 -> Exit and we didn't even need to backtrace!

Now, there is a pattern to the above workflow, see if you can pick out. Try choosing a different room each time and see where it takes you.

Technically, you don't need the history, as you are unlikely to ever back track, but if the maze becomes more complex, it will come in handy, because if you do backtrace, you'd pop the last element off the path, but the history will remind you not to go that way again ;)

Honestly, I think desk checking is so underrated as a concept, my wife gets furious with me because I have dozens of notes books laying around, all with different scribblings of different ideas in them, all unrelated, so I need a note book for each separate idea

I think that I understand this, but am having trouble doing the backtracking part. Do you maybe have an example of code? — Ferret-2742, Dec 08 '21 at 18:06
@Ferret-2742 Based on your current input, you don't actually need to do back tracking, there are only two available paths, R1->R4->R3 and R1->R2->R3, none of the available paths take you to a dead end, so I'd focus on that for the moment. If you need back tracking later, the basic concept is; if no available directions from current room, make the "current room" equal to the last room in the `path` and try again (having added the dead end to the history) — MadProgrammer, Dec 08 '21 at 19:37

score 0 · Answer 2 · answered Dec 08 '21 at 03:34

You need to implement an algorithm to find the path. There are a number of choices of algorithms that work for this kind of problem.

If you don't care about the efficiency then a breadth first search is probably the easiest to implement. There are good examples already on stack overflow:

Finding the shortest path nodes with breadth first search

Breadth First Search and Depth First Search

If you care about efficiency of your algorithm (e.g. you want it to work with progressively larger graphs) you'll want to use a graph algorithm such as Dijkstra's shortest path.

There are many tutorials on using this algorithm, here is one such Java based tutorial.

https://www.geeksforgeeks.org/dijkstras-shortest-path-algorithm-in-java-using-priorityqueue/

Solving a maze with HashMap

2 Answers2