-- File: monkey_business.sql -- Version: 1.1 -- Last Changed: 2018-02-10 -- by: Damir; https://www.damirsystems.com -- Project: Monkey Business -- Description: Fun challenge from Decision Management Community -- https://dmcommunity.org/challenge/challenge-nov-2015/ -- DB: PostgreSQL, MS SQL Server WITH monkey AS ( SELECT mname FROM ( VALUES ('Sam'), ('Anna'), ('Harriet'), ('Mike') ) AS m(mname) ), food AS ( SELECT fruit FROM ( VALUES ('banana'), ('pear'), ('apple'), ('orange') ) AS f(fruit) ), place AS ( SELECT place FROM ( VALUES ('grass'), ('rock'), ('tree'), ('stream') ) AS p(place) ), mfp AS ( -- Create all combinations of {monkey, fruit, place} -- and remove forbidden cases. SELECT mname, fruit, place FROM monkey CROSS JOIN food CROSS JOIN place WHERE (1=1) -- Sam does not like bananas AND NOT (mname = 'Sam' AND fruit = 'banana') -- Mike does not like oranges AND NOT (mname = 'Mike' AND fruit = 'orange') -- The monkey who sat on the rock ate the apple AND NOT (place = 'rock' AND fruit != 'apple') AND NOT (place != 'rock' AND fruit = 'apple') -- The monkey who ate the pear didn’t sit on the tree branch AND NOT (fruit = 'pear' AND place = 'tree') -- Harriet didn’t sit on the tree branch. AND NOT (mname = 'Harriet' AND place = 'tree') -- Anna sat by the stream AND NOT (mname = 'Anna' AND place != 'stream') AND NOT (mname != 'Anna' AND place = 'stream') -- Anna didn’t eat the pear. AND NOT (mname = 'Anna' AND fruit = 'pear') -- Sam likes sitting on the grass. AND NOT (mname = 'Sam' AND place != 'grass') AND NOT (mname != 'Sam' AND place = 'grass') ), solution AS ( -- Each monkey is resting at exactly one place. -- Each place has exactly one monkey resting at it. -- Each monkey is eating exactly one piece of fruit. -- Each piece of fruit is being eaten by exactly one monkey. SELECT a.mname AS mname_1 , a.place AS place_1 , a.fruit AS fruit_1 , b.mname AS mname_2 , b.place AS place_2 , b.fruit AS fruit_2 , c.mname AS mname_3 , c.place AS place_3 , c.fruit AS fruit_3 , d.mname AS mname_4 , d.place AS place_4 , d.fruit AS fruit_4 -- there may be more than one solution, so number them , row_number() over(ORDER BY a.mname ASC) AS sol_no FROM mfp AS a JOIN mfp AS b ON b.mname > a.mname AND b.fruit != a.fruit AND b.place != a.place JOIN mfp AS c ON c.mname > b.mname AND c.fruit NOT IN (a.fruit, b.fruit) AND c.place NOT IN (a.place, b.place) JOIN mfp AS d ON d.mname > c.mname AND d.fruit NOT IN (a.fruit, b.fruit, c.fruit) AND d.place NOT IN (a.place, b.place, c.place) ) -- Present final result as {sol_no, monkey, place, fruit} SELECT sol_no, mname_1 AS monkey, place_1 AS place, fruit_1 AS fruit FROM solution UNION SELECT sol_no, mname_2 AS monkey, place_2 AS place, fruit_2 AS fruit FROM solution UNION SELECT sol_no, mname_3 AS monkey, place_3 AS place, fruit_3 AS fruit FROM solution UNION SELECT sol_no, mname_4 AS monkey, place_4 AS place, fruit_4 AS fruit FROM solution ORDER BY sol_no, monkey ;