Thursday, January 6, 2011

Who owns the Zebra? SQL Solution

Have you ever come across the "Who owns the Zebra?" problem? If you're reading this blog, it means you probably have. It's one of the most well-known constraint satisfaction problems and quite easy to solve using only pen and paper and logical inference. On the other hand, if you were to use a computer, you might use a constraint solver like Prolog with CSP extensions (e.g. Sicstus Prolog). However, it's also possible to generate a solution using only SQL. In this case I've been using Oracle SQL and the free version of Oracle DBMS (Oracle XE). I'll jump right in...

The problem
There are five houses, each of a different color and inhabited by men of different nationalities, with different pets, favorite drinks, and cars. Moreover, there are several constraints:
  1. The Enghlishman lives in the red house.
  2. The Spaniard owns the dog.
  3. The man in the green house drinks cocoa.
  4. The Ukrainian drinks eggnog.
  5. The green house is immediately to the right (your right) of the ivory house.
  6. The owner of the Oldsmobile also owns snails.
  7. The owner of the Ford lives in the yellow house.
  8. The man in the middle house drinks milk.
  9. The Norwegian lives in the first house on the left.
  10. The man who owns the Chevrolet lives in the house next to the house where the man owns a fox.
  11. The Ford owners's house is next to the house where the horse is kept.
  12. The Mercedes-Benz owner drinks orange juice.
  13. The Japanese drives a Volkswagen.
  14. The Norwegian lives next to the blue house
The question is: Who owns the Zebra?
Modelling the problem
From the above we can extract the following information; there are five houses each having five variables each pertaining to the house or the owner of the house The variables are color, nationality, pet, drink and car. Each variable has a domain of five possible values:
  • Color ∈ {Red,Blue,Yellow,Green,Ivory}
  • Nationality ∈ {Norwegian,English,Spanish,Japanese,Ukrainian}
  • Pet ∈ {Dog,Horse,Zebra,Snail,Fox}
  • Drink ∈ {Cocoa,Eggnog,Orange juice,Milk,Water}
  • Car ∈ {Oldsmobile,Ford,Mercedes-Benz,Chevrolet,Volkswagen}
Next we have an index for house from the set N ∈ {1,2,3,4,5}. We said that we have five houses with five variables each, which gives us 25 variables. These variables are named with abbreviations (where n ∈ N, i.e. house 1, 2, 3, etc):
  • Color: CLRn
  • Nationality: Nn
  • Pet: Pn
  • Drink: Dn
  • Car: Cn
Constraint modelling
Now that we have identified the variables and enumerated their domains, we need to formalize the constraints.

  1. All variables must have unique domain assignments. I.e. there can only be one blue house, only one yellow house, only one green house, only one ivory-colored house and only one red house, and so on...

    In logical notation this can be written as

    NONEEQUAL
    ∀n∈N,∀m∈N:(n≠m)∧(CLRn≠CLRm)∧(Nn≠Nm)∧(Dn≠Dm)∧(Pn≠Pm)∧(Cn≠Cm)

  2. The Enghlishman lives in the red house

    ∀n∈N:Nn=English⇒CLRn=Red

  3. The Spaniard owns the dog

    ∀n∈N:Nn=Spanish⇒Pn=Dog

  4. The man in the green house drinks cocoa

    ∀n∈N:CLRn=Green⇒Dn=Cocoa

  5. The Ukrainian drinks eggnog

    ∀n∈N:Nn=Ukrainian⇒Dn=eggnog

  6. The green house is immediately to the right (your right) of the ivory house

    ∀n∈N,(n<5):clrn=Ivory⇒CLRn+1=Green

  7. The owner of the Oldsmobile also owns snails

    ∀n∈N:Cn=Oldsmobile⇒Pn=Snail

  8. The owner of the Ford lives in the yellow house

    ∀n∈N:Cn=Ford⇒CLRn=Yellow

  9. The man in the middle house drinks milk

    D3=Milk

  10. The Norwegian lives in the first house on the left

    N3=Norwegian

  11. The man who owns the Chevrolet lives in the house next to the house where the man owns a fox

    ∀n∈N,(n<5):(cn=Chevrolet⇒Pn+1=Fox)∨(Pn=Fox⇒Cn+1=Chevrolet)

  12. The Ford owners's house is next to the house where the horse is kept

    ∀n∈N,(n<5):(cn=Ford⇒Pn+1=Horse)∨(Pn=Horse⇒Cn+1=Ford)

  13. The Mercedes-Benz owner drinks orange juice

    ∀n∈N:Cn=Mercedes Benz⇒Dn=Orange juice

  14. The Japanese drives a Volkswagen

    ∀n∈N:Nn=Japanese⇒Cn=Volkswagen

  15. The Norwegian lives next to the blue house

    ∀n∈N,(n<5):(nn=Norwegian⇒CLRn+1=Blue)∨(CLRn=Blue⇒Nn+1=Norwegian)
