"Einsteins's Riddle", (there is serious doubt that he was actually the author), is similar to the type of logic problem you see in LSAT, GRE, and GMAT. It's a nice reference problem because of it's popularity and familiarity(plus , it sounds soooo much more important to solve "Einsteins's" riddle). Can this riddle be solved using semantic web technology like OWL? Let's see -
THE RIDDLE -
1. In a street there are five houses, painted five different colours.
2. In each house lives a person of different nationality
3. These five homeowners each drink a different kind of beverage, smoke different brand of cigar and keep a different pet.
THE QUESTION: WHO OWNS THE FISH?
HINTS
1. The Brit lives in a red house.
2. The Swede keeps dogs as pets.
3. The Dane drinks tea.
4. The Green house is next to, and on the left of the White house.
5. The owner of the Green house 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 centre 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 horses lives next to the man who smokes Dunhill.
12. The man who smokes Blue Master 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.
So, we're going to solvethis with OWL -
When we translate this into an OWL problem and turn on the inferencer (I'm using Pellet 2.0.0 with Protege 3.3.1) we get:
Notice that the fish lover is in the German set. So, that is the answer, and is the correct one (for this version of the riddle; there are variants, but essentially the same)
Sometimes, it is interesting to see how a solution type solves a problem, even if it is not a "practical way". You get a sense of the limitations of the solution type (expressitivity - is it awkward for this type of problem?, efficiency - what's the time complexity look like? or space?, etc.) and you get a sense of the what is different about this solution space. After all, each solution type gets the answer - how are they related? how are they different?
Simple forcing strategy:
There's an old saw in computer science that says: "There are only two problems in computer science: naming things, and cache coherence" -
Naming things - we just pretend we know by "naming" - for example, I know who lives in the yellow house - "Owner_of_the_Yellow_House" - that's who...
References (man who drinks tea, for example) are assigned to individuals, e.g. individual: Tea_Drinker)
From this you get:
Person_in_the_SecondHouse, Person_in_the_ThirdHouse, Person_in_the_FourthHouse, Person_in_the_FifthHouse, Person_in_the_FirstHouse, Norwegian, Owner_of_the_Blue_House, Dane, Brit, Swede, German, Cat_Lover, Blends_Smoker, Water_Drinker, Owner_of_the_Green_House, Owner_of_the_White_House, Owner_of_the_Red_House, Owner_of_the_Yellow_House, Horse_Lover, Dunhill_Smoker, BlueMaster_Smoker, Dog_Lover, Beer_Drinker, Bird_Lover, Fish_Lover, Coffee_Drinker, Milk_Drinker, Tea_Drinker, PallMall_Smoker, Prince_Smoker
Cache Coherence - where we force things to take on traits based on their set (guilt by association)
We take the simplest type: consistency.
Each individual from above is equivalent to one of the five: swede, norwegian, brit, german, dane. We now define properties that allow us to enforce the constraints via functional relationships. For example, rule 6. The person who smokes Pall Mall rears birds. is encoded by defining a property called drinks, with domain = person and range = drink.
Then the individual: PallMall_Smoker drinks Milk.
These are the easy ones to see. About 2/3 of the way down they start getting a little more obscure, like rule 10. The man who smokes Blends lives next to the one who keeps cats.
But this is still the same thing actually. We define a property: lives_next_to (by the way, it has sub-properties lives_left_of and lives_right_of) and it's the same thing:
individual: Blends_Smoker lives_next_to Cat_Lover.
Finally, we have to embed some geometry about (ordered) houses, like the each house has a max number of neighbors = 2, and that the center house is house 3 and the first house is house 1 and so on. We also have to distinguish the first and last houses with some defined sets, since we want the inferencer to use them as a point of reference. This puts classification in the drivers seat, and allows us to see how a world dominated by primitive set theory and simple classification operates with respect to the types of problems this riddle represents.
The OWL file is at the bottom of this post, so you can go there to see a complete list of constraaints etc. Better yet, bring it into your ontology browser and play with it (I used Protege 3.3.1 browser and Pellet 2.0.0 for the inferencer)
OWL will infer that two individuals y, z are identical (sameAs) if f(x) = y and f(x) - z.
So relations will force some indiviuals to start pairing up.
In addition, there is a musical chairs thing going on with the sets representing each nationality.
There are 6 times as many individuals as needed (5 traits for each nationality = 6 traits and 5 indiviuals) we have 30 - but they have to pair up into 5 without violating the rules which are:
EquivalentTo:
({Brit , Dane , German , Norwegian , Swede})
and (lives_next_to min 1 owl:Thing)
and (drinks exactly 1 owl:Thing)
and (keeps exactly 1 owl:Thing)
and (smokes exactly 1 owl:Thing)
and (lives_next_to max 2 owl:Thing)
This "forces" individuals to pair up with a "true" individual (sweded, dane, etc.) as well.
So these sets are the 5 chairs and the individuals run around trying to find someone sitting in a chair that is missing their part (pet, tobacco, drink, housecolor, etc.) -
There are lots of problems like this - and we have this mechanical approach now -
For each clue, assign an individual. Define constraints through property restrictions and set inclusion (e.g. simple set theory) -
Record facts through indiviual property values.
Turn on inferencer and enjoy.
Scalability is bad - true - but for modest problems, like.....guess what this is -
individuals:
owner_of_knife
last_viewer_of_file
victim
assailant
driver_of_car_leaving_tire_prints_#a14-789-22
etc.
What type of problem does this represent?
Why do we test for the ability to solve these?
We can think of it as jigsaw puzzles within a bigger jiggsaw puzzle.
This technique of using lots of individuals to solve a problem is fine for a machine or something that can keep track of lots of relationships - like a neural net or relational database or even nature. Sets scale poorly unless there is a corresponding increase in parallelism. Nevertheless, we just want to see what happens in this world, not necessarily, apply it.
If we change the "substance" from hypotheticals from the real world to a semantic world, then things change in utility. For example, we can think of each instant of history as an individual that is equivalent to some part of the future - we can talk about how much of the information endures in the next ensemble of information. Each moment then is an instance of one set of conditions and each of these has a relationship to other moments in other places and at other times, new "prime" individuals will rise up over time: democracy, fascism, tolerance, intolerance, new modernisms, and so on. Past moments will try to assemble themselves into the new individuals or eventually die out.
We can assign an individual to each subject or object from the facts, and a property to each verb (or action word) - record all of the conditions and constraints and then infer about soundness -
The main point is that we (or any agent that wants to) can mindlessly assign individuals to big messy problems and see why we get the answer we do.
Anything that is a "mystery" with "clues" can be solved this way....does your life have "mystery"? Do you have any "clues"?
Once we know that certain types of problems can be solved by assigning individuals to each "clue", clues start looking different.....and so do individuals.
Grand deduction sometimes has to give way to gritty detailed deduction, where everything is an individual - like you or me.....every clue, every piece of the puzzle, assigned to an individual with properties, looking for a chair before the music stops......
more on all this later - for now, here's the OWL:
(*NB* you'll have to replace zttp with http - I had to do this to avoid google constraints)
--------------------------------------------------------
default:Person_in_the_SecondHouse a default:Person ; default:left_of default:Person_in_the_ThirdHouse ; default:right_of default:Person_in_the_FirstHouse .
default:Beverage a owl:Class ; owl:equivalentClass [ a owl:Class ; owl:oneOf (default:Tea default:Beer default:Milk default:Water default:Coffee) ] .
default:Cat_Lover a default:Person ; default:keeps default:Cat ; default:lives_next_to default:Blends_Smoker .
[] a owl:AllDifferent ; owl:distinctMembers (default:Bird_Lover default:Cat_Lover default:Dog_Lover default:Fish_Lover default:Horse_Lover) .
default:Horse_Lover a default:Person ; default:keeps default:Horse ; default:lives_next_to default:Dunhill_Smoker .
default:Milk a default:Beverage .
default:Person_in_the_FourthHouse a default:Person ; default:left_of default:Person_in_the_FifthHouse ; default:right_of default:Person_in_the_ThirdHouse .
default:Pet a owl:Class ; owl:equivalentClass [ a owl:Class ; owl:oneOf (default:Dog default:Fish default:Horse default:Bird default:Cat) ] .
default:Horse a default:Pet .
default:Norwegian a default:NorwegianClass , default:Person ; default:lives_next_to default:Owner_of_the_Blue_House .
default:PallMall a default:Tobacco .
default:drinks a owl:ObjectProperty ; rdfs:domain default:Person .
default:BlueMaster_Smoker a default:Person ; default:drinks default:Beer ; default:smokes default:BlueMaster .
default:Blends_Smoker a default:Person ; default:lives_next_to default:Cat_Lover , default:Water_Drinker ; default:smokes default:Blends .
default:Owner_of_the_Green_House a default:Person ; default:drinks default:Coffee ; default:left_of default:Owner_of_the_White_House .
default:Blends a default:Tobacco .
default:keeps a owl:ObjectProperty , owl:InverseFunctionalProperty , owl:FunctionalProperty ; rdfs:domain default:Person ; rdfs:range default:Pet .
default:Dunhill_Smoker a default:Person ; default:lives_next_to default:Horse_Lover ; default:smokes default:Dunhill .
{http://www.ndfa01.com/ontologies/EinsteinRiddle-3.owl} a owl:Ontology .
default:Dog_Lover a default:Person ; default:keeps default:Dog .
default:Prince a default:Tobacco .
default:Owner_of_the_Blue_House a default:Person ; default:lives_next_to default:Norwegian .
[] a owl:AllDifferent ; owl:distinctMembers (default:Brit default:Dane default:German default:Norwegian default:Swede) .
default:GermanClass a owl:Class ; rdfs:subClassOf default:Person ; owl:disjointWith default:BritClass , default:NorwegianClass , default:SwedeClass , default:DaneClass ; owl:equivalentClass [ a owl:Restriction ; owl:hasValue default:Prince ; owl:onProperty default:smokes ] .
default:Person_in_the_FifthHouse a default:Person_in_the_LastHouseClass , default:Person ; default:right_of default:Person_in_the_FourthHouse .
default:German a default:GermanClass , default:Person ; default:smokes default:Prince .
default:Dunhill a default:Tobacco .
default:Water_Drinker a default:Person ; default:drinks default:Water ; default:lives_next_to default:Blends_Smoker .
default:Person a owl:Class ; owl:equivalentClass [ a owl:Class ; owl:intersectionOf ([ a owl:Class ; owl:oneOf (default:Norwegian default:Dane default:Brit default:Swede default:German) ] [ a owl:Restriction ; owl:minCardinality "1"^^xsd:int ; owl:onProperty default:lives_next_to ] [ a owl:Restriction ; owl:maxCardinality "2"^^xsd:int ; owl:onProperty default:lives_next_to ] [ a owl:Restriction ; owl:cardinality "1"^^xsd:int ; owl:onProperty default:keeps ] [ a owl:Restriction ; owl:cardinality "1"^^xsd:int ; owl:onProperty default:drinks ] [ a owl:Restriction ; owl:cardinality "1"^^xsd:int ; owl:onProperty default:smokes ]) ] .
default:BlueMaster a default:Tobacco .
default:Bird a default:Pet .
default:Person_in_the_FirstHouseClass a owl:Class ; rdfs:subClassOf default:Person ; owl:equivalentClass [ a owl:Class ; owl:intersectionOf ([ a owl:Restriction ; owl:cardinality "1"^^xsd:int ; owl:onProperty default:lives_next_to ] [ a owl:Restriction ; owl:hasValue default:Person_in_the_SecondHouse ; owl:onProperty default:left_of ]) ] .
default:Beer_Drinker a default:Person ; default:drinks default:Beer .
default:Tobacco a owl:Class ; rdfs:subClassOf owl:Thing ; rdfs:subClassOf [ a owl:Class ; owl:oneOf (default:Prince default:Blends default:PallMall default:BlueMaster default:Dunhill) ] ; owl:equivalentClass [ a owl:Class ; owl:oneOf (default:Prince default:Blends default:PallMall default:BlueMaster default:Dunhill) ] .
default:left_of a owl:ObjectProperty , owl:InverseFunctionalProperty , owl:FunctionalProperty ; rdfs:subPropertyOf default:lives_next_to ; owl:inverseOf default:right_of .
[] a owl:AllDifferent ; owl:distinctMembers (default:Beer_Drinker default:Coffee_Drinker default:Milk_Drinker default:Tea_Drinker default:Water_Drinker) .
default:Owner_of_the_Yellow_House a default:Person ; default:smokes default:Dunhill .
default:Owner_of_the_Red_House a default:BritClass , default:Person .
default:Dane a default:DaneClass , default:Person ; default:drinks default:Tea .
default:Swede a default:SwedeClass , default:Person ; default:keeps default:Dog .
default:lives_next_to a owl:ObjectProperty , owl:SymmetricProperty ; rdfs:domain default:Person ; rdfs:range default:Person ; owl:inverseOf default:lives_next_to .
[] a owl:AllDifferent ; owl:distinctMembers (default:Milk default:Beer default:Water default:Tea default:Coffee) .
default:Tea a default:Beverage .
default:Coffee_Drinker a default:Person ; default:drinks default:Coffee .
default:SwedeClass a owl:Class ; rdfs:subClassOf default:Person ; owl:disjointWith default:BritClass , default:NorwegianClass , default:GermanClass , default:DaneClass ; owl:equivalentClass [ a owl:Restriction ; owl:hasValue default:Dog ; owl:onProperty default:keeps ] .
default:Person_in_the_LastHouseClass a owl:Class ; rdfs:subClassOf default:Person ; owl:equivalentClass [ a owl:Class ; owl:intersectionOf ([ a owl:Restriction ; owl:cardinality "1"^^xsd:int ; owl:onProperty default:lives_next_to ] [ a owl:Restriction ; owl:hasValue default:Person_in_the_FourthHouse ; owl:onProperty default:right_of ]) ] .
default:Bird_Lover a default:Person ; default:keeps default:Bird .
default:Fish_Lover a default:Person ; default:keeps default:Fish .
default:Milk_Drinker a default:Person ; default:drinks default:Milk .
default:Beer a default:Beverage .
default:Water a default:Beverage .
default:smokes a owl:ObjectProperty , owl:InverseFunctionalProperty , owl:FunctionalProperty ; rdfs:domain default:Person ; rdfs:range default:Tobacco .
default:Brit a default:BritClass , default:Person .
default:DaneClass a owl:Class ; rdfs:subClassOf default:Person ; owl:disjointWith default:BritClass , default:NorwegianClass , default:GermanClass , default:SwedeClass ; owl:equivalentClass [ a owl:Restriction ; owl:hasValue default:Tea ; owl:onProperty default:drinks ] .
default:Fish a default:Pet .
default:Dog a default:Pet .
[] a owl:AllDifferent ; owl:distinctMembers (default:Blends default:PallMall default:Prince default:BlueMaster default:Dunhill) .
default:NorwegianClass a owl:Class ; rdfs:subClassOf default:Person ; owl:disjointWith default:BritClass , default:GermanClass , default:SwedeClass , default:DaneClass .
[] a owl:AllDifferent ; owl:distinctMembers (default:Blends_Smoker default:BlueMaster_Smoker default:Dunhill_Smoker default:PallMall_Smoker default:Prince_Smoker) .
[] a owl:AllDifferent ; owl:distinctMembers (default:Cat default:Dog default:Horse default:Bird default:Fish) .
default:Prince_Smoker a default:Person ; default:smokes default:Prince .
[] a owl:AllDifferent ; owl:distinctMembers (default:Owner_of_the_Blue_House default:Owner_of_the_Green_House default:Owner_of_the_Red_House default:Owner_of_the_White_House default:Owner_of_the_Yellow_House) .
default:BritClass a owl:Class ; rdfs:subClassOf default:Person ; owl:disjointWith default:NorwegianClass , default:GermanClass , default:SwedeClass , default:DaneClass .
default:Cat a default:Pet .
default:Person_in_the_ThirdHouse a default:Person ; default:drinks default:Milk ; default:left_of default:Person_in_the_FourthHouse ; default:right_of default:Person_in_the_SecondHouse .
[] a owl:AllDifferent ; owl:distinctMembers (default:Person_in_the_FirstHouse default:Person_in_the_SecondHouse default:Person_in_the_ThirdHouse default:Person_in_the_FourthHouse default:Person_in_the_FifthHouse) .
default:PallMall_Smoker a default:Person ; default:keeps default:Bird ; default:smokes default:PallMall .
default:Owner_of_the_White_House a default:Person ; default:right_of default:Owner_of_the_Green_House .
default:Coffee a default:Beverage .
default:Person_in_the_FirstHouse a default:NorwegianClass , default:Person_in_the_FirstHouseClass , default:Person ; default:left_of default:Person_in_the_SecondHouse .
default:Tea_Drinker a default:Person ; default:drinks default:Tea .
default:right_of a owl:ObjectProperty , owl:InverseFunctionalProperty , owl:FunctionalProperty ; rdfs:subPropertyOf default:lives_next_to ; owl:inverseOf default:left_of .
