Solving a maze with HashMap-CodePudding

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.

CodePudding user response：

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/

CodePudding user response：

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