Solving "Who owns the Zebra" programmatically?

In Prolog, we can instantiate the domain just by selecting elements from it :) (making mutually-exclusive choices, for efficiency). Using SWI-Prolog,

select([A|As],S):- select(A,S,S1),select(As,S1). select([],_). left_of(A,B,C):- append(_,[A,B|_],C). next_to(A,B,C):- left_of(A,B,C) ; left_of(B,A,C). zebra(Owns, HS):- % (* house: color,nation,pet,drink,smokes *) HS = [ h(_,norwegian,_,_,_), h(blue,_,_,_,_), h(_,_,_,milk,_), _, _], left_of( h(green,_,_,coffee,_), h(white,_,_,_,_), HS), select([ h(red,brit,_,_,_), h(_,swede,dog,_,_), h(_,dane,_,tea,_), h(_,german,_,_,prince)], HS), select([ h(_,_,birds,_,pallmall), h(yellow,_,_,_,dunhill), h(_,_,_,beer,bluemaster)], HS), next_to( h(_,_,_,_,dunhill), h(_,_,horse,_,_), HS), next_to( h(_,_,_,_,blend), h(_,_,cats, _,_), HS), next_to( h(_,_,_,_,blend), h(_,_,_,water,_), HS), member( h(_,Owns,zebra,_,_), HS). 

Runs quite instantly:

?- time( (zebra(Who,HS), writeln(Who), nl, maplist(writeln,HS), nl, false ; writeln("no more solutions!") )). german h( yellow, norwegian, cats, water, dunhill ) h( blue, dane, horse, tea, blend ) h( red, brit, birds, milk, pallmall ) h( green, german, zebra, coffee, prince ) % (* formatted by hand *) h( white, swede, dog, beer, bluemaster) no more solutions! % (* 385 inferences, 0.000 CPU in 0.025 seconds (0% CPU, Infinite Lips) *) true. 

One poster already mentioned that Prolog is a potential solution. This is true, and it's the solution I would use. In more general terms, this is a perfect problem for an automated inference system. Prolog is a logic programming language (and associated interpreter) that form such a system. It basically allows concluding of facts from statements made using First Order Logic. FOL is basically a more advanced form of propositional logic. If you decide you don't want to use Prolog, you could use a similar system of your own creation using a technique such as modus ponens to perform the draw the conclusions.

You will, of course, need to add some rules about zebras, since it isn't mentioned anywhere... I believe the intent is that you can figure out the other 4 pets and thus deduce the last one is the zebra? You'll want to add rules that state a zebra is one of the pets, and each house can only have one pet. Getting this kind of "common sense" knowledge into an inference system is the major hurdle to using the technique as a true AI. There are some research projects, such as Cyc, which are attempting to give such common knowledge through brute force. They've met with an interesting amount of success.

SWI-Prolog compatible:

% NOTE - This may or may not be more efficent. A bit verbose, though. left_side(L, R, [L, R, _, _, _]). left_side(L, R, [_, L, R, _, _]). left_side(L, R, [_, _, L, R, _]). left_side(L, R, [_, _, _, L, R]). next_to(X, Y, Street) :- left_side(X, Y, Street). next_to(X, Y, Street) :- left_side(Y, X, Street). m(X, Y) :- member(X, Y). get_zebra(Street, Who) :- Street = [[C1, N1, P1, D1, S1], [C2, N2, P2, D2, S2], [C3, N3, P3, D3, S3], [C4, N4, P4, D4, S4], [C5, N5, P5, D5, S5]], m([red, english, _, _, _], Street), m([_, swede, dog, _, _], Street), m([_, dane, _, tea, _], Street), left_side([green, _, _, _, _], [white, _, _, _, _], Street), m([green, _, _, coffee, _], Street), m([_, _, birds, _, pallmall], Street), m([yellow, _, _, _, dunhill], Street), D3 = milk, N1 = norwegian, next_to([_, _, _, _, blend], [_, _, cats, _, _], Street), next_to([_, _, horse, _, _], [_, _, _, _, dunhill], Street), m([_, _, _, beer, bluemaster], Street), m([_, german, _, _, prince], Street), next_to([_, norwegian, _, _, _], [blue, _, _, _, _], Street), next_to([_, _, _, water, _], [_, _, _, _, blend], Street), m([_, Who, zebra, _, _], Street). 

