I recently read Martin Erwig's interesting paper "Escape from Zurg: An Exercise in Logic Programming" [PDF]. It's a few years old, but still relevant, I think. The paper examines a homework assignment in a computer science course where the students were asked to solve a simple logic puzzle in the programming language of their choice. The paper goes on to compare a solution in Prolog with a solution in Haskell.
The solution in Haskell is actually fairly simple, as it just stores the solution space in a list and filters the list with a user-defined function which imposes the problem's invariants. Because Haskell is evaluated lazily, filtering the list ends up being equivalent to running a depth-first search with backtracking. It's pretty cool that the language gives this to the programmer for free.
I know "enough to be dangerous" with Haskell, and this paper got me thinking about solving other kinds of logic problems with Haskell. It seemed to me that the list monad (in conjunction with the MonadPlus instance for lists) could be used to model a simple constraint solver. I decided to see if I could model and solve Einstein's Puzzle.
Modeling the problem was not bad at all. I defined algebraic data types for each of the five main variables, and then defined a house as a 5-tuple containing each variable. I defined the street as a list of five houses. I then wrote functions for each of the problem's fifteen constraints. Each constraint function was of type [(Color, Nationality, Pet, Beverage, Cigarette)] -> Bool so that I could enforce the constraints with guard. Writing each constraint function was really easy due to Haskell's pattern-matching syntax. Here's one particularly nice example:
norwegianFirstHouse ((_, Norwegian, _, _, _):_) = True
norwegianFirstHouse _ = False
While writing the program, I noticed that the running time started to increase exponentially by the time I got to about the tenth constraint. I was more interested in solving the puzzle than optimizing my program (for the moment), so I decided to just plug in the rest of the constraints, compile with optimizations, and run the program and see what it would come up with.
Embarrassingly, the program took about two hours to complete. Although, considering the solution space includes close to 300 quadrillion possibilities, perhaps that's not too unreasonable for such a naïve solution (a well-written Prolog program could solve this problem orders of magnitude faster). I won't reveal the answer to the puzzle here, but my program did find the correct solution.
So my experiment was a partial success, I'd say. On the one hand, I solved Einstein's puzzle, and writing tho code was a breeze. On the other hand, my solution is hopelessly inefficient. I do believe that Haskell's list monad could be used as the foundation for a more efficient constraint solver, though. At this point, my only truly unresolved question is whether I qualify for Einstein's "2% of the population who can solve the puzzle." Unfortunately, Einstein seems to have been silent on the matter of those of us who can solve his puzzle by cheating.
Here is the complete code:
1 comment:
This is a good posting and I like your description of the problem and solution. You note that this program is very slow and takes about two hours to run. I wanted to point out that it can be vastly sped up by moving the guards up as far as possible in the solution function so that you don't generate so many permutations that could be checked much earlier. You have to do the checks on the lists of enumerations instead of tuples, so your constraint-checker functions would have to change some, but I added the following two and it brought the runtime down to under 2 minutes:
solution = do
k <- permutations colors
guard $ elem (Green, White) (zip k (tail k))
n <- permutations nats
guard $ Norwegian == head n
p <- permutations pets
I think by moving the constraint checks up as far as they can go, the runtime would be under a second. As it is written, the program is fully generating all permutations of pets, bevs, and cigs, which is 120^3, for all of the house configurations where the Norwegian is not on the far left, so can't possibly be solutions.
Post a Comment