Puzzle Solver

Leave a comment

January 18, 2011 by huionn

Einstein’s Puzzle

Given that:

  1. There are 5 houses in 5 different colors.
  2. Each house is owned by a man of a different nationality.
  3. The 5 owners drink a certain type of beverage, smoke a certain brand of cigar, and keep a certain pet.
  4. No owners have the same pet, smoke the same brand of cigar, or drink the same beverage.

The question is: Who owns the fish?

Clues:

  1. The Brit lives in the red house.
  2. The Swede keeps dogs as pets.
  3. The Dane drinks tea.
  4. The green house is on the left of the white house.
  5. The green house’s owner drinks coffee.
  6. The person who smokes Pall Mall rears birds.
  7. The owner of the yellow house smokes Dunhill.
  8. The man living in the center house drinks milk.
  9. The Norwegian lives in the first house.
  10. The man who smokes Blends lives next to the one who keeps cats.
  11. The man who keeps the horse lives next to the man who smokes Dunhill.
  12. The owner who smokes Bluemasters drinks beer.
  13. The German smokes Prince.
  14. The Norwegian lives next to the blue house.
  15. The man who smokes Blends has a neighbour who drinks water.

This kind of puzzles is generally know as Constraint satisfaction problems or CSPs. CSP can be solved efficiently with solvers.

As I am learning Drools, I tried to solve Einstein’s Puzzle with rules. After a few days of study, I realized that Drools is not optimized to solve CSP.

Nevertheless, I managed to come out an inefficient solution with pure Drools Expert implementation.

For naive implementation, there are 5!^5 ~ 24.9 billion candidate solutions (I tried it and it took very, very, very long time to resolve the answer).

So in order to shorten the processing time, I filter out the statements applied to same house before building the candidate solution space. It greatly reduces the size of candidate solution space.

The result is 19523 rules fired in 2500ms. (Compared with other CSP Solvers which can get the answer in 200-300ms)

package com.sample

import com.sample.*;

dialect "mvel"

rule "Brit lives in a red house"
salience 100
    when
        $x : Home((nationality == "BRIT" && paint != "red") ||
            (paint == "red" && nationality != "BRIT"))
    then
        retract($x);
end

rule "Swede keeps dogs as pets"
salience 100
    when
        $x : Home((nationality == "SWEDE" && pet != "dogs") ||
            (pet == "dogs" && nationality != "SWEDE"))
    then
        retract($x);
end

rule "Dane drinks tea"
salience 100
    when
        $x : Home((nationality == "DANE" && beverage != "tea") ||
            (beverage == "tea" && nationality != "DANE"))
    then
        retract($x);
end

rule "Solution space"
salience 50
    when
        $x1 : Home(sequence == 1)
        $x2 : Home(sequence == 2, paint != $x1.paint, nationality != $x1.nationality, pet != $x1.pet, beverage != $x1.beverage, cigar != $x1.cigar)
        $x3 : Home(sequence == 3, paint != $x1.paint, nationality != $x1.nationality, pet != $x1.pet, beverage != $x1.beverage, cigar != $x1.cigar,
            paint != $x2.paint, nationality != $x2.nationality, pet != $x2.pet, beverage != $x2.beverage, cigar != $x2.cigar)
        $x4 : Home(sequence == 4, paint != $x1.paint, nationality != $x1.nationality, pet != $x1.pet, beverage != $x1.beverage, cigar != $x1.cigar,
            paint != $x2.paint, nationality != $x2.nationality, pet != $x2.pet, beverage != $x2.beverage, cigar != $x2.cigar,
            paint != $x3.paint, nationality != $x3.nationality, pet != $x3.pet, beverage != $x3.beverage, cigar != $x3.cigar)
        $x5 : Home(sequence == 5, paint != $x1.paint, nationality != $x1.nationality, pet != $x1.pet, beverage != $x1.beverage, cigar != $x1.cigar,
            paint != $x2.paint, nationality != $x2.nationality, pet != $x2.pet, beverage != $x2.beverage, cigar != $x2.cigar,
            paint != $x3.paint, nationality != $x3.nationality, pet != $x3.pet, beverage != $x3.beverage, cigar != $x3.cigar,
            paint != $x4.paint, nationality != $x4.nationality, pet != $x4.pet, beverage != $x4.beverage, cigar != $x4.cigar)
    then
        CandidateSolution cs = new CandidateSolution($x1, $x2, $x3, $x4, $x5);
        //System.out.println("insert: " + cs);
        insertLogical(cs);