At the interpreter:

?- get_zebra(Street, Who). Street = ... Who = german 

Here's how I'd go about it. First I'd generate all the ordered n-tuples

(housenumber, color, nationality, pet, drink, smoke) 

5^6 of those, 15625, easily manageable. Then I'd filter out the simple boolean conditions. there's ten of them, and each of those you'd expect to filter out 8/25 of the conditions (1/25 of the conditions contain a Swede with a dog, 16/25 contain a non-Swede with a non-dog). Of course they're not independent but after filtering those out there shouldn't be many left.

After that, you've got a nice graph problem. Create a graph with each node representing one of the remaining n-tuples. Add edges to the graph if the two ends contain duplicates in some n-tuple position or violate any 'positional' constraints (there's five of those). From there you're almost home, search the graph for an independent set of five nodes (with none of the nodes connected by edges). If there's not too many, you could possibly just exhaustively generate all the 5-tuples of n-tuples and just filter them again.

This could be a good candidate for code golf. Someone can probably solve it in one line with something like haskell :)

afterthought: The initial filter pass can also eliminate information from the positional constraints. Not much (1/25), but still significant.

Another Python solution, this time using Python's PyKE (Python Knowledge Engine). Granted, it's more verbose than using Python's "constraint" module in the solution by @J.F.Sebastian, but it provides an interesting comparison for anybody looking into a raw knowledge engine for this type of problem.

clues.kfb

categories( POSITION, 1, 2, 3, 4, 5 ) # There are five houses. categories( HOUSE_COLOR, blue, red, green, white, yellow ) # Each house has its own unique color. categories( NATIONALITY, Norwegian, German, Dane, Swede, English ) # All house owners are of different nationalities. categories( PET, birds, dog, cats, horse, zebra ) # They all have different pets. categories( DRINK, tea, coffee, milk, beer, water ) # They all drink different drinks. categories( SMOKE, Blend, Prince, 'Blue Master', Dunhill, 'Pall Mall' ) # They all smoke different cigarettes. related( NATIONALITY, English, HOUSE_COLOR, red ) # The English man lives in the red house. related( NATIONALITY, Swede, PET, dog ) # The Swede has a dog. related( NATIONALITY, Dane, DRINK, tea ) # The Dane drinks tea. left_of( HOUSE_COLOR, green, HOUSE_COLOR, white ) # The green house is on the left side of the white house. related( DRINK, coffee, HOUSE_COLOR, green ) # They drink coffee in the green house. related( SMOKE, 'Pall Mall', PET, birds ) # The man who smokes Pall Mall has birds. related( SMOKE, Dunhill, HOUSE_COLOR, yellow ) # In the yellow house they smoke Dunhill. related( POSITION, 3, DRINK, milk ) # In the middle house they drink milk. related( NATIONALITY, Norwegian, POSITION, 1 ) # The Norwegian lives in the first house. next_to( SMOKE, Blend, PET, cats ) # The man who smokes Blend lives in the house next to the house with cats. next_to( SMOKE, Dunhill, PET, horse ) # In the house next to the house where they have a horse, they smoke Dunhill. related( SMOKE, 'Blue Master', DRINK, beer ) # The man who smokes Blue Master drinks beer. related( NATIONALITY, German, SMOKE, Prince ) # The German smokes Prince. next_to( NATIONALITY, Norwegian, HOUSE_COLOR, blue ) # The Norwegian lives next to the blue house. next_to( DRINK, water, SMOKE, Blend ) # They drink water in the house next to the house where they smoke Blend. 

relations.krb

