Here's a little Java game that I found pretty entertaining.
When I got to the sixth puzzle I decided to see if I could write a program to solve these kinds of puzzles. I did; here it is in Ruby, featuring OOP goodness and a bit of recursion, but otherwise just brute force.
It only takes about .04 seconds to solve maze 9. It doesn't find an optimal solution; it tends to have Theseus wander around like a drunkard. Maybe it could be improved with heuristics, but I couldn't think of one. "Move towards the goal" doesn't work in general, because Theseus has to backtrack a lot on purpose to strand the Minotaur behind walls. It'll save one or two moves at most. "Move away from the Minotaur" or "Move toward the Minotaur" don't work because both are necessary many times. So I don't know. I only tried it on puzzle 6-9, but it seems to work.