Hunt the Wumpus Case
So, I've been playing around with my old Hunt the Wumpus world in VRChat, as well as working on my new iteration that will actually function (lol). And while showing someone how it works came across a really interesting case I wanted to share
Now for those unfamiliar with Hunt the Wumpus, the 1982 TI99/4A version specifically, the point of the game is to unsurprisingly to hunt the wumpus. The wumpus is a terrible beast with a foul stench. It is a messy eater, and the blood from its last meal travels down hallways and around bends until it is 2 rooms (not including the bendy hallways you see) away from where it's decided to nap.
Here's how that looks, with the large red... circle... being the wumpus' location.
If you enter the room it will awaken from its slumber and kill you. In order to slay the beast, you must deduce its location from the way the blood travels through connected rooms and fire an arrow into the room that it sleeps. The magic arrow will also travel along hallways, but if you miss outright the beast will wake up from the noise and kill you. For example, firing the arrow like so will result in the arrow traveling through the hallway until it finds the first 4-way, killing the wumpus if it is in that 4-way room.
Additionally there are 2 total slime pits in the dungeon that will also kill you if you fall into them. The slime is more viscous, and will only travel 1 room out form where the slime is. Finally the dungeon is cursed so that there is no exit. When you reach the end of it, it will wrap around to the other side, like so
So to recap (TLDR): entering a room with a wumpus or slime will kill you rooms up to 2 away from wumpus are red rooms up to 1 away from slime pit are green hallways dont count as rooms, and cannot contain wumpus or pits the map wraps horizontally and vertically arrows travel through hallways when fired, but not 4-way rooms Also, wumpus cant sleep in slime pits
(dont worry about the bats i didnt implement them lol)
So here's the map we ran into. If you were explore taking minimal (possibly absolutely no risks, hallway in middle of the slime stuff i didnt fully reason out) here are all the rooms we can enter without gambling our lives. I forget the spawn room but it was one of the safe ones i believe.
Now here's the problem, from that map above, it is impossible to safely tell where exactly the Wumpus is. More on that as we go
Out of the 5 rooms unexplored, one of them is definitely a slime pit, as it turns out that in the remaining 4 rooms, its possible that any of them can be some kind of hazard. Meaning we cannot possibly gather any more information. So... we should weigh the frequency of it being in each room and try to fire into the more probably room to maximize probability of success right? Absolutely not! It turns out there is a way We will start by attempting to deduce the location of the second slime pit, which we'll look for in this smaller 3x3 section.
Within the grid, we can see that if we assume the bottom right space is a slime pit, then the top middle must be connected with a hallway.
No matter what we put in the middle bottom square, we cannot connect both the two slime marked rooms on the left. Therefore, this cannot be the location of the slime pit. Now for the other two locations, we can find the following solutions to the layout.
Now something important here is that if there is a slime pit in one, there must be a hallway in the other. This narrows down the spots the wumpus can be in to 2 possible locations.
And here we start to narrow down on our solution. There are a couple cases we need to consider. We'll start by asking what is in the square in the top area. The worst case scenario is that room is a 4-way without a wumpus, because in that case we fire an arrow into the room and immediately die.
However we see this doesnt quite work. If that spot isnt the wumpus, then the other spot is wumpus, and therefore a 4-way.
When we follow the blood wrapping down past the bottom around into the top, the blood cant reach far enough to paint all the rooms. However, in order to reach the rest of the blood spots, there must be a hallway that would cause adjacent no-bloody rooms to have filled with blood
So what we get is that if the top room is a 4-way, then the other spot is not a wumpus room. Of the other spot is not a wumpus, then the top spot is a wumpus. Therefore, if the top room is a 4-way, it must be a wumpus room. Alright so lets get the next case out of the way, and this one is simple.
In the case above, the blood room directly below our wumpus candidate can't be bloody. This ones right out. Which leaves us with one final possibility, its a hallway that connects the bottom room to the right room.
So to summarize everything we've deduced, the slime pit is in one of the green question marks, and the other question mark must be a hallway, so the wumpus cant be in either of those positions. If the top remaining wumpus candidate is a 4-way, it must be a wumpus. Otherwise, it is a hallway that when entered from below leads to the right... then up... and directly to the actually location the wumpus is in! Here's my diagram showing the split possibilities.
And here, we finally get to the solution to this layout
If we go to the room below the top-most wumpus candidate, and fire directly up, regardless of which possible dungeon layout we got, we will still manage to Hunt the Wumpus. As a bonus, here's what the map actually looked like, first the two possibilities I mapped out when actually working through this. Then, turns out it wasnt either those, but luckily it didnt end up mattering. The general principle still held.