############# # Categories # Foreach set of categories, assert each type categories foreach clues.categories($category, $thing1, $thing2, $thing3, $thing4, $thing5) assert clues.is_category($category, $thing1) clues.is_category($category, $thing2) clues.is_category($category, $thing3) clues.is_category($category, $thing4) clues.is_category($category, $thing5) ######################### # Inverse Relationships # Foreach A=1, assert 1=A inverse_relationship_positive foreach clues.related($category1, $thing1, $category2, $thing2) assert clues.related($category2, $thing2, $category1, $thing1) # Foreach A!1, assert 1!A inverse_relationship_negative foreach clues.not_related($category1, $thing1, $category2, $thing2) assert clues.not_related($category2, $thing2, $category1, $thing1) # Foreach "A beside B", assert "B beside A" inverse_relationship_beside foreach clues.next_to($category1, $thing1, $category2, $thing2) assert clues.next_to($category2, $thing2, $category1, $thing1) ########################### # Transitive Relationships # Foreach A=1 and 1=a, assert A=a transitive_positive foreach clues.related($category1, $thing1, $category2, $thing2) clues.related($category2, $thing2, $category3, $thing3) check unique($thing1, $thing2, $thing3) \ and unique($category1, $category2, $category3) assert clues.related($category1, $thing1, $category3, $thing3) # Foreach A=1 and 1!a, assert A!a transitive_negative foreach clues.related($category1, $thing1, $category2, $thing2) clues.not_related($category2, $thing2, $category3, $thing3) check unique($thing1, $thing2, $thing3) \ and unique($category1, $category2, $category3) assert clues.not_related($category1, $thing1, $category3, $thing3) ########################## # Exclusive Relationships # Foreach A=1, assert A!2 and A!3 and A!4 and A!5 if_one_related_then_others_unrelated foreach clues.related($category, $thing, $category_other, $thing_other) check unique($category, $category_other) clues.is_category($category_other, $thing_not_other) check unique($thing, $thing_other, $thing_not_other) assert clues.not_related($category, $thing, $category_other, $thing_not_other) # Foreach A!1 and A!2 and A!3 and A!4, assert A=5 if_four_unrelated_then_other_is_related foreach clues.not_related($category, $thing, $category_other, $thingA) clues.not_related($category, $thing, $category_other, $thingB) check unique($thingA, $thingB) clues.not_related($category, $thing, $category_other, $thingC) check unique($thingA, $thingB, $thingC) clues.not_related($category, $thing, $category_other, $thingD) check unique($thingA, $thingB, $thingC, $thingD) # Find the fifth variation of category_other. clues.is_category($category_other, $thingE) check unique($thingA, $thingB, $thingC, $thingD, $thingE) assert clues.related($category, $thing, $category_other, $thingE) ################### # Neighbors: Basic # Foreach "A left of 1", assert "A beside 1" expanded_relationship_beside_left foreach clues.left_of($category1, $thing1, $category2, $thing2) assert clues.next_to($category1, $thing1, $category2, $thing2) # Foreach "A beside 1", assert A!1 unrelated_to_beside foreach clues.next_to($category1, $thing1, $category2, $thing2) check unique($category1, $category2) assert clues.not_related($category1, $thing1, $category2, $thing2) ################################### # Neighbors: Spatial Relationships # Foreach "A beside B" and "A=(at-edge)", assert "B=(near-edge)" check_next_to_either_edge foreach clues.related(POSITION, $position_known, $category, $thing) check is_edge($position_known) clues.next_to($category, $thing, $category_other, $thing_other) clues.is_category(POSITION, $position_other) check is_beside($position_known, $position_other) assert clues.related(POSITION, $position_other, $category_other, $thing_other) # Foreach "A beside B" and "A!(near-edge)" and "B!(near-edge)", assert "A!(at-edge)" check_too_close_to_edge foreach clues.next_to($category, $thing, $category_other, $thing_other) clues.is_category(POSITION, $position_edge) clues.is_category(POSITION, $position_near_edge) check is_edge($position_edge) and is_beside($position_edge, $position_near_edge) clues.not_related(POSITION, $position_near_edge, $category, $thing) clues.not_related(POSITION, $position_near_edge, $category_other, $thing_other) assert clues.not_related(POSITION, $position_edge, $category, $thing) # Foreach "A beside B" and "A!(one-side)", assert "A=(other-side)" check_next_to_with_other_side_impossible foreach clues.next_to($category, $thing, $category_other, $thing_other) clues.related(POSITION, $position_known, $category_other, $thing_other) check not is_edge($position_known) clues.not_related($category, $thing, POSITION, $position_one_side) check is_beside($position_known, $position_one_side) clues.is_category(POSITION, $position_other_side) check is_beside($position_known, $position_other_side) \ and unique($position_known, $position_one_side, $position_other_side) assert clues.related($category, $thing, POSITION, $position_other_side) # Foreach "A left of B"... # ... and "C=(position1)" and "D=(position2)" and "E=(position3)" # ~> assert "A=(other-position)" and "B=(other-position)+1" left_of_and_only_two_slots_remaining foreach clues.left_of($category_left, $thing_left, $category_right, $thing_right) clues.related($category_left, $thing_left_other1, POSITION, $position1) clues.related($category_left, $thing_left_other2, POSITION, $position2) clues.related($category_left, $thing_left_other3, POSITION, $position3) check unique($thing_left, $thing_left_other1, $thing_left_other2, $thing_left_other3) clues.related($category_right, $thing_right_other1, POSITION, $position1) clues.related($category_right, $thing_right_other2, POSITION, $position2) clues.related($category_right, $thing_right_other3, POSITION, $position3) check unique($thing_right, $thing_right_other1, $thing_right_other2, $thing_right_other3) clues.is_category(POSITION, $position4) clues.is_category(POSITION, $position5) check is_left_right($position4, $position5) \ and unique($position1, $position2, $position3, $position4, $position5) assert clues.related(POSITION, $position4, $category_left, $thing_left) clues.related(POSITION, $position5, $category_right, $thing_right) ######################### fc_extras def unique(*args): return len(args) == len(set(args)) def is_edge(pos): return (pos == 1) or (pos == 5) def is_beside(pos1, pos2): diff = (pos1 - pos2) return (diff == 1) or (diff == -1) def is_left_right(pos_left, pos_right): return (pos_right - pos_left == 1) 

