Our Approach

The most fundamental part of the robot's movement is to go up and hug the outer left wall, turning right when it reaches the end. This is chosen because following the path, all the coordinates on the board will be neighbored, hence gathering enough information for the whole board. Assuming that there are no obstacles, the robot would end at (3,3).

We call this the ideal path:

[(0,3),(0,2),(0,1),(0,0),(1,0),(2,0),(3,0),(3,1),(3,2),(3,3)]

However, it is almost impossible (unless the puzzle is really easy) for the robot to follow the ideal path, as it will face obstacles.  

We will discuss how the robot reacts when a breeze or stench is felt later. 

Assuming the robot is not on the ideal path due to some detour, and it is at a safe spot (nothing is felt). The next logical decision the robot makes is to find its way back to the ideal path while maximizing the map explored. 

We first define the neighbors of the current position, which have not been explored (not in the path), to be the possible next move.
Among the possible next moves, we determine the next move to be the one closest, in terms of euclidean distance, to the ideal path.

We can find the next coordinate by calculating the proximity to the path of each possibility, then choose the minimal shortest distance to any path segment. 

For every step it takes, the robot does the following deduction:

• Wumpus and Gold

Since these both only have 1 on the map. Their coordinate will be the union of the set of neighbor coordinates which they're felt at. When there is only one coordinate in the union of all neighbors, their location is determined. 

• Hole

Since there might be more than 1 hole, it would be more difficult to determine the exact location (has to travel to all neighbor coordinates of the hole). The robot simply eliminates possible hole positions based on common neighbors between the possible hole and the robot. 

↖️E.g. Breeze is felt at (1,1), but if the robot is at (3,1), it can deduce that (2,1) does not have a hole, since (1,1) and (3,1) share (2,1) as a common neighbor. 

The robot is next to the gold 🤑

If glitter is all the robot feels, it will move to all the possible neighboring coordinates, since the gold has to be in one of them.

If it feels glitter but also breeze or stench, it will mark down the possibility of where glitter is felt, and proceed with the rest of the algorithm since it doesn't take chances of death.

Wumpus is found 🧌

Wumpus is found when there is only one possible wumpus coordinate.

If so, the robot backtracks its path to the one neighboring the wumpus and shoots it. 

Once the wumpus is dead, it immediately moves to the coordinates of the wumpus. 

We mentioned the robot may be stuck in a loop, but how does the program know that? 

The program checks if any sequence of recent positions repeats itself consecutively. If such a repeating sequence is found, the program will determine the robot is stuck in the loop.

The robot got the gold 🤑

It will try to find an "optimal" pathway back home. In the optimal pathway, it will only move on coordinates that it traveled to before. It will attempt to continuously move down, until it can't, then turn left. If it can't turn left, it will move up until it can. Then keep moving left till it is at the first column.

If the optimal path has more steps than simply backtracking the same path, it will take the original path instead.