Thanks Graz, nice summary!
If you're interested in getting a prettier output from this method, then it's quite easy to cross-join another table into the query to represent a row in the result and select the value in each category according to the house number.
CREATE TABLE #n5 (n int PRIMARY KEY)
INSERT INTO #n5
SELECT 1 UNION ALL
SELECT 2 UNION ALL
SELECT 3 UNION ALL
SELECT 4 UNION ALL
SELECT 5
SELECT row AS "House Number",
CASE row
WHEN Dane THEN 'Dane'
WHEN English THEN 'English'
WHEN German THEN 'German'
WHEN Norwegian THEN 'Norwegian'
WHEN Swede THEN 'Swede'
END AS Nationality,
CASE row
WHEN Blue THEN 'Blue'
WHEN Green THEN 'Green'
WHEN Red THEN 'Red'
WHEN White THEN 'White'
WHEN Yellow THEN 'Yellow'
END AS "House Color",
CASE row
WHEN Birds THEN 'Birds'
WHEN Cats THEN 'Cats'
WHEN Dog THEN 'Dog'
WHEN Horse THEN 'Horse'
WHEN Yak THEN 'Yak'
END AS Pet,
CASE row
WHEN Beer THEN 'Beer'
WHEN Coffee THEN 'Coffee'
WHEN Milk THEN 'Milk'
WHEN Tea THEN 'Tea'
WHEN Water THEN 'Water'
END AS Drink,
CASE row
WHEN Blend THEN 'Blend'
WHEN BlueMaster THEN 'Blue Master'
WHEN Dunhill THEN 'Dunhill'
WHEN PallMall THEN 'Pall Mall'
WHEN Prince THEN 'Prince'
END AS Smoke
FROM (
SELECT row.n row,
a1.n Dane, a2.n English, a3.n German, a4.n Norwegian, a5.n Swede,
b1.n Blue, b2.n Green, b3.n Red, b4.n White, b5.n Yellow,
c1.n Birds, c2.n Cats, c3.n Dog, c4.n Horse, c5.n Yak,
d1.n Beer, d2.n Coffee, d3.n Milk, d4.n Tea, d5.n Water,
e1.n Blend, e2.n BlueMaster, e3.n Dunhill, e4.n PallMall, e5.n Prince
FROM
#n5 row,
#n5 a1, #n5 a2, #n5 a3, #n5 a4, #n5 a5, -- nationalities
#n5 b1, #n5 b2, #n5 b3, #n5 b4, #n5 b5, -- house colors
#n5 c1, #n5 c2, #n5 c3, #n5 c4, #n5 c5, -- pets
#n5 d1, #n5 d2, #n5 d3, #n5 d4, #n5 d5, -- drinks
#n5 e1, #n5 e2, #n5 e3, #n5 e4, #n5 e5 -- cigarettes
WHERE
NOT(a2.n IN (a1.n) OR a3.n IN (a1.n, a2.n)
OR a4.n IN (a1.n, a2.n, a3.n) OR a5.n IN (a1.n, a2.n, a3.n, a4.n)
OR b2.n IN (b1.n) OR b3.n IN (b1.n, b2.n)
OR b4.n IN (b1.n, b2.n, b3.n) OR b5.n IN (b1.n, b2.n, b3.n, b4.n)
OR c2.n IN (c1.n) OR c3.n IN (c1.n, c2.n)
OR c4.n IN (c1.n, c2.n, c3.n) OR c5.n IN (c1.n, c2.n, c3.n, c4.n)
OR d2.n IN (d1.n) OR d3.n IN (d1.n, d2.n)
OR d4.n IN (d1.n, d2.n, d3.n) OR d5.n IN (d1.n, d2.n, d3.n, d4.n)
OR e2.n IN (e1.n) OR e3.n IN (e1.n, e2.n)
OR e4.n IN (e1.n, e2.n, e3.n) OR e5.n IN (e1.n, e2.n, e3.n, e4.n))
) AS perms
WHERE English = Red
AND Swede = Dog
AND Dane = Tea
AND Green = White - 1
--AND Green < White -- alternate interpretation for previous line
AND Coffee = Green
AND PallMall = Birds
AND Yellow = Dunhill
AND Milk = 3
AND Norwegian = 1
AND ABS(Blend - Cats) = 1
AND ABS(Horse - Dunhill) = 1
AND BlueMaster = Beer
AND German = Prince
AND ABS(Norwegian - Blue) = 1
AND ABS(Water - Blend) = 1
ORDER BY row
DROP TABLE #n5
(note application of de Morgan to the uniqueness constraint -- this just makes things a little shorter)
This gets difficult to use if there is more than one possible answer: it produces all the rows but they won't be in a useful order. One solution is to order the rows on all 26 columns. Another is to construct a composite value and order on that: this has the advantage of making it easier to feed the result into a reporting tool for prettification.
SELECT solution,
row AS "House Number",
[...]
FROM (
SELECT row.n row,
CAST(a1.n*1000 + a2.n*100 + a3.n*10 + a4.n AS char(4))+
CAST(b1.n*1000 + b2.n*100 + b3.n*10 + b4.n AS char(4))+
CAST(c1.n*1000 + c2.n*100 + c3.n*10 + c4.n AS char(4))+
CAST(d1.n*1000 + d2.n*100 + d3.n*10 + d4.n AS char(4))+
CAST(e1.n*1000 + e2.n*100 + e3.n*10 + e4.n AS char(4)) AS solution,
[...]
ORDER BY solution, row
This uses a character string, but there is enough room in a numeric(18,0) or bigint. I didn't include a5.n - e5.n in this because they are uniquely constrained by the other vaues.
In fact, we can use this last fact to cut down the number of cross-joined tables generating the solution space. The inner subquery perms becomes:
SELECT row.n row,
a1.n Dane, a2.n English, a3.n German, a4.n Norwegian,
15 - a1.n - a2.n - a3.n - a4.n Swede,
b1.n Blue, b2.n Green, b3.n Red, b4.n White,
15 - b1.n - b2.n - b3.n - b4.n Yellow,
c1.n Birds, c2.n Cats, c3.n Dog, c4.n Horse,
15 - c1.n - c2.n - c3.n - c4.n Yak,
d1.n Beer, d2.n Coffee, d3.n Milk, d4.n Tea,
15 - d1.n - d2.n - d3.n - d4.n Water,
e1.n Blend, e2.n BlueMaster, e3.n Dunhill, e4.n PallMall,
15 - e1.n - e2.n - e3.n - e4.n Prince
FROM
#n5 row,
#n5 a1, #n5 a2, #n5 a3, #n5 a4, -- nationalities
#n5 b1, #n5 b2, #n5 b3, #n5 b4, -- house colors
#n5 c1, #n5 c2, #n5 c3, #n5 c4, -- pets
#n5 d1, #n5 d2, #n5 d3, #n5 d4, -- drinks
#n5 e1, #n5 e2, #n5 e3, #n5 e4 -- cigarettes
WHERE
NOT(a2.n IN (a1.n) OR a3.n IN (a1.n, a2.n) OR a4.n IN (a1.n, a2.n, a3.n)
OR b2.n IN (b1.n) OR b3.n IN (b1.n, b2.n) OR b4.n IN (b1.n, b2.n, b3.n)
OR c2.n IN (c1.n) OR c3.n IN (c1.n, c2.n) OR c4.n IN (c1.n, c2.n, c3.n)
OR d2.n IN (d1.n) OR d3.n IN (d1.n, d2.n) OR d4.n IN (d1.n, d2.n, d3.n)
OR e2.n IN (e1.n) OR e3.n IN (e1.n, e2.n) OR e4.n IN (e1.n, e2.n, e3.n))
(For brevity, I've left out the 'solution' column introduced above)
To be honest, it doesn't make much difference either way, you trade a few keystrokes for an arguable loss of clarity and the need to work out that 1+2+3+4+5=15!
Something that Graz didn't mention is that this method relies heavily on the query optimizer. If the optimizer generated an execution plan for the perms subquery in isolation and fed the all resulting rows into the main query it would be a disaster, since the perms query on its own generates (5!)^5 = 24,883,200,000 rows. Rather, the optimizer works globally on the query and 'promotes' the testing of the puzzle constraints to a point much closer to where the values are generated. The optimizer also works hard at ordering the joins to minimize the number of solutions tested -- one thing you may notice is that it takes far longer to find an execution plan than to execute it!
By comparison, the original query (using a SELECT *, a permanent table for the numbers and sprinkled with lot of AS) run on Access 2000 takes my machine about 45 seconds -- which is still better than I expected!
Inspiration for this approach came from a couple of sources. First was an old column by Joe Celko on creating permutations http://www.dbmsmag.com/9806d06.html. Joe's thoughts were that the naive approach could be speeded up by creating a column of 'weights' like this:
i wgt
-------
1 1
2 2
3 4
4 8
5 16
6 32
7 64
and then testing that the values made a permutation with a single WHERE adding all the weights and checking that all the bits were set -- in this case, a total weight of 127.
Of course, on SQL Server, this turns out to be a terrible idea, much slower than the naive solution. The 'optimized' version has to generate all possible values while the in 'naive' version all the INs get broken up and each pair is tested at the first possible point!
I only discovered what the other source had been after submitting my solution! Some while back, I had a play around with Mozart http://www.mozart-oz.org/, an implementation of the OZ programming language. It's a weird language: part functional, part logic-based, part object-oriented with strong support for concurrency and constraint programming. I'd rather bridled at Rob's comment in the challenge that SQL was the best language for solving this puzzle, and resolved to write it in OZ too. Whereupon I found almost exactly the same thing as a worked example in the Finite Domain Constraint Programming tutorial! http://www.mozart-oz.org/documentation/fdt/node23.html#section.elimination.zebra
For what it's worth, here's the Yak puzzle translated from SQL to OZ by my decidedly inexpert hand -- their 'Zebra' solution is a little better abstracted:
declare
proc {Log Root}
Dane English German Norwegian Swede
Blue Green Red White Yellow
Beer Coffee Milk Tea Water
Birds Cats Dog Horse Yak
Blend BlueMaster Dunhill PallMall Prince
in
Root = sol(
dane:Dane english:English german:German
norgwegian:Norwegian swede:Swede
blue:Blue green:Green red:Red white:White yellow:Yellow
beer:Beer coffee:Coffee milk:Milk tea:Tea water:Water
birds:Birds cats:Cats dog:Dog horse:Horse yak:Yak
blend:Blend bluemaster:BlueMaster dunhill:Dunhill
pallmall:PallMall prince:Prince
)
Root ::: 1#5
{FD.distinct [Dane English German Norwegian Swede]}
{FD.distinct [Blue Green Red White Yellow]}
{FD.distinct [Beer Coffee Milk Tea Water]}
{FD.distinct [Birds Cats Dog Horse Yak]}
{FD.distinct [Blend BlueMaster Dunhill PallMall Prince]}
English =: Red
Swede =: Dog
Dane =: Tea
Green =: White - 1
/*Green <: White*/
Coffee =: Green
PallMall =: Birds
Yellow =: Dunhill
Milk =: 3
Norwegian =: 1
{FD.distance Blend Cats '=:' 1}
{FD.distance Horse Dunhill '=:' 1}
BlueMaster =: Beer
German =: Prince
{FD.distance Norwegian Blue '=:' 1}
{FD.distance Water Blend '=:' 1}
{FD.distribute ff Root}
end
{ExploreAll Log}
The execution of this takes very little time indeed, since Mozart is able to find a unique solution just by applying its constraint 'propagators' with no need for 'distribution' -- if you were doing this puzzle on paper, that's like getting the answer without even having to say to yourself "let's suppose that the Horse is in house number 3" and seeing if it leads to a solution or not.
Edited by - Arnold Fribble on 07/16/2002 05:36:25
Article: Another German Yak ... with a suprise (RC #3)
Posted - 07/16/2002 : 01:12:58
.