driver.py (actually larger, but this is the essence)

from pyke import knowledge_engine engine = knowledge_engine.engine(__file__) engine.activate('relations') try: natl = engine.prove_1_goal('clues.related(PET, zebra, NATIONALITY, $nationality)')[0].get('nationality') except Exception, e: natl = "Unknown" print "== Who owns the zebra? %s ==" % natl 

Sample output:

$ python driver.py == Who owns the zebra? German == # Color Nationality Pet Drink Smoke ======================================================= 1 yellow Norwegian cats water Dunhill 2 blue Dane horse tea Blend 3 red English birds milk Pall Mall 4 green German zebra coffee Prince 5 white Swede dog beer Blue Master Calculated in 1.19 seconds. 

Source: https://github.com/DreadPirateShawn/pyke-who-owns-zebra

Here is an excerpt from the full solution using NSolver, posted at Einstein’s Riddle in C#:

// The green house's owner drinks coffee Post(greenHouse.Eq(coffee)); // The person who smokes Pall Mall rears birds Post(pallMall.Eq(birds)); // The owner of the yellow house smokes Dunhill Post(yellowHouse.Eq(dunhill)); 

ES6 (Javascript) solution

With lots of ES6 generators and a little bit of lodash. You will need Babel to run this.

var _ = require('lodash'); function canBe(house, criteria) { for (const key of Object.keys(criteria)) if (house[key] && house[key] !== criteria[key]) return false; return true; } function* thereShouldBe(criteria, street) { for (const i of _.range(street.length)) yield* thereShouldBeAtIndex(criteria, i, street); } function* thereShouldBeAtIndex(criteria, index, street) { if (canBe(street[index], criteria)) { const newStreet = _.cloneDeep(street); newStreet[index] = _.assign({}, street[index], criteria); yield newStreet; } } function* leftOf(critA, critB, street) { for (const i of _.range(street.length - 1)) { if (canBe(street[i], critA) && canBe(street[i+1], critB)) { const newStreet = _.cloneDeep(street); newStreet[i ] = _.assign({}, street[i ], critA); newStreet[i+1] = _.assign({}, street[i+1], critB); yield newStreet; } } } function* nextTo(critA, critB, street) { yield* leftOf(critA, critB, street); yield* leftOf(critB, critA, street); } const street = [{}, {}, {}, {}, {}]; // five houses // Btw: it turns out we don't need uniqueness constraint. const constraints = [ s => thereShouldBe({nation: 'English', color: 'red'}, s), s => thereShouldBe({nation: 'Swede', animal: 'dog'}, s), s => thereShouldBe({nation: 'Dane', drink: 'tea'}, s), s => leftOf({color: 'green'}, {color: 'white'}, s), s => thereShouldBe({drink: 'coffee', color: 'green'}, s), s => thereShouldBe({cigarettes: 'PallMall', animal: 'birds'}, s), s => thereShouldBe({color: 'yellow', cigarettes: 'Dunhill'}, s), s => thereShouldBeAtIndex({drink: 'milk'}, 2, s), s => thereShouldBeAtIndex({nation: 'Norwegian'}, 0, s), s => nextTo({cigarettes: 'Blend'}, {animal: 'cats'}, s), s => nextTo({animal: 'horse'}, {cigarettes: 'Dunhill'}, s), s => thereShouldBe({cigarettes: 'BlueMaster', drink: 'beer'}, s), s => thereShouldBe({nation: 'German', cigarettes: 'Prince'}, s), s => nextTo({nation: 'Norwegian'}, {color: 'blue'}, s), s => nextTo({drink: 'water'}, {cigarettes: 'Blend'}, s), s => thereShouldBe({animal: 'zebra'}, s), // should be somewhere ]; function* findSolution(remainingConstraints, street) { if (remainingConstraints.length === 0) yield street; else for (const newStreet of _.head(remainingConstraints)(street)) yield* findSolution(_.tail(remainingConstraints), newStreet); } for (const streetSolution of findSolution(constraints, street)) { console.log(streetSolution); } 