end

rule "Green house is on the left of the White house"
salience 10
    when
        $cs : CandidateSolution()
        $x : Home(paint == "green") from $cs.neighbours
        exists (Home(paint == "white", sequence != ($x.sequence + 1)) from $cs.neighbours)
    then
        //System.out.println("retract ‘Green house is on the left of the White house’: " + $cs);
        retract($cs);
end

rule "owner of the Green house drinks coffee"
salience 100
    when
        $x : Home((paint == "green" && beverage != "coffee") ||
            (beverage == "coffee" && paint != "green"))
    then
        retract($x);
end

rule "person who smokes Pall Mall rears birds"
salience 100
    when
        $x : Home((cigar == "Pall Mall" && pet != "birds") ||
            (pet == "birds" && cigar != "Pall Mall"))
    then
        retract($x);
end

rule "owner of the Yellow house smokes Dunhill"
salience 100
    when
        $x : Home((paint == "yellow" && cigar != "Dunhill") ||
            (cigar == "Dunhill" && paint != "yellow"))
    then
        retract($x);
end

rule "man living in the centre house drinks milk"
salience 100
    when
        $x : Home((sequence == 3 && beverage != "milk") ||
            (beverage == "milk" && sequence != 3))
    then
        retract($x);
end

rule "Norwegian lives in the first house"
salience 100
    when
        $x : Home((nationality == "NORWEGIAN" && sequence != 1) ||
            (sequence == 1 && nationality != "NORWEGIAN"))
    then
        retract($x);
end

rule "man who smokes Blends lives next to the one who keeps cats"
salience 10
    when
        $cs : CandidateSolution()
        $x : Home(cigar == "Blends") from $cs.neighbours
        exists (Home(pet == "cats", sequence != ($x.sequence + 1), sequence != ($x.sequence – 1)) from $cs.neighbours)
    then
        //System.out.println("retract ‘man who smokes Blends lives next to the one who keeps cats’: " + $cs);
        retract($cs);
end

rule "man who keeps horses lives next to the man who smokes Dunhill"
salience 10
    when
        $cs : CandidateSolution()
        $x : Home(pet == "horses") from $cs.neighbours
        exists (Home(cigar == "Dunhill", sequence != ($x.sequence + 1),  sequence != ($x.sequence – 1)) from $cs.neighbours)
    then
        //System.out.println("retract ‘man who keeps horses lives next to the man who smokes Dunhill’: " + $cs);
        retract($cs);
end

rule "man who smokes Blue Master drinks beer"
salience 100
    when
        $x : Home((cigar == "Blue Master" && beverage != "beer") ||
            (beverage == "beer" && cigar != "Blue Master"))
    then
        retract($x);
end

rule "German smokes Prince"
salience 100
    when
        $x : Home((nationality == "GERMAN" && cigar != "Prince") ||
            (cigar == "Prince" && nationality != "GERMAN"))
    then
        retract($x);
end

rule "Norwegian lives next to the blue house"
salience 10
    when
        $cs : CandidateSolution()
        $x : Home(nationality == "NORWEGIAN") from $cs.neighbours
        exists (Home(paint == "blue", sequence != ($x.sequence + 1), sequence != ($x.sequence – 1)) from $cs.neighbours)
    then
        //System.out.println("retract ‘Norwegian lives next to the blue house’: " + $cs);
        retract($cs);
end

rule "man who smokes Blends has a neighbour who drinks water"
salience 10
    when
        $cs : CandidateSolution()
        $x : Home(cigar == "Blends") from $cs.neighbours
        exists (Home(beverage == "water", sequence != ($x.sequence + 1), sequence != ($x.sequence – 1)) from $cs.neighbours)
    then
        //System.out.println("retract ‘man who smokes Blends has a neighbour who drinks water’: " + $cs);
        retract($cs);
end

// should have only one left
/*
rule "result"
    salience -10
    when
        $cs : CandidateSolution()
    then
        System.out.println("The solution is " + $cs);
end
*/

query getSolution
    $cs : CandidateSolution()
end

Very verbose, lolz

I guess the bottleneck lies in rule "Solution space"

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: