Theseus and the minotaur is a puzzle designed by Robert Abbott, the aim of which is to escape a maze before the minotaur can get you. However, you can only move one step at a time, while the minotaur will take two steps for every step you take. Furthermore, the minotaur will always try to move as close to the person in the maze as possible, but will first move horizontally, then vertically to find a path. This element is crucial in figuring out some of these puzzles.
Since the minotaur will never move away from the person in the maze it is possible to get the minotaur stuck in certain sections of the maze, which is another crucial part to figuring out these puzzles. Both the minotaur and the person can wait as well. The minotaur will do so if taking another step would mean moving away from the person. Other than that it's mostly a case of planning out your steps.
As far as RPG settings go this one makes for a fun puzzle. The steps are easily translated into grids or even movement speeds, the minotaur can be replaced with any monster, and the maze doesn't even have to be a contained area. It could be a grim and dire looking monster following the party around the world, occasionally coming close enough to the party at which point they have to try and escape once more. The monster will eventually catch up with them again once they've moved in any direction that allows the monster to escape its locked position, but until that time the party is relatively safe.
In my example below my character finds herself in a maze-like area, she knows a minotaur is coming, and where the minotaur is coming from. She also knows the rules of the Theseus and the minotaur puzzle. If she manages to evade the minotaur she'll escape safely, if she runs into the minotaur at any point a fight will ensue, one she'll likely lose.
Of course in an RPG setting my character might have spells or other abilities at her disposal, but let's just assume this area nullifies all of them through magic.
The solution to the illustration below is as follows:
1. I move to the left. The minotaur moves two to the right.
2. I move down. The minotaur moves one to the right, and one down.
3. I move to the left. The minotaur will move one to the left, then stop. Remember, the minotaur will always move horizontally first.
4. I move left, the minotaur moves one left as well.
5. I move two down, then 1 left into the corner. The minotaur will stay put until I'm in the corner, then move 1 left and 1 down.
6. I wait. The minotaur moves 2 further down, and is now right next to me behind the wall.
7. I move 2 right, 1 up, and 1 right again. The minotaur will not move, as doing so would mean going further from me.
8. I move 1 up. The minotaur moves 1 up as well.
9. I move one up, the minotaur moves 1 up, and 1 to the right.
10. I move one up again. The minotaur will move one to the right, and is now stuck in that corner.
11. I move 1 up, 1 to the right, and 1 up out of the exit. The minotaur still cannot move without going further from me.