A robot, let's say, Steve, is in the bottom left corner of a rectangular room, the size of which is unknown. His goal is to travel to the top left corner of the room and stop there. There are random walls present in the room. There always is a way to the corner.
Steve can do the following:
- Move forward.
- Turn left, right and around.
- Detect if a wall is in front of him or not.
- Detect if he is facing to the left, right, up or down.
- Put/pick up a diamond in/from the slot he is standing in.
- Detect if there is a diamond where he is standing.
- Steve has an infinite numbers of diamonds.
- Steve cannot count (that is, he functions as a finite state machine).
What I've thought of so far is using the right-handed method using which Steve will always arrive at the top right corner, but detecting it is the major problem, as there can be other places in the room with walls to the right and top. Consider this case, for example:
"S" represents Steve. His destination is (10, 8), but as we can see, there are 7 other places in the room which can be mistaken for the destination by simply checking for the bordering walls.