# Einstein's Riddle

Brian Harvey bh at abbenay.cs.berkeley.edu
Sun Mar 11 19:43:00 EST 2001

```"Boris Popov" <no-spam-popov at bigserver.com> writes:
>house         1 2 3 4 5
>color            yellow blue red green white
>nationality   norweigian dane brit german swede
>drink            water tea milk coffee beer
>smoke        dunhill blend pall mall prince bluemaster
>pet              cats horse birds fish dogs
>
>P.S. Did I have to write software to solve it ? :)

I can't resist being (apparently) first to post a computer program.
But it doesn't really belong in any of these newsgroups, because it's
written in Logo.

First get Berkeley Logo from ftp://ftp.cs.berkeley.edu/ucblogo/
(pick the one that matches your platform)

Then get the logic-puzzle-solver from
http://www.cs.berkeley.edu/~bh/logic-code/hybrid.lg

Then here's the part specific to this puzzle:

? po [einstein neighbor neighbor1]
to einstein
cleanup
category "position [1 2 3 4 5]
category "color [red green white yellow blue]
category "nationality [British Swedish Danish Norwegian German]
category "beverage [tea coffee milk beer water]
category "cigar [pallmall dunhill blend bluemaster prince]
category "pet [dog bird cat horse fish]
verify "British "red
verify "Swedish "dog
verify "Danish "tea
justbefore "green "white :position
verify "green "coffee
verify "pallmall "bird
verify "yellow "dunhill
verify 3 "milk
verify 1 "Norwegian
neighbor "blend "cat :position
neighbor "horse "dunhill :position
verify "bluemaster "beer
verify "German "prince
neighbor "Norwegian "blue :position
neighbor "blend "water :position
print []
solution
end

to neighbor :a :b :lineup
falsify :a :b
neighbor1 :lineup count :lineup
end

to neighbor1 :lineup :count
if :count=0 [stop]
foreach bl bf bf :lineup [implies :a first :lineup "true :b ? "false]
neighbor1 (lput first :lineup bf :lineup) :count-1
end

? solve [einstein]
category position [1 2 3 4 5]
category color [red green white yellow blue]
category nationality [British Swedish Danish Norwegian German]
category beverage [tea coffee milk beer water]
category cigar [pallmall dunhill blend bluemaster prince]
category pet [dog bird cat horse fish]
British red -> true
Swedish red -> false
Danish red -> false
Norwegian red -> false
German red -> false
green British -> false
white British -> false
yellow British -> false
blue British -> false
Swedish dog -> true
British dog -> false
red dog -> false
Danish dog -> false
Norwegian dog -> false
German dog -> false
bird Swedish -> false
cat Swedish -> false
horse Swedish -> false
fish Swedish -> false
Danish tea -> true
British tea -> false
red tea -> false
Swedish tea -> false
dog tea -> false
Norwegian tea -> false
German tea -> false
coffee Danish -> false
milk Danish -> false
beer Danish -> false
water Danish -> false
green 5 -> false
white 1 -> false
green coffee -> true
red coffee -> false
British coffee -> false
white coffee -> false
yellow coffee -> false
blue coffee -> false
5 coffee -> false
tea green -> false
Danish green -> false
milk green -> false
beer green -> false
water green -> false
pallmall bird -> true
dunhill bird -> false
blend bird -> false
bluemaster bird -> false
prince bird -> false
dog pallmall -> false
Swedish pallmall -> false
cat pallmall -> false
horse pallmall -> false
fish pallmall -> false
yellow dunhill -> true
red dunhill -> false
British dunhill -> false
green dunhill -> false
coffee dunhill -> false
white dunhill -> false
blue dunhill -> false
pallmall yellow -> false
bird yellow -> false
blend yellow -> false
bluemaster yellow -> false
prince yellow -> false
3 milk -> true
1 milk -> false
2 milk -> false
4 milk -> false
5 milk -> false
tea 3 -> false
Danish 3 -> false
coffee 3 -> false
green 3 -> false
white 4 -> false
beer 3 -> false
water 3 -> false
1 Norwegian -> true
2 Norwegian -> false
3 Norwegian -> false
milk Norwegian -> false
4 Norwegian -> false
5 Norwegian -> false
white Norwegian -> false
British 1 -> false
red 1 -> false
Swedish 1 -> false
dog 1 -> false
Danish 1 -> false
tea 1 -> false
German 1 -> false
blend cat -> false
horse dunhill -> false
yellow horse -> false
bluemaster beer -> true
pallmall beer -> false
bird beer -> false
dunhill beer -> false
yellow beer -> false
blend beer -> false
prince beer -> false
tea bluemaster -> false
Danish bluemaster -> false
coffee bluemaster -> false
green bluemaster -> false
milk bluemaster -> false
3 bluemaster -> false
water bluemaster -> false
German prince -> true
British prince -> false
red prince -> false
Swedish prince -> false
dog prince -> false
Danish prince -> false
tea prince -> false
Norwegian prince -> false
1 prince -> false
pallmall German -> false
bird German -> false
dunhill German -> false
yellow German -> false
blend German -> false
bluemaster German -> false
beer German -> false
Norwegian blue -> false
1 blue -> false
blue 3 -> false
milk blue -> false
blue 4 -> false
blend water -> false

Assuming 1 yellow
1 yellow -> true
2 yellow -> false
dunhill 2 -> false
3 yellow -> false
milk yellow -> false
dunhill milk -> false
3 dunhill -> false
4 yellow -> false
dunhill 4 -> false
5 yellow -> false
dunhill 5 -> false
1 dunhill -> true
Norwegian dunhill -> true
Swedish dunhill -> false
dog dunhill -> false
yellow dog -> false
Swedish yellow -> false
Danish dunhill -> false
tea dunhill -> false
water dunhill -> true
pallmall water -> false
bird water -> false
prince water -> false
German water -> false
yellow water -> true
red water -> false
British water -> false
white water -> false
blue water -> false
Swedish water -> false
Norwegian water -> true
1 water -> true
2 water -> false
4 water -> false
5 water -> false
dog water -> false
coffee 1 -> false
green 1 -> false
Norwegian green -> false
yellow Norwegian -> true
beer Norwegian -> false
bluemaster Norwegian -> false
1 bluemaster -> false
beer 1 -> false
horse Norwegian -> false
1 horse -> false
water horse -> false
blend Norwegian -> false
1 blend -> false
pallmall Norwegian -> false
bird Norwegian -> false
1 bird -> false
pallmall 1 -> false
coffee Norwegian -> false
Danish yellow -> false
tea yellow -> false
white 2 -> false
blend 4 -> false
blend 3 -> false
milk blend -> false
horse 4 -> false
horse 3 -> false
milk horse -> false

Assuming 5 beer
5 beer -> true
2 beer -> false
bluemaster 2 -> false
4 beer -> false
bluemaster 4 -> false
5 bluemaster -> true
pallmall 5 -> false
bird 5 -> false
blend 5 -> false
2 blend -> true
white blend -> false
pallmall 2 -> false
bird 2 -> false
prince 2 -> false
German 2 -> false
cat 2 -> false
cat 5 -> false
bluemaster cat -> false
beer cat -> false
cat 4 -> false
prince 5 -> false
German 5 -> false
tea 5 -> false
Danish 5 -> false

Assuming 5 Swedish
5 Swedish -> true
2 Swedish -> false
blend Swedish -> false
bluemaster Swedish -> true
beer Swedish -> true
coffee Swedish -> false
green Swedish -> false
German green -> true
prince green -> true
pallmall green -> false
bird green -> false
coffee bird -> false
pallmall coffee -> false
blend green -> false
2 green -> false
4 green -> true
cat green -> false
coffee cat -> false
horse green -> false
coffee horse -> false
red 4 -> false
British 4 -> false
coffee 4 -> true
tea 4 -> false
Danish 4 -> false
2 Danish -> true
blend Danish -> true
pallmall Danish -> false
bird Danish -> false
British bird -> true
red bird -> true
white bird -> false
pallmall white -> false
blue bird -> false
pallmall blue -> false
red pallmall -> true
British pallmall -> true
4 pallmall -> false
3 pallmall -> true
milk pallmall -> true
tea pallmall -> false
blend tea -> true
2 tea -> true
cat tea -> false
Danish cat -> false
bird tea -> false
milk bird -> true
3 bird -> true
4 bird -> false
dog 3 -> false
Swedish 3 -> false
milk Swedish -> false
dog milk -> false
cat 3 -> false
1 cat -> true
yellow cat -> true
red cat -> false
British cat -> false
white cat -> false
blue cat -> false
water cat -> true
milk cat -> false
Norwegian cat -> true
German cat -> false
prince cat -> false
dunhill cat -> true
fish dunhill -> false
1 fish -> false
yellow fish -> false
water fish -> false
Norwegian fish -> false
fish 3 -> false
milk fish -> false
white 3 -> false
red 3 -> true
British 3 -> true
German 3 -> false
prince 3 -> false
4 prince -> true
horse prince -> false
fish prince -> true
milk prince -> false
coffee prince -> true
blue prince -> false
German blue -> false
white prince -> false
bluemaster white -> true
5 white -> true
beer white -> true
tea white -> false
Danish white -> false
blue Danish -> true
Swedish blue -> false
dog blue -> false
white Swedish -> true
4 Swedish -> false
German 4 -> true
dog 4 -> false
fish 4 -> true
2 fish -> false
blend fish -> false
5 fish -> false
beer fish -> false
bluemaster fish -> false
green fish -> true
red fish -> false
British fish -> false
white fish -> false
blue fish -> false
Danish fish -> false
German fish -> true
tea fish -> false
coffee fish -> true
dog coffee -> false
beer dog -> true
5 dog -> true
2 dog -> false
blend dog -> false
bluemaster dog -> true
green dog -> false
white dog -> true
horse white -> false
milk white -> false
red milk -> true
British milk -> true
German milk -> false
coffee German -> true
horse German -> false
white German -> false
2 coffee -> false
blend coffee -> false
beer British -> false
5 British -> false
bluemaster British -> false
red bluemaster -> false
5 red -> false
beer red -> false
horse British -> false
Danish horse -> true
tea horse -> true
beer horse -> false
5 horse -> false
2 horse -> true
blend horse -> true
bluemaster horse -> false
British blend -> false
red blend -> false
blue blend -> true
bluemaster blue -> false
5 blue -> false
2 blue -> true
beer blue -> false
tea blue -> true
red 2 -> false
British 2 -> false
horse blue -> true
red horse -> false

1 yellow Norwegian water dunhill cat
2 blue Danish tea blend horse
3 red British milk pallmall bird
4 green German coffee prince fish
5 white Swedish beer bluemaster dog

```