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