--         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
;