How to solve the Zebra Puzzle in SQL
July 5th, 2010 By newkid
From Wikipedia http://en.wikipedia.org/wiki/Zebra_Puzzle:
The Zebra Puzzle is a well-known logic puzzle. It is often called Einstein’s Puzzle or Einstein’s Riddle because it is said to have been invented by Albert Einstein as a boy. Some claim that Einstein said “only 2 percent of the world’s population can solve it.” It is also sometimes attributed to Lewis Carroll.
However, there is no known evidence for Einstein’s or Carroll’s authorship; and the original puzzle mentions brands of cigarette, such as Kools, that did not exist during Carroll’s lifetime or Einstein’s boyhood.
There are several versions of this puzzle, below is one of them:
The British lives in the red house.
The Swede keeps dogs as pets.
The Dane drinks tea.
The green house is on the left of the white house.
The green homeowner drinks coffee.
The man who smokes Pall Mall keeps birds.
The owner of the yellow house smokes Dunhill.
The man living in the center house drinks milk.
The Norwegian lives in the first house.
The man who smokes Blend lives next to the one who keeps cats.
The man who keeps the horse lives next to the man who smokes Dunhill.
The man who smokes Bluemaster drinks beer.
The German smokes Prince.
The Norwegian lives next to the blue house.
The man who smokes Blend has a neighbor who drinks water.
Question: Who owns the fish?
SQL solution:
WITH comb as ( ----- Permutations of number 1-5. they can be interpreted as other properties, and the position of number in string p means room number
SELECT REPLACE(SYS_CONNECT_BY_PATH(rn,'\'),'\') AS p
FROM (SELECT ROWNUM rn FROM DUAL CONNECT BY ROWNUM<=5)
WHERE LEVEL=5
CONNECT BY NOCYCLE LEVEL<=5 AND rn<>PRIOR rn
)
,nationality AS (
SELECT INSTR(p,'1') AS Englishman
,INSTR(p,'2') AS Swede
,INSTR(p,'3') AS Dane
,INSTR(p,'4') AS Norwegian
,INSTR(p,'5') AS German
FROM comb
)
,house AS (
SELECT INSTR(p,'1') AS red
,INSTR(p,'2') AS white
,INSTR(p,'3') AS green
,INSTR(p,'4') AS yellow
,INSTR(p,'5') AS blue
FROM comb
)
,beverages AS (
SELECT INSTR(p,'1') AS tea
,INSTR(p,'2') AS coffee
,INSTR(p,'3') AS milk
,INSTR(p,'4') AS beer
,INSTR(p,'5') AS water
FROM comb
)
,cigarettes AS (
SELECT INSTR(p,'1') AS pall_mall
,INSTR(p,'2') AS dunhill
,INSTR(p,'3') AS blends
,INSTR(p,'4') AS blue_master
,INSTR(p,'5') AS prince
FROM comb
)
,pets AS (
SELECT INSTR(p,'1') AS dog
,INSTR(p,'2') AS bird
,INSTR(p,'3') AS cat
,INSTR(p,'4') AS horse
,INSTR(p,'5') AS fish
FROM comb
)
,res AS (
SELECT *
FROM nationality
,house
,beverages
,cigarettes
,pets
WHERE Englishman = red ---- join condition: different properties appear in the same room number, or number of next room
AND Swede = dog
AND Dane = tea
AND green = white -1
AND green = coffee
AND pall_mall = bird
AND yellow = dunhill
AND milk = 3
AND Norwegian = 1
AND ABS(blends - cat) =1
AND ABS(dunhill - horse) =1
AND blue_master = beer
AND German = prince
AND blue = 2
AND ABS(blends - water) =1
)
SELECT room_num
,DECODE(room_num,Englishman,'Englishman',Swede ,'Swede' ,Dane ,'Dane' ,Norwegian ,'Norwegian' ,German,'German') as nationality
,DECODE(room_num,red ,'red' ,white ,'white' ,green ,'green' ,yellow ,'yellow' ,blue ,'blue' ) as house
,DECODE(room_num,pall_mall ,'pall mall' ,dunhill ,'dunhill',blends,'blends',blue_master,'blue master',prince,'prince') as beverages
,DECODE(room_num,tea ,'tea' ,coffee ,'coffee' ,milk ,'milk' ,beer ,'beer' ,water ,'water' ) as cigarettes
,DECODE(room_num,dog ,'dog' ,bird ,'bird' ,cat ,'cat' ,horse ,'horse' ,fish ,'fish' ) as pets
FROM res,(SELECT ROWNUM room_num FROM DUAL CONNECT BY ROWNUM<=5)
ORDER BY room_num;
Output:
ROOM_NUM NATIONALIT HOUSE BEVERAGES CIGARE PETS
---------- ---------- ------ ----------- ------ -----
1 Norwegian yellow dunhill water cat
2 Dane blue blends tea horse
3 Englishman red pall mall milk bird
4 German green prince coffee fish
5 Swede white blue master beer dog