This is a read-only archive!

Theseus and the Minotaur

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.

June 03, 2006 @ 4:03 PM PDT
Cateogory: Programming
Tags: Ruby, Java

1 Comment

Quoth Hussam on June 03, 2006 @ 5:04 PM PDT

Becomes a smart ass

"If you are using Internet Explorer, you might be able to play these mazes off-line. Click here for more information."

That's all I have to say to you. xD