Result:

[ { color: 'yellow', cigarettes: 'Dunhill', nation: 'Norwegian', animal: 'cats', drink: 'water' }, { nation: 'Dane', drink: 'tea', cigarettes: 'Blend', animal: 'horse', color: 'blue' }, { nation: 'English', color: 'red', cigarettes: 'PallMall', animal: 'birds', drink: 'milk' }, { color: 'green', drink: 'coffee', nation: 'German', cigarettes: 'Prince', animal: 'zebra' }, { nation: 'Swede', animal: 'dog', color: 'white', cigarettes: 'BlueMaster', drink: 'beer' } ] 

Run time is around 2.5s for me, but this can be improved a lot by changing the order of rules. I decided to keep the original order for clarity.

Thanks, this was a cool challenge!

Here is a straightforward solution in CLP(FD) (see also clpfd):

:- use_module(library(clpfd)). solve(ZebraOwner) :- maplist( init_dom(1..5), [[British, Swedish, Danish, Norwegian, German], % Nationalities [Red, Green, Blue, White, Yellow], % Houses [Tea, Coffee, Milk, Beer, Water], % Beverages [PallMall, Blend, Prince, Dunhill, BlueMaster], % Cigarettes [Dog, Birds, Cats, Horse, Zebra]]), % Pets British #= Red, % Hint 1 Swedish #= Dog, % Hint 2 Danish #= Tea, % Hint 3 Green #= White - 1 , % Hint 4 Green #= Coffee, % Hint 5 PallMall #= Birds, % Hint 6 Yellow #= Dunhill, % Hint 7 Milk #= 3, % Hint 8 Norwegian #= 1, % Hint 9 neighbor(Blend, Cats), % Hint 10 neighbor(Horse, Dunhill), % Hint 11 BlueMaster #= Beer, % Hint 12 German #= Prince, % Hint 13 neighbor(Norwegian, Blue), % Hint 14 neighbor(Blend, Water), % Hint 15 memberchk(Zebra-ZebraOwner, [British-british, Swedish-swedish, Danish-danish, Norwegian-norwegian, German-german]). init_dom(R, L) :- all_distinct(L), L ins R. neighbor(X, Y) :- (X #= (Y - 1)) #\/ (X #= (Y + 1)). 

Running it, produces:

