Friday, July 13, 2012

Jewels of the Oracle - Horse Puzzle Solver (1999)

For a programmer, there are always two games - the game, and the metagame. Often it's much more fun writing software to play the game for you. This is a post about a project I wrote in winter 1999.

I remember first trying the horse puzzle from Jewels of the Oracle. It is a puzzle where one must arrange nine squares by positioning and turning them such that each adjacent pair of edges matches properly. It seemed to me like a fun, straightforward programming challenge. You can see a screenshot of it here.

I threw a brute-force solver together using Turbo Pascal and ran it on our 486DX2/66, but that wasn't quite enough power for the task. Fortunately, my dad had just taken delivery of a Pentium II/366 laptop, which happened to be wasting cycles just then. I transferred the program over and my dad ran it in the background. After about a minute, the computer started emitting a loud hissing noise. Worried, we examined the situation closer and realized that the laptop's fans had kicked into overdrive, due to high and constant processor load... which yielded a solution in only a few minutes.

I never sat down to think about it seriously, but although the problem space of that particular puzzle is very large, I reckon the number of solutions is fairly large as well. Or it could just be that I got really, really, really lucky and that my encoding of the problem results in finding a solution so "low" in the problem space index.

The solver doing its thing.  Solutions flash by quite fast.
More solving work.
This following one actually represents a solution, whereby all 1's are beside 2's, all 3's are beside 4's and all 5's are beside 6's.

A solution.
I had at one point estimated that a Pentium III running at 600 MHz could probably exhaust the solution space in 45 minutes to an hour.

No comments:

Post a Comment