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 5SELECT 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 SmokeFROM ( 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 permsWHERE 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) = 1ORDER BY rowDROP 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 12 23 44 85 166 327 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.zebraFor 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:declareproc {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 Princein 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 - 2002-07-16 : 01:12:58
===============================================Creating tomorrow's legacy systems today.One crisis at a time. 
<O> 
.