3 ?- time(solve(Z)).
% 111,798 inferences, 0.016 CPU in 0.020 seconds (78% CPU, 7166493 Lips)
Z = german.

In PAIP (Chapter 11), Norvig solves the zebra puzzle using a Prolog embedded in Lisp.

This is really a constraint solving problem. You can do it with a generalized kind of constraint propagation in logic-programming like languages. We have a demo specifically for the Zebra problem in the ALE (attribute logic engine) system:

http://www.cs.toronto.edu/~gpenn/ale.html

Here's the link to the coding of a simplified Zebra puzzle:

http://www.cs.toronto.edu/~gpenn/ale/files/grammars/baby.pl

To do this efficiently is another matter.

The easiest way to solve such problems programmatically is to use nested loops over all permutations and check to see if the result satisfies the predicates in the question. Many of the predicates can be hoisted from the inner loop to outer loops in order to dramatically reduce the computational complexity until the answer can be computed in a reasonable time.

Here is a simple F# solution derived from an article in the F# Journal:

let rec distribute y xs = match xs with | [] -> [[y]] | x::xs -> (y::x::xs)::[for xs in distribute y xs -> x::xs] let rec permute xs = match xs with | [] | [_] as xs -> [xs] | x::xs -> List.collect (distribute x) (permute xs) let find xs x = List.findIndex ((=) x) xs + 1 let eq xs x ys y = find xs x = find ys y let nextTo xs x ys y = abs(find xs x - find ys y) = 1 let nations = ["British"; "Swedish"; "Danish"; "Norwegian"; "German"] let houses = ["Red"; "Green"; "Blue"; "White"; "Yellow"] let drinks = ["Milk"; "Coffee"; "Water"; "Beer"; "Tea"] let smokes = ["Blend"; "Prince"; "Blue Master"; "Dunhill"; "Pall Mall"] let pets = ["Dog"; "Cat"; "Zebra"; "Horse"; "Bird"] [ for nations in permute nations do if find nations "Norwegian" = 1 then for houses in permute houses do if eq nations "British" houses "Red" && find houses "Green" = find houses "White"-1 && nextTo nations "Norwegian" houses "Blue" then for drinks in permute drinks do if eq nations "Danish" drinks "Tea" && eq houses "Green" drinks "Coffee" && 3 = find drinks "Milk" then for smokes in permute smokes do if eq houses "Yellow" smokes "Dunhill" && eq smokes "Blue Master" drinks "Beer" && eq nations "German" smokes "Prince" && nextTo smokes "Blend" drinks "Water" then for pets in permute pets do if eq nations "Swedish" pets "Dog" && eq smokes "Pall Mall" pets "Bird" && nextTo pets "Cat" smokes "Blend" && nextTo pets "Horse" smokes "Dunhill" then yield nations, houses, drinks, smokes, pets ] 

The output obtained in 9ms is:

val it : (string list * string list * string list * string list * string list) list = [(["Norwegian"; "Danish"; "British"; "German"; "Swedish"], ["Yellow"; "Blue"; "Red"; "Green"; "White"], ["Water"; "Tea"; "Milk"; "Coffee"; "Beer"], ["Dunhill"; "Blend"; "Pall Mall"; "Prince"; "Blue Master"], ["Cat"; "Horse"; "Bird"; "Zebra"; "Dog"])] 

This is a MiniZinc solution to the zebra puzzle as defined in Wikipedia:

