Typical logic puzzles describe a number of individuals and give a range of likes and dislikes for those individuals expressed as constraints. The puzzle is to find the specific set of preferences for each individual. Given that Prolog is a logic programming language, we would hope it would be good for solving this kind of problem.
I came across this example on Kris Jenkins' Clojure blog where it was used as a problem for a core.logic workshop. Here I am going to detail the Prolog solution. I didn't look at either of the Clojure solutions before I wrote this Prolog version; I believe this is considerably better than the Clojure core.logic version - I compare and contrast at the end. I also wrote a solution in Java - it is very interesting to compare the run time performance of the Prolog with the Java.
The Problem Description
The problem itself originates on the Puzzle Baron's Logic Puzzles site. Here are the entities we are computing over:
- People: Amaya, Bailey, Jamari, Jason & Landon.
- Cheeses: Asiago, Blue Cheese, Mascarpone, Mozzarella & Muenster
- Magazines: Fortune, Time, Cosmopolitan, US Weekly & Vogue
- Reservation times: 5pm, 6pm, 7pm, 7:30pm, 8:30pm.
And here are the rules that tie each individual to their preferences:
- Of Landon and Jason, one has the 7:30pm reservation and the other loves mozzarella.
- The blue cheese enthusiast subscribed to Fortune.
- The muenster enthusiast didn't subscribe to Vogue.
- The 5 people were the Fortune subscriber, Landon, the person with a reservation at 5:00pm, the mascarpone enthusiast, and the Vogue subscriber.
- The person with a reservation at 5:00pm didn't subscribe to Time.
- The Cosmopolitan subscriber has an earlier reservation than the mascarpone enthusiast.
- Bailey has a later reservation than the blue cheese enthusiast.
- Either the person with a reservation at 7:00pm or the person with a reservation at 7:30pm subscribed to Fortune.
- Landon has a later reservation than the Time subscriber.
- The Fortune subscriber is not Jamari.
- The person with a reservation at 5:00pm loves mozzarella.
There is only one possible solution that satisfies all these constraints.
My first goal was to develop a clean solution without any regard to the efficiency of the program. Once I have that solution I will worry about the efficiency issues. I discuss the solution of this problem in some detail to give students an opportunity to follow through the problem solving from beinning to end.
The First Solution
The first version applies the generate-and-test pattern to the problem. The program generates a candidate solution and then tests to see if it meets all the constraints. If it does not, then backtracking generates the next solution until one is found that meets the requirements.
Now we have a clean solution that works, we can look at its implementation with a view to improving the run-time efficiency of the code. In this case it is possible to significant improvements.