Implementing the model in SQL
Now for the fun part. We're going to model both the problem and the constraints in plain SQL so that the DBMS can search for a solution. We will do this without storing any data to a physical database table. Let's go.
  1. Implement the variable domains

    -- Setup variable domains (Color, Nationality, Pet, Drink, Car)
    CREATE OR REPLACE VIEW V_WOTZ_COLORS AS
    SELECT
    COLORS.V COLOR
    FROM
    (SELECT 'Red' V FROM DUAL UNION ALL
    SELECT 'Blue' V FROM DUAL UNION ALL
    SELECT 'Green' V FROM DUAL UNION ALL
    SELECT 'Ivory' V FROM DUAL UNION ALL
    SELECT 'Yellow' V FROM DUAL) COLORS;

    CREATE OR REPLACE VIEW V_WOTZ_NATIONALITIES AS
    SELECT
    NATIONALITIES.V NATIONALITY
    FROM
    (SELECT 'English' V FROM DUAL UNION ALL
    SELECT 'Spanish' V FROM DUAL UNION ALL
    SELECT 'Norwegian' V FROM DUAL UNION ALL
    SELECT 'Ukrainian' V FROM DUAL UNION ALL
    SELECT 'Japanese' V FROM DUAL) NATIONALITIES;

    CREATE OR REPLACE VIEW V_WOTZ_PETS AS
    SELECT
    PETS.V PET
    FROM
    (SELECT 'Dog' V FROM DUAL UNION ALL
    SELECT 'Snail' V FROM DUAL UNION ALL
    SELECT 'Fox' V FROM DUAL UNION ALL
    SELECT 'Horse' V FROM DUAL UNION ALL
    SELECT 'Zebra' V FROM DUAL) PETS;

    CREATE OR REPLACE VIEW V_WOTZ_DRINKS AS
    SELECT
    DRINKS.V DRINK
    FROM
    (SELECT 'Cocoa' V FROM DUAL UNION ALL
    SELECT 'Eggnog' V FROM DUAL UNION ALL
    SELECT 'Orange juice' V FROM DUAL UNION ALL
    SELECT 'Milk' V FROM DUAL UNION ALL
    SELECT 'Water' V FROM DUAL) DRINKS;

    CREATE OR REPLACE VIEW V_WOTZ_CARS AS
    SELECT
    CARS.V CAR
    FROM
    (SELECT 'Oldsmobile' V FROM DUAL UNION ALL
    SELECT 'Ford' V FROM DUAL UNION ALL
    SELECT 'Chevrolet' V FROM DUAL UNION ALL
    SELECT 'Mercedes Benz' V FROM DUAL UNION ALL
    SELECT 'Volkswagen' V FROM DUAL) CARS;

  2. Generate solutions and apply constraints. This is where we solve it!

    WITH SOLUTION AS
    -- Find a solution which satisfies the constraints
    (SELECT
    ROWNUM SOLUTION_ID,

    CLR1.COLOR CLR1,
    N1.NATIONALITY N1,
    P1.PET P1,
    D1.DRINK D1,
    C1.CAR C1,

    CLR2.COLOR CLR2,
    N2.NATIONALITY N2,
    P2.PET P2,
    D2.DRINK D2,
    C2.CAR C2,

    CLR3.COLOR CLR3,
    N3.NATIONALITY N3,
    P3.PET P3,
    D3.DRINK D3,
    C3.CAR C3,

    CLR4.COLOR CLR4,
    N4.NATIONALITY N4,
    P4.PET P4,
    D4.DRINK D4,
    C4.CAR C4,

    CLR5.COLOR CLR5,
    N5.NATIONALITY N5,
    P5.PET P5,
    D5.DRINK D5,
    C5.CAR C5
    FROM
    (SELECT COLOR FROM V_WOTZ_COLORS) CLR1,
    (SELECT COLOR FROM V_WOTZ_COLORS) CLR2,
    (SELECT COLOR FROM V_WOTZ_COLORS) CLR3,
    (SELECT COLOR FROM V_WOTZ_COLORS) CLR4,
    (SELECT COLOR FROM V_WOTZ_COLORS) CLR5,

    (SELECT NATIONALITY FROM V_WOTZ_NATIONALITIES) N1,
    (SELECT NATIONALITY FROM V_WOTZ_NATIONALITIES) N2,
    (SELECT NATIONALITY FROM V_WOTZ_NATIONALITIES) N3,
    (SELECT NATIONALITY FROM V_WOTZ_NATIONALITIES) N4,
    (SELECT NATIONALITY FROM V_WOTZ_NATIONALITIES) N5,

    (SELECT PET FROM V_WOTZ_PETS) P1,
    (SELECT PET FROM V_WOTZ_PETS) P2,
    (SELECT PET FROM V_WOTZ_PETS) P3,
    (SELECT PET FROM V_WOTZ_PETS) P4,
    (SELECT PET FROM V_WOTZ_PETS) P5,

    (SELECT DRINK FROM V_WOTZ_DRINKS) D1,
    (SELECT DRINK FROM V_WOTZ_DRINKS) D2,
    (SELECT DRINK FROM V_WOTZ_DRINKS) D3,
    (SELECT DRINK FROM V_WOTZ_DRINKS) D4,
    (SELECT DRINK FROM V_WOTZ_DRINKS) D5,

    (SELECT CAR FROM V_WOTZ_CARS) C1,
    (SELECT CAR FROM V_WOTZ_CARS) C2,
    (SELECT CAR FROM V_WOTZ_CARS) C3,
    (SELECT CAR FROM V_WOTZ_CARS) C4,
    (SELECT CAR FROM V_WOTZ_CARS) C5
    WHERE
    ((CLR1.COLOR NOT IN (CLR2.COLOR,CLR3.COLOR,CLR4.COLOR,CLR5.COLOR) AND
    CLR2.COLOR NOT IN (CLR3.COLOR,CLR4.COLOR,CLR5.COLOR) AND
    CLR3.COLOR NOT IN (CLR4.COLOR,CLR5.COLOR) AND
    CLR4.COLOR NOT IN (CLR5.COLOR)) AND
    (N1.NATIONALITY NOT IN (N2.NATIONALITY,N3.NATIONALITY,N4.NATIONALITY,N5.NATIONALITY) AND
    N2.NATIONALITY NOT IN (N3.NATIONALITY,N4.NATIONALITY,N5.NATIONALITY) AND
    N3.NATIONALITY NOT IN (N4.NATIONALITY,N5.NATIONALITY) AND
    N4.NATIONALITY NOT IN (N5.NATIONALITY)) AND
    (P1.PET NOT IN (P2.PET,P3.PET,P4.PET,P5.PET) AND
    P2.PET NOT IN (P3.PET,P4.PET,P5.PET) AND
    P3.PET NOT IN (P4.PET,P5.PET) AND
    P4.PET NOT IN (P5.PET)) AND
    (D1.DRINK NOT IN (D2.DRINK,D3.DRINK,D4.DRINK,D5.DRINK) AND
    D2.DRINK NOT IN (D3.DRINK,D4.DRINK,D5.DRINK) AND
    D3.DRINK NOT IN (D4.DRINK,D5.DRINK) AND
    D4.DRINK NOT IN (D5.DRINK)) AND
    (C1.CAR NOT IN (C2.CAR,C3.CAR,C4.CAR,C5.CAR) AND
    C2.CAR NOT IN (C3.CAR,C4.CAR,C5.CAR) AND
    C3.CAR NOT IN (C4.CAR,C5.CAR) AND
    C4.CAR NOT IN (C5.CAR)))
    AND
    (
    (N1.NATIONALITY = 'English' AND CLR1.COLOR = 'Red') OR
    (N2.NATIONALITY = 'English' AND CLR2.COLOR = 'Red') OR
    (N3.NATIONALITY = 'English' AND CLR3.COLOR = 'Red') OR
    (N4.NATIONALITY = 'English' AND CLR4.COLOR = 'Red') OR
    (N5.NATIONALITY = 'English' AND CLR5.COLOR = 'Red')
    )
    AND
    (
    (N1.NATIONALITY = 'Spanish' AND P1.PET = 'Dog') OR
    (N2.NATIONALITY = 'Spanish' AND P2.PET = 'Dog') OR
    (N3.NATIONALITY = 'Spanish' AND P3.PET = 'Dog') OR
    (N4.NATIONALITY = 'Spanish' AND P4.PET = 'Dog') OR
    (N5.NATIONALITY = 'Spanish' AND P5.PET = 'Dog')
    )
    AND
    (
    (CLR1.COLOR = 'Green' AND D1.DRINK = 'Cocoa') OR
    (CLR2.COLOR = 'Green' AND D2.DRINK = 'Cocoa') OR
    (CLR3.COLOR = 'Green' AND D3.DRINK = 'Cocoa') OR
    (CLR4.COLOR = 'Green' AND D4.DRINK = 'Cocoa') OR
    (CLR5.COLOR = 'Green' AND D5.DRINK = 'Cocoa')
    )
    AND
    (
    (N1.NATIONALITY = 'Ukrainian' AND D1.DRINK = 'Eggnog') OR
    (N2.NATIONALITY = 'Ukrainian' AND D2.DRINK = 'Eggnog') OR
    (N3.NATIONALITY = 'Ukrainian' AND D3.DRINK = 'Eggnog') OR
    (N4.NATIONALITY = 'Ukrainian' AND D4.DRINK = 'Eggnog') OR
    (N5.NATIONALITY = 'Ukrainian' AND D5.DRINK = 'Eggnog')
    )
    AND
    (
    (CLR1.COLOR = 'Ivory' AND CLR2.COLOR = 'Green') OR
    (CLR2.COLOR = 'Ivory' AND CLR3.COLOR = 'Green') OR
    (CLR3.COLOR = 'Ivory' AND CLR4.COLOR = 'Green') OR
    (CLR4.COLOR = 'Ivory' AND CLR5.COLOR = 'Green')
    )
    AND
    (
    (C1.CAR = 'Oldsmobile' AND P1.PET = 'Snail') OR
    (C2.CAR = 'Oldsmobile' AND P2.PET = 'Snail') OR
    (C3.CAR = 'Oldsmobile' AND P3.PET = 'Snail') OR
    (C4.CAR = 'Oldsmobile' AND P4.PET = 'Snail') OR
    (C5.CAR = 'Oldsmobile' AND P5.PET = 'Snail')
    )
    AND
    (
    (C1.CAR = 'Ford' AND CLR1.COLOR = 'Yellow') OR
    (C2.CAR = 'Ford' AND CLR2.COLOR = 'Yellow') OR
    (C3.CAR = 'Ford' AND CLR3.COLOR = 'Yellow') OR
    (C4.CAR = 'Ford' AND CLR4.COLOR = 'Yellow') OR
    (C5.CAR = 'Ford' AND CLR5.COLOR = 'Yellow')
    )
    AND
    (
    D3.DRINK = 'Milk'
    )
    AND
    (
    N1.NATIONALITY = 'Norwegian'
    )
    AND
    (
    (
    (C1.CAR = 'Chevrolet' AND P2.PET = 'Fox') OR
    (C2.CAR = 'Chevrolet' AND P3.PET = 'Fox') OR
    (C3.CAR = 'Chevrolet' AND P4.PET = 'Fox') OR
    (C4.CAR = 'Chevrolet' AND P5.PET = 'Fox')
    )
    OR
    (
    (P1.PET = 'Fox' AND C2.CAR = 'Chevrolet') OR
    (P2.PET = 'Fox' AND C3.CAR = 'Chevrolet') OR
    (P3.PET = 'Fox' AND C4.CAR = 'Chevrolet') OR
    (P4.PET = 'Fox' AND C5.CAR = 'Chevrolet')
    )
    )
    AND
    (
    (
    (C1.CAR = 'Ford' AND P2.PET = 'Horse') OR
    (C2.CAR = 'Ford' AND P3.PET = 'Horse') OR
    (C3.CAR = 'Ford' AND P4.PET = 'Horse') OR
    (C4.CAR = 'Ford' AND P5.PET = 'Horse')
    )
    OR
    (
    (P1.PET = 'Horse' AND C2.CAR = 'Ford') OR
    (P2.PET = 'Horse' AND C3.CAR = 'Ford') OR
    (P3.PET = 'Horse' AND C4.CAR = 'Ford') OR
    (P4.PET = 'Horse' AND C5.CAR = 'Ford')
    )
    )
    AND
    (
    (C1.CAR = 'Mercedes Benz' AND D1.DRINK = 'Orange juice') OR
    (C2.CAR = 'Mercedes Benz' AND D2.DRINK = 'Orange juice') OR
    (C3.CAR = 'Mercedes Benz' AND D3.DRINK = 'Orange juice') OR
    (C4.CAR = 'Mercedes Benz' AND D4.DRINK = 'Orange juice') OR
    (C5.CAR = 'Mercedes Benz' AND D5.DRINK = 'Orange juice')
    )
    AND
    (
    (N1.NATIONALITY = 'Japanese' AND C1.CAR = 'Volkswagen') OR
    (N2.NATIONALITY = 'Japanese' AND C2.CAR = 'Volkswagen') OR
    (N3.NATIONALITY = 'Japanese' AND C3.CAR = 'Volkswagen') OR
    (N4.NATIONALITY = 'Japanese' AND C4.CAR = 'Volkswagen') OR
    (N5.NATIONALITY = 'Japanese' AND C5.CAR = 'Volkswagen')
    )
    AND
    (
    (
    (N1.NATIONALITY = 'Norwegian' AND CLR2.COLOR = 'Blue') OR
    (N2.NATIONALITY = 'Norwegian' AND CLR3.COLOR = 'Blue') OR
    (N3.NATIONALITY = 'Norwegian' AND CLR4.COLOR = 'Blue') OR
    (N4.NATIONALITY = 'Norwegian' AND CLR5.COLOR = 'Blue')
    )
    OR
    (
    (CLR1.COLOR = 'Blue' AND N2.NATIONALITY = 'Norwegian') OR
    (CLR2.COLOR = 'Blue' AND N3.NATIONALITY = 'Norwegian') OR
    (CLR3.COLOR = 'Blue' AND N4.NATIONALITY = 'Norwegian') OR
    (CLR4.COLOR = 'Blue' AND N5.NATIONALITY = 'Norwegian')
    )
    ))
    SELECT
    'Color' VARIABLE,
    CLR1 HOUSE1,
    CLR2 HOUSE2,
    CLR3 HOUSE3,
    CLR4 HOUSE4,
    CLR5 HOUSE5
    FROM
    SOLUTION
    UNION ALL
    SELECT
    'Nationality' VARIABLE,
    N1 HOUSE1,
    N2 HOUSE2,
    N3 HOUSE3,
    N4 HOUSE4,
    N5 HOUSE5
    FROM
    SOLUTION
    UNION ALL
    SELECT
    'Drink' VARIABLE,
    D1 HOUSE1,
    D2 HOUSE2,
    D3 HOUSE3,
    D4 HOUSE4,
    D5 HOUSE5
    FROM
    SOLUTION
    UNION ALL
    SELECT
    'Pet' VARIABLE,
    P1 HOUSE1,
    P2 HOUSE2,
    P3 HOUSE3,
    P4 HOUSE4,
    P5 HOUSE5
    FROM
    SOLUTION
    UNION ALL
    SELECT
    'Car' VARIABLE,
    C1 HOUSE1,
    C2 HOUSE2,
    C3 HOUSE3,
    C4 HOUSE4,
    C5 HOUSE5
    FROM
    SOLUTION;
Result
The DBMS found the only solution to the problem given the constraints.
The answer to the question: The Japanese owns the Zebra! What's cool is that the DBMS found the answer.

Discussion
The SQL methodology is as follows.
  1. Do a cartesian join on all the 25 variables. We'll call this the UNIVERSAL set.

    This yields (55)5 combinations, an unmanageable amount of data. Which is why we need to apply step 2.

  2. Apply the constraints. This is done in the where-clause of the SQL statement.

    After we've applied the NONEEQUAL constraint, the number of combinations have been reduced to (5!)5

    Note that the SQL statement above never stores all these combinations to a physical table or in memory. The trick is that the DBMS will build the result set by applying the given constraints (from the where-clause) in the order it finds most efficient. Not until all the constraints have been satisfied, will the DBMS present the result set.
Try it! It works.

No comments:

Post a Comment