include "globals.mzn"; % Zebra puzzle int: nc = 5; % Colors int: red = 1; int: green = 2; int: ivory = 3; int: yellow = 4; int: blue = 5; array[1..nc] of var 1..nc:color; constraint alldifferent([color[i] | i in 1..nc]); % Nationalities int: eng = 1; int: spa = 2; int: ukr = 3; int: nor = 4; int: jap = 5; array[1..nc] of var 1..nc:nationality; constraint alldifferent([nationality[i] | i in 1..nc]); % Pets int: dog = 1; int: snail = 2; int: fox = 3; int: horse = 4; int: zebra = 5; array[1..nc] of var 1..nc:pet; constraint alldifferent([pet[i] | i in 1..nc]); % Drinks int: coffee = 1; int: tea = 2; int: milk = 3; int: orange = 4; int: water = 5; array[1..nc] of var 1..nc:drink; constraint alldifferent([drink[i] | i in 1..nc]); % Smokes int: oldgold = 1; int: kools = 2; int: chesterfields = 3; int: luckystrike = 4; int: parliaments = 5; array[1..nc] of var 1..nc:smoke; constraint alldifferent([smoke[i] | i in 1..nc]); % The Englishman lives in the red house. constraint forall ([nationality[i] == eng <-> color[i] == red | i in 1..nc]); % The Spaniard owns the dog. constraint forall ([nationality[i] == spa <-> pet[i] == dog | i in 1..nc]); % Coffee is drunk in the green house. constraint forall ([color[i] == green <-> drink[i] == coffee | i in 1..nc]); % The Ukrainian drinks tea. constraint forall ([nationality[i] == ukr <-> drink[i] == tea | i in 1..nc]); % The green house is immediately to the right of the ivory house. constraint forall ([color[i] == ivory -> if i<nc then color[i+1] == green else false endif | i in 1..nc]); % The Old Gold smoker owns snails. constraint forall ([smoke[i] == oldgold <-> pet[i] == snail | i in 1..nc]); % Kools are smoked in the yellow house. constraint forall ([smoke[i] == kools <-> color[i] == yellow | i in 1..nc]); % Milk is drunk in the middle house. constraint drink[3] == milk; % The Norwegian lives in the first house. constraint nationality[1] == nor; % The man who smokes Chesterfields lives in the house next to the man with the fox. constraint forall ([smoke[i] == chesterfields -> (if i>1 then pet[i-1] == fox else false endif \/ if i<nc then pet[i+1] == fox else false endif) | i in 1..nc]); % Kools are smoked in the house next to the house where the horse is kept. constraint forall ([smoke[i] == kools -> (if i>1 then pet[i-1] == horse else false endif \/ if i<nc then pet[i+1] == horse else false endif)| i in 1..nc]); %The Lucky Strike smoker drinks orange juice. constraint forall ([smoke[i] == luckystrike <-> drink[i] == orange | i in 1..nc]); % The Japanese smokes Parliaments. constraint forall ([nationality[i] == jap <-> smoke[i] == parliaments | i in 1..nc]); % The Norwegian lives next to the blue house. constraint forall ([color[i] == blue -> (if i > 1 then nationality[i-1] == nor else false endif \/ if i<nc then nationality[i+1] == nor else false endif) | i in 1..nc]); solve satisfy; 

Solution:

Compiling zebra.mzn Running zebra.mzn color = array1d(1..5 ,[4, 5, 1, 3, 2]); nationality = array1d(1..5 ,[4, 3, 1, 2, 5]); pet = array1d(1..5 ,[3, 4, 2, 1, 5]); drink = array1d(1..5 ,[5, 2, 3, 4, 1]); smoke = array1d(1..5 ,[2, 3, 1, 4, 5]); ---------- Finished in 47msec 

The Microsoft Solver Foundation example from: https://msdn.microsoft.com/en-us/library/ff525831%28v=vs.93%29.aspx?f=255&MSPPError=-2147217396

