Question: I left my cat in a maze, and I’m not allowed in to retrieve it. The maze is a 10m×10m grid, where some of the grid edges are walls and some aren’t. I can’t remember anything about where the walls are. My cat is very obedient, but he only understands the instructions “walk 1m forwards”, “turn 90◦ left”, and “turn 90◦ right” but nothing else. If I shout for him to walk forwards and that would result in him walking into a wall, he’ll just do nothing for that order. I can’t see into the maze, and have no idea whether my orders for him to walk forward are succeeding or not. Is there a sequence of orders I could shout that would get him out of the maze, no matter what the maze looks like and no matter which square I left him at, and no matter which direction I left him facing?
Apparently there is a sequence of moves that solves any maze. My idea is that if you imagine the 10x10 grid as 100 vertices, then the maze is only solvable if it is a tree and then find an algorithm that lets you traverse every vertex, no matter where you start. Another one of my ideas is to pick an arbitrary sequence of moves, and define some function, that takes this sequence and turns it into something else, which you can add on to the first sequence and make it the "2nd step", then do that a number of times. I'm not sure it gets me anywhere, and I would really like to see a solution to this problem. The number of steps should be finite, otherwise the answer is trivial.