Solving Logic Puzzles With Clojure's Core Logic, Part One

I used to love solving logic puzzles as a kid. Bought books of 'em. Great fun. They're a puzzle with this sort of shape:

  1. There are four sets of five things. For example, 5 people, 5 magazines, 5 reservation times and 5 cheeses.
  2. There are rules that connect them together, like, "Jason likes mozzarella."
  3. The rules are exclusive. If we're told Jason likes mozzarella, then Jason likes no other cheese, and nobody else likes mozzarella.
  4. You are given enough clues about the relationships between these things that only one possible configuration can exist. Find it.

It cries out, "Logic Programming", doesn't it? Well, recently the London Cloure group took a crack at it. We got pretty far, but didn't complete it before the night was over. I thought I'd finish it off and write it up, for your pleasure. Here goes...

I've taken a puzzle from Logic Puzzles.org, who seem to have a army of them. Here are the sets of things we're dealing with:

  • 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. You can skim over them. We'll go through them in detail in part two.

  1. Of Landon and Jason, one has the 7:30pm reservation and the other loves mozzarella.
  2. The blue cheese enthusiast subscribed to Fortune.
  3. The muenster enthusiast didn't subscribe to Vogue.
  4. The 5 people were the Fortune subscriber, Landon, the person with a reservation at 5:00pm, the mascarpone enthusiast, and the Vogue subscriber.
  5. The person with a reservation at 5:00pm didn't subscribe to Time.
  6. The Cosmopolitan subscriber has an earlier reservation than the mascarpone enthusiast.
  7. Bailey has a later reservation than the blue cheese enthusiast.
  8. Either the person with a reservation at 7:00pm or the person with a reservation at 7:30pm subscribed to Fortune.
  9. Landon has a later reservation than the Time subscriber.
  10. The Fortune subscriber is not Jamari.
  11. The person with a reservation at 5:00pm loves mozzarella.

There's only one possible solution, and core.logic is going to find it for us.

Before We Start, What's An lvar?

Imagine a closed box. I'll tell you that inside the box is something that is grey, weighs one tonne, and has a horn on its nose. When we open the box, you won't be surprised to see it contains a rhino. That's how I think of a logic variable, or lvar. It's a box containing something that's unknown right now. We can state some rules about what must be inside, and when we come to open the box, the right kind of thing will pop out.

So, with that in mind, let's set up our solution.

The Setup

We'll start with this code:

(let [people       (repeatedly 5 lvar)
      magazines    (repeatedly 5 lvar)
      cheeses      (repeatedly 5 lvar)
      reservations (repeatedly 5 lvar)
      answers (map list people magazines cheeses reservations)]
  (run* [q]
       (== q answers)))

Here, we've done four things:

  1. Called the lvar function five times, to create boxes for the five people.
  2. Repeated that three more times for magazines, cheeses and reservations.
  3. Spliced those four lists together, using (map list ...), to create a structure that's a list of five `[person, magazine, cheese,

reservation-time]tuples. When we open all those boxes, we'll have our answer. 4.run` a simple query: "Find all the qs, such that q is a possible answer."

So far, so good. Now all we need to do is add the right constraints, and the boxes will magically open to reveal the single answer to the puzzle.

First Constraints

So the first thing we need to constrain is the list of people, magazines, cheeses and reservations. This would be a start:

(let [people       (repeatedly 5 lvar)
      magazines    (repeatedly 5 lvar)
      cheeses      (repeatedly 5 lvar)
      reservations (repeatedly 5 lvar)
      answers (map list people magazines cheeses reservations)]
  (run 1 [q]
       (== q answers)
       (permuteo people [:amaya :bailey :jamari :jason :landon])
       (permuteo magazines [:fortune :time :cosmopolitan :us-weekly :vogue])
       (permuteo cheeses [:asiago :blue-cheese :mascarpone :mozzarella :muenster])
       (permuteo reservations [5 6 7 7.5 8.5])))

That says that people matches the list of five names, but not necessarily in the same order. It's a permutation of the given list. We repeat that pattern for all four kinds of thing.

That's almost right, but there's a problem with ordering. Even once we've figured out the correct tuples, we're going to get them in all possible orders, which is 5! or 120 answers, all of which are equivalent.

There are a few ways to handle this. We could to use a Set for the answers, instead of a list. That would be good in theory, but core.logic doesn't support setsyet. We could ignore the problem and just take whichever answer pops out first. Or we could define a fixed order for any one of the collections, and let the others fall in line with that.

Fixing the order is the approach I like, because then there's only one possible solution, which makes it easy to check we've got the rest of the code right later. So let's fix the order of the people:

(let [people       (repeatedly 5 lvar)
      magazines    (repeatedly 5 lvar)
      cheeses      (repeatedly 5 lvar)
      reservations (repeatedly 5 lvar)
      answers (map list people magazines cheeses reservations)]
  (run 1 [q]
       (== q answers)
       (== people [:amaya :bailey :jamari :jason :landon])
       (permuteo magazines [:fortune :time :cosmopolitan :us-weekly :vogue])
       (permuteo cheeses [:asiago :blue-cheese :mascarpone :mozzarella :muenster])
       (permuteo reservations [5 6 7 7.5 8.5])))

And with that, we're ready to start encoding puzzle rules. We'll pull them out as separate functions, so our final main function will look like this:

(let [people       (repeatedly 5 lvar)
      magazines    (repeatedly 5 lvar)
      cheeses      (repeatedly 5 lvar)
      reservations (repeatedly 5 lvar)
      answers (map list people magazines cheeses reservations)]
  (run 1 [q]
       (== q answers)
       (== people [:amaya :bailey :jamari :jason :landon])
       (rule-1 answers)
       (rule-2 answers)
       (rule-3 answers)
       (rule-4 answers)
       (rule-5 answers)
       (rule-6 answers)
       (rule-7 answers)
       (rule-8 answers)
       (rule-9 answers)
       (rule-10 answers)
       (rule-11 answers)
       (permuteo magazines [:fortune :time :cosmopolitan :us-weekly :vogue])
       (permuteo cheeses [:asiago :blue-cheese :mascarpone :mozzarella :muenster])
       (permuteo reservations [5 6 7 7.5 8.5])))

We'll look at the individual rules in part two...

  1. Yet.↩