delegate CspTerm NamedTerm(string name); public static void Zebra() { ConstraintSystem S = ConstraintSystem.CreateSolver(); var termList = new List<KeyValuePair<CspTerm, string>>(); NamedTerm House = delegate(string name) { CspTerm x = S.CreateVariable(S.CreateIntegerInterval(1, 5), name); termList.Add(new KeyValuePair<CspTerm, string>(x, name)); return x; }; CspTerm English = House("English"), Spanish = House("Spanish"), Japanese = House("Japanese"), Italian = House("Italian"), Norwegian = House("Norwegian"); CspTerm red = House("red"), green = House("green"), white = House("white"), blue = House("blue"), yellow = House("yellow"); CspTerm dog = House("dog"), snails = House("snails"), fox = House("fox"), horse = House("horse"), zebra = House("zebra"); CspTerm painter = House("painter"), sculptor = House("sculptor"), diplomat = House("diplomat"), violinist = House("violinist"), doctor = House("doctor"); CspTerm tea = House("tea"), coffee = House("coffee"), milk = House("milk"), juice = House("juice"), water = House("water"); S.AddConstraints( S.Unequal(English, Spanish, Japanese, Italian, Norwegian), S.Unequal(red, green, white, blue, yellow), S.Unequal(dog, snails, fox, horse, zebra), S.Unequal(painter, sculptor, diplomat, violinist, doctor), S.Unequal(tea, coffee, milk, juice, water), S.Equal(English, red), S.Equal(Spanish, dog), S.Equal(Japanese, painter), S.Equal(Italian, tea), S.Equal(1, Norwegian), S.Equal(green, coffee), S.Equal(1, green - white), S.Equal(sculptor, snails), S.Equal(diplomat, yellow), S.Equal(3, milk), S.Equal(1, S.Abs(Norwegian - blue)), S.Equal(violinist, juice), S.Equal(1, S.Abs(fox - doctor)), S.Equal(1, S.Abs(horse - diplomat)) ); bool unsolved = true; ConstraintSolverSolution soln = S.Solve(); while (soln.HasFoundSolution) { unsolved = false; System.Console.WriteLine("solved."); StringBuilder[] houses = new StringBuilder[5]; for (int i = 0; i < 5; i++) houses[i] = new StringBuilder(i.ToString()); foreach (KeyValuePair<CspTerm, string> kvp in termList) { string item = kvp.Value; object house; if (!soln.TryGetValue(kvp.Key, out house)) throw new InvalidProgramException( "can't find a Term in the solution: " + item); houses[(int)house - 1].Append(", "); houses[(int)house - 1].Append(item); } foreach (StringBuilder house in houses) { System.Console.WriteLine(house); } soln.GetNext(); } if (unsolved) System.Console.WriteLine("No solution found."); else System.Console.WriteLine( "Expected: the Norwegian drinking water and the Japanese with the zebra."); } 

One example of a programmatic solution (originally written for a similar question), can be found here: https://puzzle-solvers.readthedocs.io/en/latest/

I implemented a matrix of relationships between the classes, which gets updated as you enter the constraints. The API centers on a Solver class, which you initialize with the categories and labels. You then call methods like adjecent_to and match on to set up the relationships.

The docs have a fairly thorough explanation of the underlying logic. The exact puzzle you describe is one of the demos. To answer your literal question, here is what the demo looks like:

positions = [1, 2, 3, 4, 5] nationalities = [ 'Englishman', 'Spaniard', 'Ukrainian', 'Norwegian', 'Japanese' ] colors = ['red', 'green', 'ivory', 'yellow', 'blue'] pets = ['dog', 'snails', 'fox', 'horse', 'ZEBRA'] drinks = ['coffee', 'tea', 'milk', 'orange juice', 'WATER'] cigarettes = [ 'Old Gold', 'Kools', 'Chesterfields', 'Lucky Strikes', 'Parliaments' ] problem = { 'position': positions, 'nationality': nationalities, 'color': colors, 'pet': pets, 'drink': drinks, 'cigarette': cigarettes, } solver = Solver(problem) if __name__ == '__main__': solver.match('Englishman', 'red') solver.match('Spaniard', 'dog') solver.match('coffee', 'green') solver.match('Ukrainian', 'tea') solver.greater_than('green', 'ivory', 'position', 1) solver.match('Old Gold', 'snails') solver.match('Kools', 'yellow') solver.match('milk', 3) solver.match('Norwegian', 1) solver.adjacent_to('Chesterfields', 'fox', 'position') solver.adjacent_to('Kools', 'horse', 'position') solver.match('Lucky Strikes', 'orange juice') solver.match('Japanese', 'Parliaments') solver.adjacent_to('Norwegian', 'blue', 'position') solver.draw(show=False, title=f'After Rules: {solver.edges} Edges') print(f'Solved? {solver.solved}') print(f'{solver.category_for("ZEBRA", "nationality")} owns the ZEBRA') print(f'{solver.category_for("WATER", "nationality")} drinks WATER') 

The nice thing about this code is that it's something one might write overnight, and not a really well thought-out production package, yet it still does the job.