Zebra puzzle: Difference between revisions
Added Uiua solution
(Added Uiua solution) |
|||
(68 intermediate revisions by 27 users not shown) | |||
Line 1:
[[File:zebra.png
{{task|Puzzles}}
[[Category:
[[Category:Puzzles]]
The [[wp:Zebra puzzle|Zebra puzzle]], a.k.a. Einstein's Riddle,
is a logic puzzle which is to be solved programmatically.
It has several variants, one of them this:
:# There are five houses.
:# The English man lives in the red house.
:# The Swede has a dog.
:# The Dane drinks tea.
:# The green house is immediately to the left of the white house.
:# They drink coffee in the green house.
:# The man who smokes Pall Mall has a bird.
:# In the yellow house they smoke Dunhill.
:# In the middle house they drink milk.
:# The Norwegian lives in the first house.
:# The Blend-smoker lives in the house next to the house with a cat.
:# In a house next to the house with a horse, they smoke Dunhill.
:# The man who smokes Blue Master drinks beer.
:# The German smokes Prince.
:# The Norwegian lives next to the blue house.
:# They drink water in a house next to the house where they smoke Blend.
<br>The question is, who owns the zebra? For clarity, each of the five houses is painted a different color, and their inhabitants are of different nationalities, own different pets, drink different beverages and smoke different brands of cigarettes.
Additionally, list the solution for all the houses.
<br>Optionally, show the solution is unique.
Line 38 ⟶ 39:
=={{header|Ada}}==
Not the prettiest Ada, but it's simple and very fast. Similar to my Dinesman's code; uses enums to keep things readable.
<
procedure Zebra is
type Content is (Beer, Coffee, Milk, Tea, Water,
Line 143 ⟶ 144:
end loop; end loop;
Solve (myAlley, 0, 5); -- start at test 0 with 5 options
end Zebra;</
{{out}}
<pre>ONE: DRINK=WATER PERSON=NORWEGIAN COLOR=YELLOW SMOKE=DUNHILL PET=CAT
Line 153 ⟶ 154:
=={{header|ALGOL 68}}==
Attempts to find solutions using the rules.
<
# attempt to solve Einstein's Riddle - the Zebra puzzle #
INT unknown = 0, same = -1;
Line 293 ⟶ 294:
print( ( "solutions: ", whole( solutions, 0 ), newline ) )
END
</syntaxhighlight>
{{out}}
<pre>
Line 304 ⟶ 305:
solutions: 1
</pre>
=={{header|AppleScript}}==
<syntaxhighlight lang="applescript">on zebraPuzzle()
-- From statement 10, the Norwegian lives in the first house,
-- so from statement 15, the blue house must be the second one.
-- From these and statements 5, 6, and 9, the green and white houses can only be the 4th & 5th,
-- and the Englishman's red house (statement 2) must be the middle one, where (9) they drink
-- milk. This only leaves the first house to claim the yellow colour and the Dunhill smokers
-- (statement 8), which means the second house must have the the horse (statement 12).
-- Initialise the house data accordingly.
set mv to missing value
set streetTemplate to {¬
{resident:"Norwegian", colour:"yellow", pet:mv, drink:mv, smoke:"Dunhill"}, ¬
{resident:mv, colour:"blue", pet:"horse", drink:mv, smoke:mv}, ¬
{resident:"Englishman", colour:"red", pet:mv, drink:"milk", smoke:mv}, ¬
{resident:mv, colour:"green", pet:mv, drink:"coffee", smoke:mv}, ¬
{resident:mv, colour:"white", pet:mv, drink:mv, smoke:mv} ¬
}
-- Test all permutations of the remaining values.
set solutions to {}
set drinkPermutations to {{"beer", "water"}, {"water", "beer"}}
set residentPermutations to {{"Swede", "Dane", "German"}, {"Swede", "German", "Dane"}, ¬
{"Dane", "German", "Swede"}, {"Dane", "Swede", "German"}, ¬
{"German", "Swede", "Dane"}, {"German", "Dane", "Swede"}}
set petPermutations to {{"birds", "cats", "ZEBRA"}, {"birds", "ZEBRA", "cats"}, ¬
{"cats", "ZEBRA", "birds"}, {"cats", "birds", "ZEBRA"}, ¬
{"ZEBRA", "birds", "cats"}, {"ZEBRA", "cats", "birds"}}
set smokePermutations to {{"Pall Mall", "Blend", "Blue Master"}, {"Pall Mall", "Blue Master", "Blend"}, ¬
{"Blend", "Blue Master", "Pall Mall"}, {"Blend", "Pall Mall", "Blue Master"}, ¬
{"Blue Master", "Pall Mall", "Blend"}, {"Blue Master", "Blend", "Pall Mall"}}
repeat with residentPerm in residentPermutations
-- Properties associated with resident.
copy streetTemplate to sTemplate2
set {r, OK} to {0, true}
repeat with h in {2, 4, 5} -- House numbers with unknown residents.
set thisHouse to sTemplate2's item h
set r to r + 1
set thisResident to residentPerm's item r
if (thisResident is "Swede") then
if (thisHouse's pet is not mv) then
set OK to false
exit repeat
end if
set thisHouse's pet to "dog"
else if (thisResident is "Dane") then
if (thisHouse's drink is not mv) then
set OK to false
exit repeat
end if
set thisHouse's drink to "tea"
else
set thisHouse's smoke to "Prince"
end if
set thisHouse's resident to thisResident
end repeat
-- Properties associated with cigarette brand.
if (OK) then
repeat with smokePerm in smokePermutations
-- Fit in this permutation of smokes.
copy sTemplate2 to sTemplate3
set s to 0
repeat with thisHouse in sTemplate3
if (thisHouse's smoke is mv) then
set s to s + 1
set thisHouse's smoke to smokePerm's item s
end if
end repeat
repeat with drinkPerm in drinkPermutations
-- Try to fit this permutation of drinks.
copy sTemplate3 to sTemplate4
set {d, OK} to {0, true}
repeat with h from 1 to 5
set thisHouse to sTemplate4's item h
if (thisHouse's drink is mv) then
set d to d + 1
set thisDrink to drinkPerm's item d
if (((thisDrink is "beer") and (thisHouse's smoke is not "Blue Master")) or ¬
((thisDrink is "water") and not ¬
(((h > 1) and (sTemplate4's item (h - 1)'s smoke is "Blend")) or ¬
((h < 5) and (sTemplate4's item (h + 1)'s smoke is "Blend"))))) then
set OK to false
exit repeat
end if
set thisHouse's drink to thisDrink
end if
end repeat
if (OK) then
repeat with petPerm in petPermutations
-- Try to fit this permutation of pets.
copy sTemplate4 to sTemplate5
set {p, OK} to {0, true}
repeat with h from 1 to 5
set thisHouse to sTemplate5's item h
if (thisHouse's pet is mv) then
set p to p + 1
set thisPet to petPerm's item p
if ((thisPet is "birds") and (thisHouse's smoke is not "Pall Mall")) or ¬
((thisPet is "cats") and not ¬
(((h > 1) and (sTemplate5's item (h - 1)'s smoke is "Blend")) or ¬
((h < 5) and (sTemplate5's item (h + 1)'s smoke is "Blend")))) then
set OK to false
exit repeat
end if
set thisHouse's pet to thisPet
end if
end repeat
if (OK) then set end of solutions to sTemplate5
end repeat
end if
end repeat
end repeat
end if
end repeat
set solutionCount to (count solutions)
set owners to {}
repeat with thisSolution in solutions
repeat with thisHouse in thisSolution
if (thisHouse's pet is "zebra") then
set owners's end to thisHouse's resident
exit repeat
end if
end repeat
end repeat
return {zebraOwners:owners, numberOfSolutions:solutionCount, solutions:solutions}
end zebraPuzzle
zebraPuzzle()</syntaxhighlight>
{{output}}
<syntaxhighlight lang="applescript">{zebraOwners:{"German"}, numberOfSolutions:1, solutions:{{{resident:"Norwegian", colour:"yellow", pet:"cats", drink:"water", smoke:"Dunhill"}, {resident:"Dane", colour:"blue", pet:"horse", drink:"tea", smoke:"Blend"}, {resident:"Englishman", colour:"red", pet:"birds", drink:"milk", smoke:"Pall Mall"}, {resident:"German", colour:"green", pet:"ZEBRA", drink:"coffee", smoke:"Prince"}, {resident:"Swede", colour:"white", pet:"dog", drink:"beer", smoke:"Blue Master"}}}}</syntaxhighlight>
=={{header|AutoHotkey}}==
Line 310 ⟶ 443:
=={{header|BBC BASIC}}==
{{works with|BBC BASIC for Windows}}
<
DIM Drink$(4), Nation$(4), Colr$(4), Smoke$(4), Animal$(4)
Drink$() = "Beer", "Coffee", "Milk", "Tea", "Water"
Line 410 ⟶ 543:
j% -= 1
ENDWHILE
= TRUE</
'''Output:'''
<pre>
Line 425 ⟶ 558:
=={{header|Bracmat}}==
<
(red green white yellow blue,(red.English.))
(dog birds cats horse zebra,(dog.?.Swede.))
Line 507 ⟶ 640:
& props$(!properties...)
& done
);</
Output:
<pre> Solution
Line 518 ⟶ 651:
=={{header|C}}==
<
#include <string.h>
Line 755 ⟶ 888:
return 0;
}</
{{out}}
<pre>% gcc -Wall -O3 -std=c99 zebra.c -o zebra && time ./zebra
Line 769 ⟶ 902:
I'll be the first to admit the following doesn't quite look like a C program. It's in fact in Perl, which outputs a C source, which in turn solves the puzzle. If you think this is long, wait till you see the C it writes.
<
use utf8;
Line 944 ⟶ 1,077:
# write C code. If it's ugly to you: I didn't write; Perl did.
make_c;</
output (ran as <code>perl test.pl | gcc -Wall -x c -; ./a.out</code>):<pre>
0 dunhill cats yellow water Norske
Line 952 ⟶ 1,085:
4 blue_master dog white beer Svensk
</pre>
=={{header|C sharp|C#}}==
Line 1,128 ⟶ 1,091:
<!-- By Martin Freedman, 17/01/2018 -->
This is adapted from a solution to a similar problem by Peter Norvig in his [https://www.udacity.com/course/design-of-computer-programs--cs212 Udacity course CS212], originally written in Python. This is translated from [https://github.com/exercism/python/blob/master/exercises/zebra-puzzle/example.py example python solution on exercism]. This is a Generate-and-Prune Constraint Programming algorithm written with Linq. (See Benchmarks below)
<
using System.Collections.Generic;
using System.Linq;
Line 1,212 ⟶ 1,175:
Read();
}
}</
Produces:
<pre>
Line 1,231 ⟶ 1,194:
This is a different type of generate-and-prune compared to Norvig. The Norvig solution generates each attribute for 5 houses, then prunes and repeats with the next attribute. Here all houses with possible attributes are first generated and pruned to 78 candidates. The second phase proceeds over the combination of 5 houses from that 78, generating and pruning 1 house at a time. (See Benchmarks below)
<
using System.Collections.Generic;
using System.Linq;
Line 1,339 ⟶ 1,302:
}
}
}</
Produces
<pre>The zebra owner is German
Line 1,355 ⟶ 1,318:
{{works with|C sharp|C#|7.1}}
<!-- By Martin Freedman, 9/02/2018 -->
<
using System;
using System.Collections.Generic;
Line 1,440 ⟶ 1,403:
Read();
}
}</
Produces
<pre>The zebra owner is German
Line 1,456 ⟶ 1,419:
{{libheader|Microsoft Solver Foundation}}
<!-- By Martin Freedman, 19/01/2018 based on MS example code-->
<
using System.Collections.Generic;
using System.Linq;
Line 1,568 ⟶ 1,531:
Read();
}
}</
Produces:
<pre>
Line 1,592 ⟶ 1,555:
</pre>
I think that it is Enums (not the use of ''dynamic'' in a dictionary, which is only called 8 times in Combine), and Linq query comprehensions (versus for loops) slow down the 2 non_solver solutions. A non-type-safe non-Enum int version of Combine (not posted here) runs at ~21ms, which is a nearly 5x speed up for that algo. (Not tried with Norvig). Regardless, learning and using the Solver class (and that solution already uses ints rather than enums) provides a dramatic x 100 + performance increase compared to the best manual solutions.
=={{header|C++}}==
This is a modification of the C submission that uses rule classes and reduces the number of permutations evaluated.
<syntaxhighlight lang="cpp">
#include <stdio.h>
#include <string.h>
#define defenum(name, val0, val1, val2, val3, val4) \
enum name { val0, val1, val2, val3, val4 }; \
const char *name ## _str[] = { # val0, # val1, # val2, # val3, # val4 }
defenum( Attrib, Color, Man, Drink, Animal, Smoke );
defenum( Colors, Red, Green, White, Yellow, Blue );
defenum( Mans, English, Swede, Dane, German, Norwegian );
defenum( Drinks, Tea, Coffee, Milk, Beer, Water );
defenum( Animals, Dog, Birds, Cats, Horse, Zebra );
defenum( Smokes, PallMall, Dunhill, Blend, BlueMaster, Prince );
void printHouses(int ha[5][5]) {
const char **attr_names[5] = {Colors_str, Mans_str, Drinks_str, Animals_str, Smokes_str};
printf("%-10s", "House");
for (const char *name : Attrib_str) printf("%-10s", name);
printf("\n");
for (int i = 0; i < 5; i++) {
printf("%-10d", i);
for (int j = 0; j < 5; j++) printf("%-10s", attr_names[j][ha[i][j]]);
printf("\n");
}
}
struct HouseNoRule {
int houseno;
Attrib a; int v;
} housenos[] = {
{2, Drink, Milk}, // Cond 9: In the middle house they drink milk.
{0, Man, Norwegian} // Cond 10: The Norwegian lives in the first house.
};
struct AttrPairRule {
Attrib a1; int v1;
Attrib a2; int v2;
bool invalid(int ha[5][5], int i) {
return (ha[i][a1] >= 0 && ha[i][a2] >= 0) &&
((ha[i][a1] == v1 && ha[i][a2] != v2) ||
(ha[i][a1] != v1 && ha[i][a2] == v2));
}
} pairs[] = {
{Man, English, Color, Red}, // Cond 2: The English man lives in the red house.
{Man, Swede, Animal, Dog}, // Cond 3: The Swede has a dog.
{Man, Dane, Drink, Tea}, // Cond 4: The Dane drinks tea.
{Color, Green, Drink, Coffee}, // Cond 6: drink coffee in the green house.
{Smoke, PallMall, Animal, Birds}, // Cond 7: The man who smokes Pall Mall has birds.
{Smoke, Dunhill, Color, Yellow}, // Cond 8: In the yellow house they smoke Dunhill.
{Smoke, BlueMaster, Drink, Beer}, // Cond 13: The man who smokes Blue Master drinks beer.
{Man, German, Smoke, Prince} // Cond 14: The German smokes Prince
};
struct NextToRule {
Attrib a1; int v1;
Attrib a2; int v2;
bool invalid(int ha[5][5], int i) {
return (ha[i][a1] == v1) &&
((i == 0 && ha[i + 1][a2] >= 0 && ha[i + 1][a2] != v2) ||
(i == 4 && ha[i - 1][a2] != v2) ||
(ha[i + 1][a2] >= 0 && ha[i + 1][a2] != v2 && ha[i - 1][a2] != v2));
}
} nexttos[] = {
{Smoke, Blend, Animal, Cats}, // Cond 11: The man who smokes Blend lives in the house next to the house with cats.
{Smoke, Dunhill, Animal, Horse}, // Cond 12: In a house next to the house where they have a horse, they smoke Dunhill.
{Man, Norwegian, Color, Blue}, // Cond 15: The Norwegian lives next to the blue house.
{Smoke, Blend, Drink, Water} // Cond 16: They drink water in a house next to the house where they smoke Blend.
};
struct LeftOfRule {
Attrib a1; int v1;
Attrib a2; int v2;
bool invalid(int ha[5][5]) {
return (ha[0][a2] == v2) || (ha[4][a1] == v1);
}
bool invalid(int ha[5][5], int i) {
return ((i > 0 && ha[i][a1] >= 0) &&
((ha[i - 1][a1] == v1 && ha[i][a2] != v2) ||
(ha[i - 1][a1] != v1 && ha[i][a2] == v2)));
}
} leftofs[] = {
{Color, Green, Color, White} // Cond 5: The green house is immediately to the left of the white house.
};
bool invalid(int ha[5][5]) {
for (auto &rule : leftofs) if (rule.invalid(ha)) return true;
for (int i = 0; i < 5; i++) {
#define eval_rules(rules) for (auto &rule : rules) if (rule.invalid(ha, i)) return true;
eval_rules(pairs);
eval_rules(nexttos);
eval_rules(leftofs);
}
return false;
}
void search(bool used[5][5], int ha[5][5], const int hno, const int attr) {
int nexthno, nextattr;
if (attr < 4) {
nextattr = attr + 1;
nexthno = hno;
} else {
nextattr = 0;
nexthno = hno + 1;
}
if (ha[hno][attr] != -1) {
search(used, ha, nexthno, nextattr);
} else {
for (int i = 0; i < 5; i++) {
if (used[attr][i]) continue;
used[attr][i] = true;
ha[hno][attr] = i;
if (!invalid(ha)) {
if ((hno == 4) && (attr == 4)) {
printHouses(ha);
} else {
search(used, ha, nexthno, nextattr);
}
}
used[attr][i] = false;
}
ha[hno][attr] = -1;
}
}
int main() {
bool used[5][5] = {};
int ha[5][5]; memset(ha, -1, sizeof(ha));
for (auto &rule : housenos) {
ha[rule.houseno][rule.a] = rule.v;
used[rule.a][rule.v] = true;
}
search(used, ha, 0, 0);
return 0;
}
</syntaxhighlight>
{{out}}
<pre>
$ g++ -O3 -std=c++11 zebra.cpp -o zebracpp && time ./zebracpp
House Color Man Drink Animal Smoke
0 Yellow Norwegian Water Cats Dunhill
1 Blue Dane Tea Horse Blend
2 Red English Milk Birds PallMall
3 Green German Coffee Zebra Prince
4 White Swede Beer Dog BlueMaster
real 0m0.003s
user 0m0.000s
sys 0m0.000s
</pre>
My measured time is slower than that posted for the original C code, but on my machine this C++ code is faster than the original C code.
=={{header|Clojure}}==
This solution uses the contributed package ''clojure.core.logic'' (with ''clojure.tools.macro''), a mini-Kanren based logic solver. The solution is basically the one in [http://github.com/swannodette/logic-tutorial Swannodette's logic tutorial], adapted to the problem statement here.
<
(:refer-clojure :exclude [==])
(:use [clojure.core.logic]
Line 1,637 ⟶ 1,770:
(println "full solution (in house order):")
(doseq [h soln] (println " " h)))
</syntaxhighlight>
{{output}}
<pre>solution count: 1
Line 1,655 ⟶ 1,788:
This is adapted from a solution to a similar problem by Peter Norvig in his [https://www.udacity.com/course/design-of-computer-programs--cs212 Udacity course CS212], originally written in Python but equally applicable in any language with for-comprehensions.
<
(:require [clojure.math.combinatorics :as c]))
Line 1,702 ⟶ 1,835:
(println (apply format "%5s %-11s %-7s %-7s %-12s %-6s"
(map #(% i) (cons inc solution)))))))
</syntaxhighlight>
{{output}}
<pre>user=> (time (zebra/-main))
Line 1,717 ⟶ 1,850:
nil
</pre>
=={{header|Crystal}}==
{{trans|Ruby}}
<syntaxhighlight lang="ruby">CONTENT = {House: [""],
Nationality: %i[English Swedish Danish Norwegian German],
Colour: %i[Red Green White Blue Yellow],
Pet: %i[Dog Birds Cats Horse Zebra],
Drink: %i[Tea Coffee Milk Beer Water],
Smoke: %i[PallMall Dunhill BlueMaster Prince Blend]}
def adjacent?(n, i, g, e)
(0..3).any? { |x| (n[x] == i && g[x + 1] == e) || (n[x + 1] == i && g[x] == e) }
end
def leftof?(n, i, g, e)
(0..3).any? { |x| n[x] == i && g[x + 1] == e }
end
def coincident?(n, i, g, e)
n.each_index.any? { |x| n[x] == i && g[x] == e }
end
def solve_zebra_puzzle
CONTENT[:Nationality].each_permutation { |nation|
next unless nation.first == :Norwegian # 10
CONTENT[:Colour].each_permutation { |colour|
next unless leftof?(colour, :Green, colour, :White) # 5
next unless coincident?(nation, :English, colour, :Red) # 2
next unless adjacent?(nation, :Norwegian, colour, :Blue) # 15
CONTENT[:Pet].each_permutation { |pet|
next unless coincident?(nation, :Swedish, pet, :Dog) # 3
CONTENT[:Drink].each_permutation { |drink|
next unless drink[2] == :Milk # 9
next unless coincident?(nation, :Danish, drink, :Tea) # 4
next unless coincident?(colour, :Green, drink, :Coffee) # 6
CONTENT[:Smoke].each_permutation { |smoke|
next unless coincident?(smoke, :PallMall, pet, :Birds) # 7
next unless coincident?(smoke, :Dunhill, colour, :Yellow) # 8
next unless coincident?(smoke, :BlueMaster, drink, :Beer) # 13
next unless coincident?(smoke, :Prince, nation, :German) # 14
next unless adjacent?(smoke, :Blend, pet, :Cats) # 11
next unless adjacent?(smoke, :Blend, drink, :Water) # 16
next unless adjacent?(smoke, :Dunhill, pet, :Horse) # 12
print_out(nation, colour, pet, drink, smoke)
}
}
}
}
}
end
def print_out(nation, colour, pet, drink, smoke)
width = CONTENT.map { |k, v| {k.to_s.size, v.max_of { |y| y.to_s.size }}.max }
fmt = width.map { |w| "%-#{w}s" }.join(" ")
national = nation[pet.index(:Zebra).not_nil!]
puts "The Zebra is owned by the man who is #{national}", ""
puts fmt % CONTENT.keys, fmt % width.map { |w| "-" * w }
[nation, colour, pet, drink, smoke].transpose.each.with_index(1) { |x, n| puts fmt % ([n] + x) }
end
solve_zebra_puzzle</syntaxhighlight>
=={{header|Curry}}==
{{Works with|PAKCS}}
<
import Findall (findall)
Line 1,762 ⟶ 1,956:
main = findall $ \(hs,who) -> houses hs & H _ who Zebra _ _ `member` hs</
{{Output}} Using [http://www-ps.informatik.uni-kiel.de/~pakcs/webpakcs/main.cgi web interface].
<pre>Execution time: 180 msec. / elapsed: 180 msec.
Line 1,770 ⟶ 1,964:
{{trans|Ada}}
Most foreach loops in this program are static.
<
enum Content { Beer, Coffee, Milk, Tea, Water,
Line 1,864 ⟶ 2,058:
solve(M, Test.Drink, 5);
}</
{{out}}
<pre> One: Water Norwegian Yellow Dunhill Cat
Line 1,876 ⟶ 2,070:
{{trans|Python}}
This requires the module of the first D entry from the Permutations Task.
<
uint factorial(in uint n) pure nothrow @nogc @safe
Line 1,975 ⟶ 2,169:
writeln;
}
}</
{{out}}
<pre>Found a solution:
Line 1,990 ⟶ 2,184:
{{trans|PicoLisp}}
This requires the module of the second D entry from the Permutations Task.
<
import std.stdio, std.algorithm, permutations2;
Line 2,022 ⟶ 2,216:
nextTo(drinks, Water, smokes, Blend))
writefln("%(%10s\n%)\n", [houses, persons, drinks, pets, smokes]);
}</
{{out}}
<pre>[ Yellow, Blue, Red, Green, White]
Line 2,033 ⟶ 2,227:
=={{header|EchoLisp}}==
We use the '''amb''' library to solve the puzzle. The number of tries - calls to zebra-puzzle - is only 1900, before finding all solutions. Note that there are no declarations for things (cats, tea, ..) or categories (animals, drinks, ..) which are discovered when reading the constraints.
<
(lib 'hash)
(lib 'amb)
Line 2,106 ⟶ 2,300:
(amb-fail) ;; will ensure ALL solutions are printed
)
</syntaxhighlight>
{{out}}
<
(define (task)
(amb-run zebra-puzzle (amb-make-context) (iota 5)))
Line 2,122 ⟶ 2,316:
→ #f
</syntaxhighlight>
=={{header|Elixir}}==
{{trans|Ruby}}
<
defp adjacent?(n,i,g,e) do
Enum.any?(0..3, fn x ->
Line 2,199 ⟶ 2,393:
Smoke: ~w[PallMall Dunhill BlueMaster Prince Blend]a ]
ZebraPuzzle.solve(content)</
{{out}}
Line 2,216 ⟶ 2,410:
=={{header|Erlang}}==
This solution generates all houses that fits the rules for single houses, then it checks multi-house rules. It would be faster to check multi-house rules while generating the houses. I have not added this complexity since the current program takes just a few seconds.
<syntaxhighlight lang="erlang">
-module( zebra_puzzle ).
Line 2,334 ⟶ 2,528:
is_rule_16_ok( _House1, _House2, _House3, #house{drink=water}, #house{smoke=blend} ) -> true;
is_rule_16_ok( _House1, _House2, _House3, _House4, _House5 ) -> false.
</syntaxhighlight>
{{out}}
<pre>
Line 2,348 ⟶ 2,542:
=={{header|ERRE}}==
<syntaxhighlight lang="erre">
PROGRAM ZEBRA_PUZZLE
Line 2,454 ⟶ 2,648:
PRINT("Number of solutions=";SOLUTIONS%)
PRINT("Solved in ";TIMER-T1;" seconds")
END PROGRAM</
{{out}}
<pre>
Line 2,468 ⟶ 2,662:
=={{header|F_Sharp|F#}}==
This task uses [
<
(*Here I solve the Zebra puzzle using Plain Changes, definitely a challenge to some campanoligist to solve it using Grandsire Doubles.
Nigel Galloway: January 27th., 2017 *)
type N = |English=0 |Swedish=1|Danish=2 |German=3|Norwegian=4
type I = |Tea=0 |Coffee=1 |Milk=2 |Beer=3 |Water=4
type G = |Dog=0 |Birds=1 |Cats=2 |Horse=3 |Zebra=4
type E = |Red=0 |Green=1 |White=2 |Blue=3 |Yellow=4
type L = |PallMall=0|Dunhill=1|BlueMaster=2|Prince=3|Blend=4
type NIGELz={Nz:N[];Iz:I[];Gz:G[];Ez:E[];Lz:L[]}
let fn (i:'n[]) g (e:'g[]) l = //coincident?
Line 2,491 ⟶ 2,685:
_fn 0
let fg (i:'n[]) g (e:'g[]) l = (fi i g e l || fi e l i g) //adjacent?
let n = Ring.PlainChanges [|
let i = Ring.PlainChanges [|
let g = Ring.PlainChanges [|
let e = Ring.PlainChanges [|
let l = Ring.PlainChanges [|
match n|>Seq.map(fun n->{Nz=
|>Seq.collect(fun n->i|>Seq.map(fun i->{n with Iz=
|>Seq.collect(fun n->g|>Seq.map(fun i->{n with Gz=
|>Seq.collect(fun n->e|>Seq.map(fun i->{n with Ez=
|>Seq.collect(fun n->l|>Seq.map(fun i->{n with Lz=
|Some(nn) -> nn.Gz |> Array.iteri(fun n g -> if (g = G.Zebra) then printfn "\nThe man who owns a zebra is %A\n" nn.Nz.[n]); printfn "%A" nn
|None -> printfn "No solution found"
</syntaxhighlight>
{{out}}
<pre>
Line 2,524 ⟶ 2,718:
=={{header|FormulaOne}}==
<syntaxhighlight lang="formulaone">
// First, let's give some type-variables some values:
Nationality = Englishman | Swede | Dane | Norwegian | German
Colour = Red | Green | Yellow | Blue | White
Line 2,531 ⟶ 2,725:
Domestic = Dog | Bird | Cat | Zebra | Horse
Beverage = Tea | Coffee | Milk | Beer | Water
{
We use injections to make the array-elements unique.
Example: 'Pet' is an array of unique elements of type 'Domestic', indexed by 'Nationality'.
In the predicate 'Zebra', we use this injection 'Pet' to define the array-variable 'pet'
as a parameter of the 'Zebra'-predicate.
The symbol used is the '->>'. 'Nationality->>Domestic' can be read as 'Domestic(Nationality)'
in "plain array-speak";
the difference being that the elements are by definition unique (cf. 'injective function').
So, in FormulaOne we use a formula like: 'pet(Swede) = Dog', which simply means that the 'Swede'
(type 'Nationality') has a 'pet' (type 'Pet',
which appears to be a 'Dog' (type 'Domestic').
Or, one could say that the 'Swede' has been mapped to the 'Dog' (Oh, well...).
}
Line 2,549 ⟶ 2,746:
HouseColour = Nationality->>Colour
Smoke = Nationality->>Cigarette
pred Zebra(
// For convenience sake, some temporary place_holder variables are used.
// An underscore distinguishes them:
smoke(pallmall_smoker) = PallMall &
smoke(blend_smoker) = Blend &
smoke(dunhill_smoker) = Dunhill &
smoke(bluemaster_smoker) = BlueMaster &
pet(cat_keeper) = Cat &
pet(neighbour_dunhill_smoker) = Horse &
{ 2. The English man lives in the red house: }
{ 3. The Swede has a dog: }
Line 2,580 ⟶ 2,777:
}
{ 5. The green house is immediately to the left of the white house
{ 6. They drink coffee in the green house: }
Line 2,593 ⟶ 2,790:
smoke(yellow_house) = Dunhill &
{ 9. In the middle house (third in the row) they drink milk: }
drink(
{10. The Norwegian lives in the first house: }
{11. The man who smokes Blend lives in the house next to the house with cats
{12. In a house next to the house where they have a horse, they smoke Dunhill: }
Neighbour(dunhill_smoker, neighbour_dunhill_smoker,
{13. The man who smokes Blue Master drinks beer: }
Line 2,612 ⟶ 2,809:
smoke(German) = Prince &
{15. The Norwegian lives next to the blue house
house_colour(house_order(Second)) = Blue &
{16. They drink water in a house next to the house where they smoke Blend: }
drink(neighbour_blend_smoker) = Water &
Neighbour(blend_smoker, neighbour_blend_smoker,
{ A simplified solution would number the houses 1, 2, 3, 4, 5
Line 2,627 ⟶ 2,823:
}
local pred Neighbour(neighbour1::Nationality, neighbour2::Nationality,
neighbour1 <> neighbour2 &
( house1 = house2 + 1 |
house1 = house2 - 1 )
local pred LeftOf(neighbour1::Nationality, neighbour2::Nationality,
neighbour1 <> neighbour2 &
house1 = house2 - 1
{
The 'all'-query in FormulaOne:
all Zebra(
gives, of course, only one solution, so it can be replaced by:
one Zebra(
}
Line 2,654 ⟶ 2,850:
Domestic = Dog | Bird | Cat | Zebra | Horse
Beverage = Tea | Coffee | Milk | Beer | Water
Pet = Nationality->>Domestic
Line 2,660 ⟶ 2,856:
HouseColour = Nationality->>Colour
Smoke = Nationality->>Cigarette
pred Zebra(
smoke(pallmall_smoker) = PallMall &
smoke(blend_smoker) = Blend &
Line 2,673 ⟶ 2,869:
pet(cat_keeper) = Cat &
pet(neighbour_dunhill_smoker) = Horse &
house_colour(Englishman) = Red &
pet(Swede) = Dog &
drink(Dane) = Tea &
LeftOf(green_house, white_house,
drink(green_house) = Coffee &
pet(pallmall_smoker) = Bird &
smoke(yellow_house) = Dunhill &
drink(
Neighbour(blend_smoker, cat_keeper,
Neighbour(dunhill_smoker, neighbour_dunhill_smoker,
drink(bluemaster_smoker) = Beer &
smoke(German) = Prince &
drink(neighbour_blend_smoker) = Water &
Neighbour(blend_smoker, neighbour_blend_smoker,
local pred Neighbour(neighbour1::Nationality, neighbour2::Nationality,
neighbour1 <> neighbour2 &
( house1 = house2 + 1 | house1 = house2 - 1 )
local pred LeftOf(neighbour1::Nationality, neighbour2::Nationality,
neighbour1 <> neighbour2 &
house1 = house2 - 1
</syntaxhighlight>
{{out}}
<pre>
pet = [ {Englishman} Birds, {Swede} Dog, {Dane} Horse, {Norwegian} Cats, {German}
smokes = [ {Englishman} PallMall, {Swede} BlueMaster, {Dane} Blend, {Norwegian} Dunhill, {German} Prince ]
drinks = [ {Englishman} Milk, {Swede} Beer, {Dane} Tea, {Norwegian}
</pre>
=={{header|GAP}}==
<
local i;
for i in [1..4] do
Line 2,770 ⟶ 2,966:
Print(cigars,"\n");
od;od;od;od;od;
</syntaxhighlight>
=={{header|Go}}==
<
import (
Line 3,066 ⟶ 3,262:
fmt.Println(n, "solution found")
fmt.Println(sol)
}</
{{out}}
<pre>Generated 51 valid houses
Line 3,084 ⟶ 3,280:
=={{header|Haskell}}==
<
import Control.Applicative ((<$>), (<*>))
Line 3,174 ⟶ 3,370:
leftOf p q
| (_:h:_) <- dropWhile (not . p) solution = q h
| otherwise = False</
{{out}}
<pre>House {color = Yellow, man = Nor, pet = Cats, drink = Water, smoke = Dunhill}
Line 3,189 ⟶ 3,385:
(a little faster version)
<
import Data.List
Line 3,248 ⟶ 3,444:
print [nation | (nation, _, Zebra, _, _) <- answer]
putStrLn "" )
putStrLn "No more solutions!"</
Output:
Line 3,263 ⟶ 3,459:
Propositions 1 .. 16 without 9,10 and15
<
cr=: (('English';'red') 0 3} ehs);<('Dane';'tea') 0 2}ehs
Line 3,275 ⟶ 3,471:
next=: <((<'Blend') 4 }ehs);<(<'water')2}ehs
next=: next,<((<'Blend') 4 }ehs);<(<'cats')1}ehs
next=: next,<((<'Dunhill') 4}ehs);<(<'horse')1}ehs</
'''Example'''
<
┌─────────────────┬───────────┐
│┌┬┬──────┬─────┬┐│┌┬┬┬─────┬┐│
││││coffee│green│││││││white│││
│└┴┴──────┴─────┴┘│└┴┴┴─────┴┘│
└─────────────────┴───────────┘</
Collections of all variants of the propositions:
<
hcs=:~. (A.~i.@!@#)cs,2$<ehs
hlof=:(-i.4) |."0 1 lof,3$<ehs
hnext=: ,/((i.4) |."0 1 (3$<ehs)&,)"1 ;(,,:|.)&.> next</
We start the row of houses with fixed properties 9, 10 and 15.
<
{{out}}
<
┌───────────────┬──────────┬──────────┬──────┬──────┐
│┌─────────┬┬┬┬┐│┌┬┬┬────┬┐│┌┬┬────┬┬┐│┌┬┬┬┬┐│┌┬┬┬┬┐│
││Norwegian││││││││││blue││││││milk││││││││││││││││││
│└─────────┴┴┴┴┘│└┴┴┴────┴┘│└┴┴────┴┴┘│└┴┴┴┴┘│└┴┴┴┴┘│
└───────────────┴──────────┴──────────┴──────┴──────┘</
Set of proposition variants:
<
The worker and its helper verbs
<
filter=: #~*./@:(2>#S:0)"1
compose=: [: filter f. [: ,/ select f. L:0"1"1 _
Line 3,312 ⟶ 3,508:
z=.(#~1=[:+/"1 (0=#)S:0"1) h=.~. h
end.
)</
{{out}}
<
┌─────────┬─────┬──────┬──────┬──────────┐
│Norwegian│cats │water │yellow│Dunhill │
Line 3,325 ⟶ 3,521:
├─────────┼─────┼──────┼──────┼──────────┤
│Swede │dog │beer │white │BlueMaster│
└─────────┴─────┴──────┴──────┴──────────┘</
So, the German owns the zebra.
'''Alternative'''
<br>A longer running solver by adding the zebra variants.
<
solve3=: 4 :0
Line 3,337 ⟶ 3,533:
z=. f^:(3>[:#(#~p"1)&>)^:_ <,:x
>"0 (#~([:*./[:;[:<@({.~:}.)\.;)"1)(#~p"1); z
)</
{{out}}
<
┌─────────┬─────┬──────┬──────┬──────────┐
│Norwegian│cats │water │yellow│Dunhill │
Line 3,350 ⟶ 3,546:
├─────────┼─────┼──────┼──────┼──────────┤
│Swede │dog │beer │white │BlueMaster│
└─────────┴─────┴──────┴──────┴──────────┘</
=={{header|Java}}==
This Java solution includes
* The outer class <tt>Zebra</tt>
* A PossibleLine
* A set of PossibleLines
* The Solver
<syntaxhighlight lang="java">package org.rosettacode.zebra;
import java.util.Arrays;
import java.util.Iterator;
import java.util.LinkedHashSet;
import java.util.Objects;
import java.util.Set;
public class
private static final int[] orders = {1, 2, 3, 4, 5};
private static final String[] nations = {"English", "Danish", "German", "Swedish", "Norwegian"};
private static final String[] animals = {"Zebra", "Horse", "Birds", "Dog", "Cats"};
private static final String[] drinks = {"Coffee", "Tea", "Beer", "Water", "Milk"};
private static final String[] cigarettes = {"Pall Mall", "Blend", "Blue Master", "Prince", "Dunhill"};
private static final String[] colors = {"Red", "Green", "White", "Blue", "Yellow"};
static class Solver {
private final PossibleLines puzzleTable = new PossibleLines();
PossibleLines constraints = new PossibleLines();
constraints.add(new PossibleLine(null, "English", "Red", null, null, null));
constraints.add(new PossibleLine(null, "Swedish", null, "Dog", null, null));
constraints.add(new PossibleLine(null, "Danish", null, null, "Tea", null));
constraints.add(new PossibleLine(null, null, "Green", null, "Coffee", null));
constraints.add(new PossibleLine(null, null, null, "Birds", null, "Pall Mall"));
constraints.add(new PossibleLine(null, null, "Yellow", null, null, "Dunhill"));
constraints.add(new PossibleLine(3, null, null, null, "Milk", null));
constraints.add(new PossibleLine(1, "Norwegian", null, null, null, null));
constraints.add(new PossibleLine(null, null, null, null, "Beer", "Blue Master"));
constraints.add(new PossibleLine(null, "German", null, null, null, "Prince"));
constraints.add(new PossibleLine(2, null, "Blue", null, null, null));
//Creating all possible combination of a puzzle line.
//The maximum number of lines is 5^^6 (15625).
//Each combination line is checked against a set of knowing facts, thus
//only a small number of line result at the end.
for (Integer orderId : Zebra.orders) {
for (String nation : Zebra.nations) {
for (String color : Zebra.colors) {
for (String animal : Zebra.animals) {
for (String drink : Zebra.drinks) {
for (String cigarette : Zebra.cigarettes) {
addPossibleNeighbors(constraints, orderId, nation, color, animal, drink, cigarette);
}
}
}
}
}
}
System.out.println("After general rule set validation, remains " +
puzzleTable.size() + " lines.");
for (Iterator<PossibleLine> it = puzzleTable.iterator(); it.hasNext(); ) {
PossibleLine possibleLine = it.next();
if (possibleLine.leftNeighbor != null) {
PossibleLine neighbor = possibleLine.leftNeighbor;
if (neighbor.order < 1 || neighbor.order > 5) {
validLine = false;
it.remove();
}
}
if (validLine && possibleLine.rightNeighbor != null) {
PossibleLine neighbor = possibleLine.rightNeighbor;
if (neighbor.order < 1 || neighbor.order > 5) {
it.remove();
}
}
}
System.out.println("After removing out of bound neighbors, remains " +
puzzleTable.size() + " lines.");
//Setting left and right neighbors
for (PossibleLine puzzleLine : puzzleTable) {
for (PossibleLine leftNeighbor : puzzleLine.neighbors) {
PossibleLine rightNeighbor = leftNeighbor.copy();
//make it left neighbor
leftNeighbor.order = puzzleLine.order - 1;
if (puzzleTable.contains(leftNeighbor)) {
if (puzzleLine.leftNeighbor != null)
puzzleLine.leftNeighbor.merge(leftNeighbor);
else
puzzleLine.setLeftNeighbor(leftNeighbor);
}
rightNeighbor.order = puzzleLine.order + 1;
if (puzzleTable.contains(rightNeighbor)) {
if (puzzleLine.rightNeighbor != null)
puzzleLine.rightNeighbor.merge(rightNeighbor);
else
puzzleLine.setRightNeighbor(rightNeighbor);
}
}
}
int iteration = 1;
//Recursively validate against neighbor rules
while (puzzleTable.size() > 5 && lastSize != puzzleTable.size()) {
lastSize = puzzleTable.size();
puzzleTable.clearLineCountFlags();
recursiveSearch(null, puzzleTable, -1);
constraints.clear();
// Assuming we'll get at leas one valid line each iteration, we create
// a set of new rules with lines which have no more then one instance of same OrderId.
for (int i = 1; i < 6; i++) {
if (puzzleTable.getLineCountByOrderId(i) == 1)
constraints.addAll(puzzleTable.getSimilarLines(new PossibleLine(i, null, null, null, null,
null)));
}
puzzleTable.removeIf(puzzleLine -> !constraints.accepts(puzzleLine));
System.out.println("After " + iteration + " recursive iteration, remains "
+ puzzleTable.size() + " lines");
iteration++;
}
// Print the results
System.out.println("-------------------------------------------");
if (puzzleTable.size() == 5) {
for (PossibleLine puzzleLine : puzzleTable) {
System.out.println(puzzleLine.getWholeLine());
}
} else
System.out.println("Sorry, solution not found!");
}
private void addPossibleNeighbors(
PossibleLines constraints, Integer orderId, String nation,
String color, String animal, String drink, String cigarette) {
boolean validLine = true;
PossibleLine pzlLine = new PossibleLine(orderId,
color,
animal,
drink,
cigarette);
// Checking against a set of knowing facts
if (constraints.accepts(pzlLine)) {
// Adding rules of neighbors
if (cigarette.equals("Blend")
&& (animal.equals("Cats") || drink.equals("Water")))
validLine = false;
if (cigarette.equals("Dunhill")
&& animal.equals("Horse"))
puzzleTable.add(pzlLine);
//set neighbors constraints
if (color.equals("Green")) {
pzlLine.setRightNeighbor(
new PossibleLine(null, null, "White", null, null, null));
}
if (color.equals("White")) {
pzlLine.setLeftNeighbor(
new PossibleLine(null, null, "Green", null, null, null));
if (animal.equals("Cats") && !cigarette.equals("Blend")) {
pzlLine.neighbors.add(new PossibleLine(null, null, null, null, null,
}
if (cigarette.equals("Blend") && !animal.equals("Cats")) {
pzlLine.neighbors.add(new PossibleLine(null, null, null, "Cats", null
, null));
}
//
if (drink.equals("Water")
&& !animal.equals("Cats")
&& !cigarette.equals("Blend")) {
pzlLine.neighbors.add(new PossibleLine(null, null, null, null, null,
"Blend"));
}
if (cigarette.equals("Blend") && !drink.equals("Water")) {
pzlLine.neighbors.add(new PossibleLine(null, null, null, null, "Water"
, null));
}
//
if (animal.equals("Horse") && !cigarette.equals("Dunhill")) {
pzlLine.neighbors.add(new PossibleLine(null, null, null, null, null,
"Dunhill"));
}
if (cigarette.equals("Dunhill") && !animal.equals("Horse")) {
pzlLine.neighbors.add(new PossibleLine(null, null, null, "Horse",
null, null));
}
}
}
}
// Recursively checks the input set to ensure each line has right neighbor.
// Neighbors can be of three type, left, right or undefined.
// Direction: -1 left, 0 undefined, 1 right
private boolean recursiveSearch(PossibleLine pzzlNodeLine,
PossibleLines possibleLines, int direction) {
boolean validLeaf = false;
boolean hasNeighbor;
PossibleLines puzzleSubSet;
for (Iterator<PossibleLine> it = possibleLines.iterator(); it.hasNext(); ) {
PossibleLine pzzlLeafLine = it.next();
validLeaf = false;
hasNeighbor = pzzlLeafLine.hasNeighbor(direction);
if (hasNeighbor) {
puzzleSubSet = puzzleTable.getSimilarLines(pzzlLeafLine.getNeighbor(direction));
if (puzzleSubSet != null) {
if (pzzlNodeLine != null)
validLeaf = puzzleSubSet.contains(pzzlNodeLine);
else
validLeaf = recursiveSearch(pzzlLeafLine, puzzleSubSet, -1 * direction);
}
}
if (!validLeaf && pzzlLeafLine.hasNeighbor(-1 * direction)) {
hasNeighbor = true;
puzzleSubSet = puzzleTable.getSimilarLines(pzzlLeafLine.getNeighbor(-1 * direction));
if (pzzlNodeLine != null)
validLeaf = puzzleSubSet.contains(pzzlNodeLine);
else
validLeaf = recursiveSearch(pzzlLeafLine, puzzleSubSet, direction);
}
}
if (pzzlNodeLine != null && validLeaf)
if (pzzlNodeLine == null && hasNeighbor && !validLeaf) {
}
if (hasNeighbor && validLeaf) {
possibleLines.riseLineCountFlags(pzzlLeafLine.order);
if (!hasNeighbor) {
possibleLines.riseLineCountFlags(pzzlLeafLine.order);
}
return validLeaf;
}
}
public static void
Solver solver = new Solver();
}
static class PossibleLines extends LinkedHashSet<PossibleLine> {
private final int[] count = new int[5];
public
return ((PossibleLine) toArray()[index]);
}
public PossibleLines getSimilarLines(PossibleLine searchLine) {
PossibleLines puzzleSubSet = new PossibleLines();
for (PossibleLine possibleLine : this) {
if (possibleLine.getCommonFactsCount(searchLine) == searchLine.getFactsCount())
}
return null;
return puzzleSubSet;
}
public boolean contains(PossibleLine searchLine) {
for (PossibleLine puzzleLine : this) {
if (puzzleLine.getCommonFactsCount(searchLine) == searchLine.getFactsCount())
return
}
return false;
}
public boolean accepts(PossibleLine searchLine) {
int passed = 0;
int
for (PossibleLine puzzleSetLine : this)
int lineFactsCnt =
int comnFactsCnt =
if (lineFactsCnt != comnFactsCnt && lineFactsCnt != 0 && comnFactsCnt != 0) {
}
if (lineFactsCnt == comnFactsCnt)
passed++;
}
return passed >= 0 && notpassed == 0;
}
public void riseLineCountFlags(int lineOrderId) {
count[lineOrderId -
Arrays.fill(count, 0);
public int getLineCountByOrderId(int lineOrderId) {
return count[lineOrderId - 1];
}
static class PossibleLine {
Integer order;
String
String
String animal;
String
String
PossibleLine leftNeighbor;
Set<PossibleLine> neighbors = new LinkedHashSet<>();
public PossibleLine(Integer order, String nation, String color,
String animal, String drink, String cigarette) {
this.animal = animal;
this.cigarette = cigarette;
this.color = color;
this.drink = drink;
this.nation = nation;
this.order = order;
}
@Override
public boolean equals(Object obj) {
return obj instanceof PossibleLine
&& getWholeLine().equals(((PossibleLine) obj).getWholeLine());
}
public int getFactsCount() {
int facts = 0;
facts += order != null ? 1 : 0;
facts += nation != null ? 1 : 0;
facts += color != null ? 1 : 0;
facts += animal != null ? 1 : 0;
facts += cigarette != null ? 1 : 0;
facts += drink != null ? 1 : 0;
return facts;
}
private static int common(Object a, Object b) {
return a != null && Objects.equals(a, b) ? 1 : 0;
}
public int getCommonFactsCount(PossibleLine facts) {
return common(order, facts.order)
+ common(nation, facts.nation)
+ common(color, facts.color)
+ common(animal, facts.animal)
+ common(cigarette, facts.cigarette)
+ common(drink, facts.drink);
}
public void setLeftNeighbor(PossibleLine leftNeighbor) {
this.leftNeighbor = leftNeighbor;
this.leftNeighbor.order = order - 1;
}
public void setRightNeighbor(PossibleLine rightNeighbor) {
this.rightNeighbor = rightNeighbor;
this.rightNeighbor.order = order + 1;
}
public boolean hasNeighbor(int direction) {
return getNeighbor(direction) != null;
}
public PossibleLine getNeighbor(int direction) {
if (direction < 0)
return leftNeighbor;
else
return rightNeighbor;
}
public String getWholeLine() {
return order + " - " +
nation + " - " +
color + " - " +
animal + " - " +
drink + " - " +
cigarette;
}
@Override
public int hashCode() {
return Objects.hash(order, nation, color, animal, drink, cigarette);
}
public void merge(PossibleLine mergedLine) {
if (order == null) order = mergedLine.order;
if (nation == null) nation = mergedLine.nation;
if (color == null) color = mergedLine.color;
if (animal == null) animal = mergedLine.animal;
if (drink == null) drink = mergedLine.drink;
if (cigarette == null) cigarette = mergedLine.cigarette;
}
public PossibleLine copy() {
PossibleLine clone = new PossibleLine(order, nation, color, animal, drink, cigarette);
clone.leftNeighbor = leftNeighbor;
clone.rightNeighbor = rightNeighbor;
clone.neighbors = neighbors; // shallow copy
return clone;
}
}
}</syntaxhighlight>
{{out}}
<pre>
Line 4,026 ⟶ 4,009:
'''Part 1''': Generic filters for unification and matching
<syntaxhighlight lang="jq">
# Attempt to unify the input object with the specified object
def unify( object ):
Line 4,048 ⟶ 4,031:
| if $ans then .[i] = $ans else empty end
else empty
end ;</
'''Part 2''': Zebra Puzzle
<
# { "number": _, "nation": _, "owns": _, "color": _, "drinks": _, "smokes": _}
Line 4,109 ⟶ 4,092:
;
zebra</
{{Out}}
<div style="overflow:scroll; height:400px;">
<
[
{
Line 4,159 ⟶ 4,142:
real 0m0.284s
user 0m0.260s
sys 0m0.005s</
=={{header|Julia}}==
<syntaxhighlight lang="julia">
# Julia 1.0
using Combinatorics
function make(str, test )
filter(test, collect( permutations(split(str))) )
end
Line 4,173 ⟶ 4,158:
drinks = make("beer coffee milk tea water", x -> "milk" == x[3])
#Julia 1.0 compatible
colors = make("blue green red white yellow",
x -> 1 == findfirst(
pets = make("birds cats dog horse zebra")
Line 4,187 ⟶ 4,173:
1 == abs(findfirst(xs, x) - findfirst(ys, y))
end
function print_houses(n, pet, nationality, colors, drink, smokes)
println("$n, $pet, $nationality $colors $drink $smokes")
end
for m = men, c = colors
Line 4,201 ⟶ 4,191:
adj("blend",s,"cats",p) &&
adj("horse",p,"dunhill",s)
println("Zebra is owned by ", m[findfirst(
println("Houses:")
for
end
end
Line 4,215 ⟶ 4,204:
end
end
</syntaxhighlight>
{{out}}
Line 4,221 ⟶ 4,211:
Zebra is owned by german
Houses:
1, cats, norwegian
2, horse, danish
3, birds, english
4, zebra, german
5, dog, swedish
</pre>
===Constraint Programming Version===
Using the rules from https://github.com/SWI-Prolog/bench/blob/master/programs/zebra.pl
<syntaxhighlight lang="julia"># Julia 1.4
using JuMP
using GLPK
c = Dict(s => i for (i, s) in enumerate(split("blue green ivory red yellow")))
n = Dict(s => i for (i, s) in enumerate(split("english japanese norwegian spanish ukrainian")))
p = Dict(s => i for (i, s) in enumerate(split("dog fox horse snails zebra")))
d = Dict(s => i for (i, s) in enumerate(split("coffee milk orangejuice tea water")))
s = Dict(s => i for (i, s) in enumerate(split("chesterfields kools luckystrikes parliaments winstons")))
model = Model(GLPK.Optimizer)
@variable(model, colors[1:5, 1:5], Bin)
@constraints(model, begin
[h in 1:5], sum(colors[h, :]) == 1
[c in 1:5], sum(colors[:, c]) == 1
end)
@variable(model, nations[1:5, 1:5], Bin)
@constraints(model, begin
[h in 1:5], sum(nations[h, :]) == 1
[n in 1:5], sum(nations[:, n]) == 1
end)
@variable(model, pets[1:5, 1:5], Bin)
@constraints(model, begin
[h in 1:5], sum(pets[h, :]) == 1
[p in 1:5], sum(pets[:, p]) == 1
end)
@variable(model, drinks[1:5, 1:5], Bin)
@constraints(model, begin
[h in 1:5], sum(drinks[h, :]) == 1
[d in 1:5], sum(drinks[:, d]) == 1
end)
@variable(model, smokes[1:5, 1:5], Bin)
@constraints(model, begin
[h in 1:5], sum(smokes[h, :]) == 1
[s in 1:5], sum(smokes[:, s]) == 1
end)
@constraint(model, [h=1:5], colors[h, c["red"]] == nations[h, n["english"]])
@constraint(model, [h=1:5], nations[h, n["spanish"]] == pets[h, p["dog"]])
@constraint(model, [h=1:5], colors[h, c["green"]] == drinks[h, d["coffee"]])
@constraint(model, [h=1:5], nations[h, n["ukrainian"]] == drinks[h, d["tea"]])
@constraint(model, [h=1:5], colors[h, c["ivory"]] == get(colors, (h+1, c["green"]), 0))
@constraint(model, [h=1:5], pets[h, p["snails"]] == smokes[h, s["winstons"]])
@constraint(model, [h=1:5], colors[h, c["yellow"]] == smokes[h, s["kools"]])
@constraint(model, drinks[3, d["milk"]] == 1)
@constraint(model, nations[1, n["norwegian"]] == 1)
@constraint(model, [h=1:5], (1-pets[h, p["fox"]]) + get(smokes,(h-1, s["chesterfields"]), 0) + get(smokes, (h+1, s["chesterfields"]), 0) >= 1)
@constraint(model, [h=1:5], (1-pets[h, p["horse"]]) + get(smokes,(h-1, s["kools"]), 0) + get(smokes, (h+1, s["kools"]), 0) >= 1)
@constraint(model, [h=1:5], drinks[h, d["orangejuice"]] == smokes[h, s["luckystrikes"]])
@constraint(model, [h=1:5], nations[h, n["japanese"]] == smokes[h, s["parliaments"]])
@constraint(model, [h=1:5], (1-nations[h, n["norwegian"]]) + get(colors, (h-1, c["blue"]), 0) + get(colors, (h+1, c["blue"]), 0) >= 1)
optimize!(model)
if termination_status(model) == MOI.OPTIMAL && primal_status(model) == MOI.FEASIBLE_POINT
m = map(1:5) do h
[Dict(values(c) .=> keys(c))[findfirst(value.(colors)[h, :] .≈ 1.0)],
Dict(values(n) .=> keys(n))[findfirst(value.(nations)[h, :] .≈ 1.0)],
Dict(values(p) .=> keys(p))[findfirst(value.(pets)[h, :] .≈ 1.0)],
Dict(values(d) .=> keys(d))[findfirst(value.(drinks)[h, :] .≈ 1.0)],
Dict(values(s) .=> keys(s))[findfirst(value.(smokes)[h, :] .≈ 1.0)]]
end
end
using DataFrames
DataFrame(colors=getindex.(m, 1),
nations=getindex.(m, 2),
pets=getindex.(m, 3),
drinks=getindex.(m, 4),
smokes=getindex.(m, 5))
</syntaxhighlight>
{{out}}
<pre>
: 5×5 DataFrame
: │ Row │ colors │ nations │ pets │ drinks │ smokes │
: ├─────┼──────────┼───────────┼──────────┼─────────────┼───────────────┤
: │ 1 │ yellow │ norwegian │ fox │ water │ kools │
: │ 2 │ blue │ ukrainian │ horse │ tea │ chesterfields │
: │ 3 │ red │ english │ snails │ milk │ winstons │
: │ 4 │ ivory │ spanish │ dog │ orangejuice │ luckystrikes │
: │ 5 │ green │ japanese │ zebra │ coffee │ parliaments │
</pre>
=={{header|Kotlin}}==
<
fun nextPerm(perm: IntArray): Boolean {
Line 4,342 ⟶ 4,423:
val plural = if (solutions == 1) "" else "s"
println("$solutions solution$plural found")
}</
{{out}}
Line 4,362 ⟶ 4,443:
The Logtalk distribution includes a solution for a variant of this puzzle (here reproduced with permission):
<
/* Houses logical puzzle: who owns the zebra and who drinks water?
Line 4,439 ⟶ 4,520:
:- end_object.
</syntaxhighlight>
Sample query:
<
| ?- houses::(houses(S), print(S)).
h(norwegian,fox,kool,water,yellow)
Line 4,451 ⟶ 4,532:
S = [h(norwegian,fox,kool,water,yellow),h(ukrainian,horse,chesterfield,tea,blue),h(english,snake,winston,milk,red),h(japonese,zebra,kent,coffee,green),h(spanish,dog,lucky,juice,white)]
</syntaxhighlight>
=={{header|Mathematica}}/{{header|Wolfram Language}}==
This creates a table that has 5 columns, and 25 rows. We fill the table; each column is the same and equal to all the options joined together in blocks of 5:
<pre> 1 2 3 4 5
Line 4,483 ⟶ 4,564:
This should be read as follows: Each column shows (in blocks of 5) the possible candidates of each kind (beverage, animal, smoke...)
We solve it now in a 'sudoku' way: We remove candidates iteratively until we are left with 1 candidate of each kind for each house.
<
EliminatePoss[ct_, key1_, key2_] := Module[{t = ct, poss1, poss2, poss, notposs},
poss1 = Position[t, key1];
Line 4,596 ⟶ 4,677:
bigtable = FixedPoint[FilterPuzzle, bigtable];
TableForm[DeleteCases[bigtable\[Transpose], Null, \[Infinity]], TableHeadings -> {Range[5], None}]</
Using the command FixedPoint, we iteratively filter out these candidates, until we are (hopefully) left with 1 candidate per kind per house.
{{out}}
Line 4,604 ⟶ 4,685:
4 Green German Coffee Zebra Prince
5 White Swede Beer Dog Blue Master</pre>
=={{header|Mercury}}==
<syntaxhighlight lang="mercury">:- module zebra.
:- interface.
:- import_module io.
:- pred main(io, io).
:- mode main(di, uo) is cc_multi. % or det for all-solutions
:- implementation.
:- import_module list.
:- import_module solutions.
% perm
:- pred my_perm(list(T), list(T)).
:- mode my_perm(in, out) is multi.
my_perm([], []).
my_perm([X | Xs], Perm) :-
my_perm(Xs, PermXs),
my_insert(X, PermXs, Perm).
:- pred my_insert(T, list(T), list(T)).
:- mode my_insert(in, in, out) is multi.
my_insert(X, [], [X]).
my_insert(X, [Y | Ys], Zs) :-
(
Zs = [X, Y | Ys]
;
my_insert(X, Ys, Zs0),
Zs = [Y | Zs0]
).
% The puzzle
:- type person
---> english
; spanish
; ukrainian
; norwegian
; japanese.
:- pred left_of(list(T), T, T).
:- mode left_of(in, in, in) is semidet.
left_of([A, B | _], A, B).
left_of([_ | List], A, B) :- left_of(List, A, B).
:- pred next_to(list(T), T, T).
:- mode next_to(in, in, in) is semidet.
next_to(List, A, B) :-
( left_of(List, A, B)
; left_of(List, B, A)
).
:- pred puzzle({list(person), list(person), list(person), list(person),
list(person)}).
:- mode puzzle(out) is nondet.
puzzle({Houses, Colours, Pets, Drinks, Smokes}) :-
% 10. The Norwegian lives in the first house.
First = norwegian,
perm([english, spanish, ukrainian, japanese],
[Second, Third, Fourth, Fifth]),
% 2. The Englishman lives in the red house.
Red = english,
perm([spanish, ukrainian, norwegian, japanese],
[Green, Ivory, Yellow, Blue]),
% 10. The Norwegian lives in the first house.
% 15. The Norwegian lives next to the blue house.
Second = Blue,
% 6. The green house is immediately to the right of the ivory house.
left_of(Houses, Ivory, Green),
% 3. The Spaniard owns the dog.
Dog = spanish,
perm([english, ukrainian, norwegian, japanese],
[Snails, Fox, Horse, Zebra]),
% 4. Coffee is drunk in the green house.
Green = Coffee,
% 5. The Ukrainian drinks tea.
Tea = ukrainian,
% 9. Milk is drunk in the middle house.
Milk = Third,
perm([english, spanish, norwegian, japanese],
[Coffee, Milk, Juice, Water]),
% 7. The Old Gold smoker owns snails.
Snails = OldGold,
% 8. Kools are smoked in the yellow house.
Kools = Yellow,
% 13. The Lucky Strike smoker drinks orange juice.
LuckyStrike = Juice,
% 14. The Japanese smokes Parliaments.
Parliament = japanese,
perm([english, spanish, ukrainian, norwegian],
[OldGold, Kools, Chesterfield, LuckyStrike]),
% 11. The man who smokes Chesterfields lives in the house
% next to the man with the fox.
next_to(Houses, Chesterfield, Fox),
% 12. Kools are smoked in the house next to the house
% where the horse is kept.
next_to(Houses, Kools, Horse),
Houses = [First, Second, Third, Fourth, Fifth],
Colours = [Red, Green, Ivory, Yellow, Blue],
Pets = [Dog, Snails, Fox, Horse, Zebra],
Drinks = [Coffee, Tea, Milk, Juice, Water],
Smokes = [OldGold, Kools, Chesterfield, LuckyStrike, Parliament].
% Printing a solution
:- pred write_solution({list(person), list(person), list(person),
list(person), list(person)}::in, io::di, io::uo) is det.
write_solution({Houses, Colours, Pets, Drinks, Smokes}, !IO) :-
write_string("--------\n", !IO),
write_assignments(["1st", "2nd", "3rd", "4th", "5th"],
Houses, !IO),
write_assignments(["red", "green", "ivory", "yellow", "blue"],
Colours, !IO),
write_assignments(["dog", "snails", "fox", "horse", "zebra"],
Pets, !IO),
write_assignments(["coffee", "tea", "milk", "juice", "water"],
Drinks, !IO),
write_assignments(["oldgold", "kools", "chesterfield",
"luckystrike", "parliament"], Smokes, !IO).
:- pred write_assignments(list(string)::in, list(person)::in,
io::di, io::uo) is det.
write_assignments(Labels, Persons, !IO) :-
foldl_corresponding(write_assignment, Labels, Persons, !IO),
nl(!IO).
:- pred write_assignment(string::in, person::in, io::di, io::uo) is det.
write_assignment(Label, Person, !IO) :-
write_string(Label, !IO),
write_string(" - ", !IO),
write(Person, !IO),
write_string("\n", !IO).
% main
main(!IO) :-
% Print all solutions.
/*
solutions(puzzle, Solutions),
foldl(write_solution, Solutions, !IO).
*/
% Print solutions as they are found.
/*
unsorted_aggregate(puzzle, write_solution, !IO).
*/
% Print one solution.
( if puzzle(Solution) then
write_solution(Solution, !IO)
else
write_string("No solution found.\n", !IO)
).
</syntaxhighlight>
{{out}}
<pre>--------
1st - norwegian
2nd - ukrainian
3rd - english
4th - spanish
5th - japanese
red - english
green - japanese
ivory - spanish
yellow - norwegian
blue - ukrainian
dog - spanish
snails - english
fox - norwegian
horse - ukrainian
zebra - japanese
coffee - japanese
tea - ukrainian
milk - english
juice - spanish
water - norwegian
oldgold - english
kools - norwegian
chesterfield - ukrainian
luckystrike - spanish
parliament - japanese</pre>
=={{header|MiniZinc}}==
<syntaxhighlight lang="minizinc">
%Solve Zebra Puzzle. Nigel Galloway, August 27th., 2019
include "alldifferent.mzn";
enum N={English,Swedish,Danish,German,Norwegian};
enum I={Tea,Coffee,Milk,Beer,Water};
enum G={Dog,Birds,Cats,Horse,Zebra};
enum E={Red,Green,White,Blue,Yellow};
enum L={PallMall,Dunhill,BlueMaster,Prince,Blend};
array[1..5] of var N: Nz; constraint alldifferent(Nz); constraint Nz[1]=Norwegian; %The Norwegian lives in the first house.
array[1..5] of var I: Iz; constraint alldifferent(Iz); constraint Iz[3]=Milk; %In the middle house they drink milk.
array[1..5] of var G: Gz; constraint alldifferent(Gz);
array[1..5] of var E: Ez; constraint alldifferent(Ez);
array[1..5] of var L: Lz; constraint alldifferent(Lz);
constraint exists(n in 1..5)(Nz[n]=English /\ Ez[n]=Red); %The English man lives in the red house
constraint exists(n in 1..5)(Nz[n]=Swedish /\ Gz[n]=Dog); %The Swede has a dog.
constraint exists(n in 1..5)(Nz[n]=Danish /\ Iz[n]=Tea); %The Dane drinks tea.
constraint exists(n in 1..4)(Ez[n]=Green /\ Ez[n+1]=White); %The green house is immediately to the left of the white house.
constraint exists(n in 1..5)(Ez[n]=Green /\ Iz[n]=Coffee); %They drink coffee in the green house.
constraint exists(n in 1..5)(Lz[n]=PallMall /\ Gz[n]=Birds); %The man who smokes Pall Mall has birds
constraint exists(n in 1..5)(Ez[n]=Yellow /\ Lz[n]=Dunhill); %In the yellow house they smoke Dunhill.
constraint exists(n in 1..4)((Lz[n]=Blend /\ Gz[n+1]=Cats) \/ (Lz[n+1]=Blend /\ Gz[n]=Cats)); %The man who smokes Blend lives in the house next to the house with cats.
constraint exists(n in 1..4)((Gz[n]=Horse /\ Lz[n+1]=Dunhill) \/ (Gz[n+1]=Horse /\ Lz[n]=Dunhill)); %In a house next to the house where they have a horse, they smoke Dunhill.
constraint exists(n in 1..5)(Lz[n]=BlueMaster /\ Iz[n]=Beer); %The man who smokes Blue Master drinks beer.
constraint exists(n in 1..5)(Nz[n]=German /\ Lz[n]=Prince); %The German smokes Prince.
constraint exists(n in 1..4)((Nz[n]=Norwegian /\ Ez[n+1]=Blue) \/ (Nz[n+1]=Norwegian /\ Ez[n]=Blue));%The Norwegian lives next to the blue house.
constraint exists(n in 1..4)((Lz[n]=Blend /\ Iz[n+1]=Water) \/ (Lz[n+1]=Blend /\ Iz[n]=Water)); %They drink water in a house next to the house where they smoke Blend.
var 1..5: n;
constraint Gz[n]=Zebra;
solve satisfy;
output ["The "++show(Nz[n])++" owns the zebra"++"\n\n"++show(Nz)++"\n"++show(Iz)++"\n"++show(Gz)++"\n"++show(Ez)++"\n"++show(Lz)++"\n"];
</syntaxhighlight>
{{out}}
<pre>
The German owns the zebra
[Norwegian, Danish, English, German, Swedish]
[Water, Tea, Milk, Coffee, Beer]
[Cats, Horse, Birds, Zebra, Dog]
[Yellow, Blue, Red, Green, White]
[Dunhill, Blend, PallMall, Prince, BlueMaster]
----------
</pre>
=={{header|Nial}}==
Line 4,612 ⟶ 4,949:
be pasted into the REPL.
<syntaxhighlight lang="nial">
remove is op x xs {filter (not (x =)) xs}
Line 4,668 ⟶ 5,005:
abs(time - (run; time))
</syntaxhighlight>
{{out}}
Line 4,685 ⟶ 5,022:
0.03
</pre>
=={{header|Nim}}==
Using the same order for test of criteria as in Kotlin solution.
<syntaxhighlight lang="nim">import algorithm, strformat, sequtils
type
Color {.pure.} = enum Blue, Green, Red, White, Yellow
Person {.pure.} = enum Dane, English, German, Norwegian, Swede
Pet {.pure.} = enum Birds, Cats, Dog, Horse, Zebra
Drink {.pure.} = enum Beer, Coffee, Milk, Tea, Water
Cigarettes {.pure.} = enum Blend, BlueMaster = "Blue Master",
Dunhill, PallMall = "Pall Mall", Prince
House = tuple
color: Color
person: Person
pet: Pet
drink: Drink
cigarettes: Cigarettes
Houses = array[5, House]
iterator permutations[T](): array[5, T] =
## Yield the successive permutations of values of type T.
var term = [T(0), T(1), T(2), T(3), T(4)]
yield term
while term.nextPermutation():
yield term
proc findSolutions(): seq[Houses] =
## Return all the solutions.
for colors in permutations[Color]():
if colors.find(White) != colors.find(Green) + 1: continue # 5
for persons in permutations[Person]():
if persons[0] != Norwegian: continue # 10
if colors.find(Red) != persons.find(English): continue # 2
if abs(persons.find(Norwegian) - colors.find(Blue)) != 1: continue # 15
for pets in permutations[Pet]():
if persons.find(Swede) != pets.find(Dog): continue # 3
for drinks in permutations[Drink]():
if drinks[2] != Milk: continue # 9
if persons.find(Dane) != drinks.find(Tea): continue # 4
if colors.find(Green) != drinks.find(Coffee): continue # 6
for cigarettes in permutations[Cigarettes]():
if cigarettes.find(PallMall) != pets.find(Birds): continue # 7
if cigarettes.find(Dunhill) != colors.find(Yellow): continue # 8
if cigarettes.find(BlueMaster) != drinks.find(Beer): continue # 13
if cigarettes.find(Prince) != persons.find(German): continue # 14
if abs(cigarettes.find(Blend) - pets.find(Cats)) != 1: continue # 11
if abs(cigarettes.find(Dunhill) - pets.find(Horse)) != 1: continue # 12
if abs(cigarettes.find(Blend) - drinks.find(Water)) != 1: continue # 16
var houses: Houses
for i in 0..4:
houses[i] = (colors[i], persons[i], pets[i], drinks[i], cigarettes[i])
result.add houses
let solutions = findSolutions()
echo "Number of solutions: ", solutions.len
let sol = solutions[0]
echo()
echo "Number Color Person Pet Drink Cigarettes"
echo "—————— —————— ————————— ————— —————— ———————————"
for i in 0..4:
echo &"{i + 1:3} {sol[i].color:6} {sol[i].person:9} ",
&"{sol[i].pet:5} {sol[i].drink:6} {sol[i].cigarettes: 11}"
let owner = sol.filterIt(it.pet == Zebra)[0].person
echo &"\nThe {owner} owns the zebra."</syntaxhighlight>
{{out}}
<pre>Number of solutions: 1
Number Color Person Pet Drink Cigarettes
—————— —————— ————————— ————— —————— ———————————
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
The German owns the zebra.</pre>
=={{header|PARI/GP}}==
<syntaxhighlight lang="none">
perm(arr) = {
n=#arr;i=n-1;
Line 4,707 ⟶ 5,133:
adj(x,xs,y,ys)={
abs(select(z->z==x,xs,1)[1] - select(z->z==y,ys,1)[1])==1;
}
eq(x,xs,y,ys)={
select(z->z==x,xs,1) == select(z->z==y,ys,1);
}
Line 4,738 ⟶ 5,164:
for(i=1,5,printf("House:%s %6s %10s %10s %10s %10s\n",i,colors[c][i],nations[n][i],pets[p][i],drinks[d][i],smokes[s][i]));\
)))))))));
</syntaxhighlight>
{{out}}
Line 4,754 ⟶ 5,180:
=={{header|Perl}}==
Basically the same idea as C, though of course it's much easier to have Perl generate Perl code.
<
use utf8;
Line 4,857 ⟶ 5,283:
pair qw( water blend -1 1 );
$solve->();</
Incidentally, the same logic can be used to solve the dwelling problem, if somewhat awkwardly:
<
# property names and values
setprops
Line 4,880 ⟶ 5,306:
pair qw(cooper fletcher 4 3 2 -2 -3 -4);
$solve->();</
=={{header|Phix}}==
<!--(phixonline)-->
<syntaxhighlight lang="phix">
--enum colour, nationality, drink, smoke, pet -- (now implicit)
enum red,white,green,yellow,blue
enum English,Swede,Dane,Norwegian,German
enum tea,coffee,milk,beer,water
enum PallMall,Dunhill,Blend,BlueMaster,Prince
enum dog,birds,cats,horse,zebra
constant
nationalities = {"English","Swede","Dane","Norwegian","German"},
drinks = {"tea","coffee","milk","beer","water"},
smokes = {"Pall Mall","Dunhill","Blend","Blue Master","Prince"},
pets = {"dog","birds","cats","horse","zebra"},
sets = {colours,nationalities,drinks,smokes,pets}
constant p5 = permutes(tagset(5)), -- all permutes of {1,2,3,4,5},
lp = length(p5) -- (== factorial(5), ie 120)
// In the following, c1,c2 are indexes to p5, for colour..pet,
// and v1,v2 are from their corresponding enums, so eg p5[c1]
// might be {1,4,3,2,5} for the colours of 1..5 and finding
// v1 in that gives us a house number. Checking the specified
// condition, eg [h] == green && [h+1] == white is then easy.
function
return h<=4 and p5[c2][h+1]=v2
end function
function
return p5[c2][h]=v2
end function
function next_to(integer
integer h1 = find(v1,p5[c1]),
h2 = find(v2,p5[c2])
return abs(h1-h2)=1
end function
procedure print_house(integer
sequence args = {n}
for i,p in perm do
args =
end for
printf(1,"House %d: %|7s %|10s %|6s %|12s %=6s\n",args)
end procedure
integer
atom t0 = time()
for colour=1 to lp do
if left_of(colour,green,colour,white) then
for nationality=1 to lp do
if p5[nationality][1]=Norwegian -- Norwegian lives in 1st house
and same_house(nationality,English,colour,red)
if same_house(nationality,Dane,drink,tea)
and
if
and
and
if
and
and
and next_to(
for i=1 to 5 do
print_house(i,{colour,nationality,drink,smoke,pet})
end for
ns += 1
end if
end for
Line 5,054 ⟶ 5,396:
end if
end for
printf(1,"%d solution%s found (%3.3fs).\n",{
</syntaxhighlight>
{{out}}
<pre>
House 1: yellow
House 2: blue
House 3: red
House 4: green
House 5: white
The German owns the Zebra
1 solution found (0.000s).
</pre>
=={{header|Picat}}==
<syntaxhighlight lang="picat">import cp.
main =>
Nat = [English, Swede, Dane, German, Norwegian],
Color = [Red, Green, White, Yellow, Blue],
Smoke = [PallMall, Dunhill, Blend, SBlue, Prince],
Pet = [Dog, Bird, Cat, Horse, Zebra],
Drink = [Tea, Coffee, Milk, Beer, Water],
Nat :: 1..5,
Color :: 1..5,
Smoke :: 1..5,
Pet :: 1..5,
Drink :: 1..5,
all_different(Nat),
all_different(Color),
all_different(Smoke),
all_different(Pet),
all_different(Drink),
English = Red,
Swede = Dog,
Dane = Tea,
Green #= White-1,
Coffee = Green,
Bird = PallMall,
Yellow = Dunhill,
Milk = 3,
Norwegian = 1,
abs(Blend-Cat) #= 1,
abs(Dunhill-Horse) #= 1,
SBlue = Beer,
German = Prince,
abs(Norwegian-Blue) #= 1,
abs(Blend-Water) #= 1,
solve(Nat ++ Color ++ Smoke ++ Pet ++ Drink),
L = [English=english,
Swede=swede,
Dane=dane,
German=german,
Norwegian=norwegian].sort(),
member(Zebra=ZebraOwner, L),
writef("The %w owns the zebra\n", ZebraOwner),
writeln(L).
</syntaxhighlight>
{{out}}
<pre>
The german owns the zebra
[1 = norwegian,2 = dane,3 = english,4 = german,5 = swede]
</pre>
=={{header|PicoLisp}}==
<
(permute (red blue green yellow white) @House)
(left-of @House white @House green)
Line 5,111 ⟶ 5,505:
(be next-to (@X @A @Y @B) (right-of @X @A @Y @B))
(be next-to (@X @A @Y @B) (left-of @X @A @Y @B))</
Test:
<
(let Fmt (-8 -11 -8 -7 -11)
(tab Fmt "HOUSE" "PERSON" "DRINKS" "HAS" "SMOKES")
(mapc '(@ (pass tab Fmt))
@House @Person @Drink @Pet @Cigarettes ) ) )</
Output:
<pre>HOUSE PERSON DRINKS HAS SMOKES
Line 5,130 ⟶ 5,524:
In Prolog we can specify the domain by selecting elements from it, making mutually exclusive choices for efficiency:
<
select([],_).
Line 5,150 ⟶ 5,544:
:- ?- time(( zebra(Who, HS), maplist(writeln,HS), nl, write(Who), nl, nl, fail
; write('No more solutions.') )).</
Output:
Line 5,173 ⟶ 5,567:
Using extensible records, letting the houses' attributes be discovered from rules, ''not'' predetermined by a programmer (as any ''"a house has five attributes"'' solution is doing).
<
attrs( H, [N-V | R]) :- !, memberchk( N-X, H), X = V, (R = [], ! ; attrs( H, R)).
attrs( HS, AttrsL) :- maplist( attrs, HS, AttrsL).
Line 5,202 ⟶ 5,596:
, [[drink -water ], [smoke-'Blend' ]] % 16
] ),
in( Houses, [owns-zebra, nation-Owner]).</
[http://ideone.com/wcwXfZ Output]:
<
maplist(writeln,S),nl,writeln(Z)), false ; writeln('No More Solutions'))).
Line 5,216 ⟶ 5,610:
german
No More Solutions
% 263,486 inferences, 0.047 CPU in 0.063 seconds (74% CPU, 5630007 Lips)</
===Alternative version===
{{Works with|GNU Prolog}}
{{Works with|SWI Prolog}}
<
Line 5,266 ⟶ 5,660:
main :- findall(_, (zebra(_), nl), _), halt.
</syntaxhighlight>
{{Output}}
<pre>h(yellow,nvg,cats,water,dh)
Line 5,280 ⟶ 5,674:
{{Works with|SWI Prolog}}
Original source code is 'ECLiPSe ( http://eclipseclp.org/ )' example: http://eclipseclp.org/examples/zebra.ecl.txt
<
zebra :-
Line 5,334 ⟶ 5,728:
format(Fmt, PetNames),
format(Fmt, DrinkNames).
</syntaxhighlight>
{{Output}}
<pre>
Line 5,347 ⟶ 5,741:
{{trans|Clojure}}
Using 'logpy': https://github.com/logpy/logpy
<
from logpy import *
from logpy.core import lall
Line 5,421 ⟶ 5,815:
for line in solutions[0]:
print str(line)
</syntaxhighlight>
===Alternative Version===
{{trans|D}}
<
class Content: elems= """Beer Coffee Milk Tea Water
Line 5,525 ⟶ 5,919:
solve(M, Test.Drink, 5)
main()</
{{out}}
<pre> One: Water Norwegian Yellow Dunhill Cat
Line 5,534 ⟶ 5,928:
Runtime about 0.18 seconds.
===Alternative Version===
<
class Number:elems= "One Two Three Four Five".split()
Line 5,584 ⟶ 5,978:
print
main()</
Output:
<pre>Found a solution:
Line 5,597 ⟶ 5,991:
Using 'python-constraint': http://labix.org/python-constraint,
Original source code is 'ECLiPSe ( http://eclipseclp.org/ )' example: http://eclipseclp.org/examples/zebra.ecl.txt
<syntaxhighlight lang
Improved version: Instead of simple variables (a, b),
more intelligible and readable (?) variables are employed.
'''
def doc1():
'''
There are five houses.
The English man lives in the red house.
The Swede has a dog.
The Dane drinks tea.
The green house is immediately to the left of the white house.
They drink coffee in the green house.
The man who smokes Pall Mall has a bird.
In the yellow house they smoke Dunhill.
In the middle house they drink milk.
The Norwegian lives in the first house.
The man who smokes Blend lives in the house next to the house with a cat.
In a house next to the house where they have a horse, they smoke Dunhill.
The man who smokes Blue Master drinks beer.
The German smokes Prince.
The Norwegian lives next to the blue house.
They drink water in a house next to the house where they smoke Blend.
The solution:
Nation: Norwegian Dane
Color:
Smoke: Dunhill Blend PallMall Prince BlueMaster
Drink:
'''
import os
print(os.system('cls') if os.name == 'nt' else os.system('clear'))
print(doc1.__doc__)
input('<key>')
from constraint import *
p = Problem()
Nation = ['Englishman', 'Dane', 'German', 'Norwegian', 'Swede']
Color = [ 'Blue', 'Green', 'Red', 'White', 'Yellow']
Smoke = [ 'Blend', 'BlueMaster', 'Dunhill', 'PallMall', 'Prince']
Pet = [ 'Bird', 'Cat', 'Dog', 'Horse', 'Zebra']
Drink = [ 'Beer', 'Coffee', 'Milk', 'Tea', 'Water']
# add variables: house numbers 1 to 5
# add constraint: the values in each list are exclusive
# add constraint: actual constraints
# The English man lives in the red house.
p.addConstraint(
lambda house_englishman, red:
house_englishman is red,
['Englishman', 'Red'])
# The Swede has a dog.
p.addConstraint(
lambda pet_swede, dog:
['Swede', 'Dog'])
# The Dane drinks tea.
p.addConstraint(
lambda drink_dane, tea:
drink_dane is tea,
['Dane', 'Tea'])
# The green house is immediately to the left of the white house.
p.addConstraint(
lambda green_house, white_house:
# Houses 1 .. 5 -> green house is 1 lower than white house
green_house is white_house - 1,
['Green', 'White'])
# They drink coffee in the green house.
p.addConstraint(
lambda drink_green_house, coffee:
drink_green_house is coffee,
['Green', 'Coffee'])
# The man who smokes Pall Mall has a bird.
p.addConstraint(
lambda pet_of_pallmall_smoker, a_bird:
pet_of_pallmall_smoker is a_bird,
['PallMall', 'Bird'])
# In the yellow house they smoke Dunhill.
p.addConstraint(
lambda owner_yellow_house, dunhill_smoker:
owner_yellow_house is dunhill_smoker,
['Yellow', 'Dunhill'])
# In the middle house they drink milk.
p.addConstraint(
lambda house_number_milk_drinker:
house_number_milk_drinker is 3,
['Milk'])
# The Norwegian lives in the first house.
p.addConstraint(
lambda house_number_norwegian:
house_number_norwegian is 1,
['Norwegian'])
# The man who smokes Blend lives in the house next to the house with a cat.
p.addConstraint(
lambda house_number_blend_smoker, number_of_house_with_cat:
# next -> housenumber +/- 1
house_number_blend_smoker is number_of_house_with_cat + 1 or
house_number_blend_smoker is number_of_house_with_cat - 1,
['Blend', 'Cat'])
# In a house next to the house where they have a horse, they smoke Dunhill.
p.addConstraint(
lambda house_number_dunhill_smoker, number_of_house_with_horse:
# next -> housenumber +/- 1
house_number_dunhill_smoker is number_of_house_with_horse + 1 or
house_number_dunhill_smoker is number_of_house_with_horse - 1,
['Dunhill', 'Horse'])
# The man who smokes Blue Master drinks beer.
p.addConstraint(
lambda drink_bluemaster_smoker, beer:
drink_bluemaster_smoker is beer,
['BlueMaster', 'Beer'])
# The German smokes Prince.
p.addConstraint(
lambda prince_smoker, german:
prince_smoker is german,
['Prince', 'German'])
# The Norwegian lives next to the blue house.
p.addConstraint(
lambda house_number_norwegian, house_number_blue_house:
house_number_norwegian is house_number_blue_house + 1 or
house_number_norwegian is house_number_blue_house - 1,
['Norwegian', 'Blue'])
# They drink water in a house next to the house where they smoke Blend.
p.addConstraint(
lambda house_number_water_drinker, house_number_blend_smoker:
house_number_water_drinker is house_number_blend_smoker + 1 or
house_number_water_drinker is house_number_blend_smoker - 1,
['Water', 'Blend'])
# get solution
sol =
# print the answers
nation = [
color = [
smoke = [
pet = [
drink = [
for n in Nation: nation[sol[n]] = n
for n in Color: color[sol[n]] = n
for n in
for n in
for n in
# put the answers in the correct order of solution
print('\n\n', 'The calculated solution:', '\n')
for
print(f'{r[0]:>13s}: ', end='')
for i in range(1, 6):
print(f'{r[i]:>14s}',end='')
print()
print()
</syntaxhighlight>
Output:
<pre>
</pre>
=={{header|R}}==
{{libheader|combinat}}<
library(combinat)
Line 5,748 ⟶ 6,267:
}
}</
{{out}}
<pre>
Line 5,763 ⟶ 6,282:
{{trans|Prolog}}
<
(require racklog)
Line 5,819 ⟶ 6,338:
(%member (list (_) Owns 'zebra (_) (_)) HS)]))
(%which (Who HS) (%zebra Who HS))</
Output:
Line 5,831 ⟶ 6,350:
(white swede dog beer bluemaster)))
</pre>
=={{header|Raku}}==
(formerly Perl 6)
A rule driven approach:
<syntaxhighlight lang="raku" line>my Hash @houses = (1 .. 5).map: { %(:num($_)) }; # 1 there are five houses
my @facts = (
{ :nat<English>, :color<red> }, # 2 The English man lives in the red house.
{ :nat<Swede>, :pet<dog> }, # 3 The Swede has a dog.
{ :nat<Dane>, :drink<tea> }, # 4 The Dane drinks tea.
{ :color<green>, :Left-Of(:color<white>) }, # 5 the green house is immediately to the left of the white house
{ :drink<coffee>, :color<green> }, # 6 They drink coffee in the green house.
{ :smoke<Pall-Mall>, :pet<birds> }, # 7 The man who smokes Pall Mall has birds.
{ :color<yellow>, :smoke<Dunhill> }, # 8 In the yellow house they smoke Dunhill.
{ :num(3), :drink<milk> }, # 9 In the middle house they drink milk.
{ :num(1), :nat<Norwegian> }, # 10 The Norwegian lives in the first house.
{ :smoke<Blend>, :Next-To(:pet<cats>) }, # 11 The man who smokes Blend lives in the house next to the house with cats.
{ :pet<horse>, :Next-To(:smoke<Dunhill>) }, # 12 In a house next to the house where they have a horse, they smoke Dunhill.
{ :smoke<Blue-Master>, :drink<beer> }, # 13 The man who smokes Blue Master drinks beer.
{ :nat<German>, :smoke<Prince> }, # 14 The German smokes Prince.
{ :nat<Norwegian>, :Next-To(:color<blue>) }, # 15 The Norwegian lives next to the blue house.
{ :drink<water>, :Next-To(:smoke<Blend>) }, # 16 They drink water in a house next to the house where they smoke Blend.
{ :pet<zebra> }, # who owns this?
);
sub MAIN {
for gather solve(@houses, @facts) {
#-- output
say .head.sort.map(*.key.uc.fmt("%-9s")).join(' | ');
say .sort.map(*.value.fmt("%-9s")).join(' | ')
for .list;
last; # stop after first solution
}
}
#| a solution has been found that fits all the facts
multi sub solve(@solution, @facts [ ]) {
take @solution;
}
#| extend this scenario to fit the next fact
multi sub solve(@scenario, [ $fact, *@facts ]) {
for gather match(@scenario, |$fact) -> @houses {
solve(@houses, @facts)
}
}
#| find all possible solutions for pairs of houses with
#| properties %b, left of a house with properties %a
multi sub match(@houses, :Left-Of(%a)!, *%b) {
for 1 ..^ @houses {
my %left-house := @houses[$_-1];
my %right-house := @houses[$_];
if plausible(%left-house, %a) && plausible(%right-house, %b) {
temp %left-house ,= %a;
temp %right-house ,= %b;
take @houses;
}
}
}
#| match these houses are next to each other (left or right)
multi sub match(@houses, :Next-To(%b)!, *%a ) {
match(@houses, |%a, :Left-Of(%b) );
match(@houses, |%b, :Left-Of(%a) );
}
#| find all possible houses that match the given properties
multi sub match(@houses, *%props) {
for @houses.grep({plausible($_, %props)}) -> %house {
temp %house ,= %props;
take @houses;
}
}
#| plausible if doesn't conflict with anything
sub plausible(%house, %props) {
! %props.first: {%house{.key} && %house{.key} ne .value };
}
</syntaxhighlight>
{{out}}
<pre>
COLOR | DRINK | NAT | NUM | PET | SMOKE
yellow | water | Norwegian | 1 | cats | Dunhill
blue | tea | Dane | 2 | horse | Blend
red | milk | English | 3 | birds | Pall-Mall
green | coffee | German | 4 | zebra | Prince
white | beer | Swede | 5 | dog | Blue-Master
</pre>
Note: Facts can be shuffled by changing line 3 to <code>my @facts = pick *, (</code>. It seems to reliably find solutions, although execution times will vary (from under 1 sec up to about 10sec).
=={{header|REXX}}==
{{trans|BBC BASIC}}
Permutations algorithm taken from REXX
<
* Solve the Zebra Puzzle
*--------------------------------------------------------------------*/
Line 6,003 ⟶ 6,614:
out:
Say arg(1)
Return</
{{out}}
<pre>House Drink Nation Colour Smoke Animal
Line 6,015 ⟶ 6,626:
=={{header|Ruby}}==
<
Nationality: %i[English Swedish Danish Norwegian German],
Colour: %i[Red Green White Blue Yellow],
Line 6,068 ⟶ 6,679:
end
solve_zebra_puzzle</
{{out}}
Line 6,084 ⟶ 6,695:
===Another approach===
<
class String; def brk; split(/(?=[A-Z])/); end; end
men,drinks,colors,pets,smokes = "NorwegianGermanDaneSwedeEnglish
Line 6,109 ⟶ 6,720:
puts "The #{x.find{|y|y[0]=="Zebra"}[1]} owns the zebra.",
x.map{|y| y.map{|z| z.ljust(11)}.join}}}}}}
</syntaxhighlight>
Output:
<pre>
Line 6,122 ⟶ 6,733:
=={{header|Scala}}==
===Idiomatic (for comprehension)===
<
*
* It can further concluded that:
Line 6,148 ⟶ 6,759:
} yield new House(nationality, color, beverage, animal, brand)
val members = for { // Neighborhood clues
h1 <- housesLeftOver().filter(p => (p.nationality == "
h3 <- housesLeftOver(h1).filter(p => p.beverage == "Milk") // #9 // 24
h2 <- housesLeftOver(h1, h3).filter(_.color == "Blue") // #15
Line 6,199 ⟶ 6,810:
members.foreach(solution => solution.zipWithIndex.foreach(h => println(s"House ${h._2 + 1} ${h._1}")))
}
} // loc 58</
{{Out}}See it in running in your browser by [https://scalafiddle.io/sf/h5Y98te/0 ScalaFiddle (JavaScript executed in browser)] or by [https://scastie.scala-lang.org/fJZRog4xQ9aAV4D3crM1gQ Scastie (remote JVM)].{{out}}
<pre> The German is the owner of the zebra.
Line 6,209 ⟶ 6,820:
House 5 German, Green, Coffee, Zebra, Prince.
</pre>
===Scala Alternate Version (Over-engineered)===
<
object Einstein extends App {
Line 6,293 ⟶ 6,905:
}
}// loc 38</
{{Out}}Experience running it in your browser by [https://scalafiddle.io/sf/hJgtjYG/1 ScalaFiddle (JavaScript executed in browser)] or by [https://scastie.scala-lang.org/ajeuRgDSQKyVv4Jd6SPfVQ Scastie (remote JVM)].
{{out}}
Line 6,308 ⟶ 6,920:
=={{header|Sidef}}==
{{trans|Ruby}}
<
:House => nil,
:Nationality => [:English, :Swedish, :Danish, :Norwegian, :German],
Line 6,359 ⟶ 6,971:
say "The Zebra is owned by the man who is #{res[0][res[2].first_index(:Zebra)]}\n"
say (fmt % keys..., "\n", fmt % width.map{|w| "-"*w }...)
res[0].indices.map{|i| res.map{|a| a[i] }}.each_kv {|k,v| say fmt%(k,v...) }</
{{out}}
<pre>
Line 6,376 ⟶ 6,988:
{{works with|SML/NJ}}
{{trans|C++}}(This implementation uses the search algorithm of the C++ implementation, but the rules check algorithm is different.)
<
(* Attributes and values *)
val str_attributes = Vector.fromList ["Color", "Nation", "Drink", "Pet", "Smoke"]
Line 6,626 ⟶ 7,238:
else print "No solution found!\n"
end
</syntaxhighlight>
{{out}}
Line 6,638 ⟶ 7,250:
4 White Swede Beer Dog BlueMaster
val it = () : unit
</pre>
=={{header|Tailspin}}==
===General solver with relational algebra===
A general solver for this type of puzzle, using relational algebra. This solver can also be used for "Dinesman's multiple-dwelling problem"
<syntaxhighlight lang="tailspin">
processor EinsteinSolver
@: [{|{}|}]; // A list of possible relations, start with one relation with an empty tuple
$ -> \(
when <[](1..)> do
def variableRange: $(1);
@EinsteinSolver: [($@EinsteinSolver(1) join {|{by $variableRange...}|})];
$(2..last) -> #
\) -> !VOID
sink isFact
def fact: $;
def parts: [$... -> {$}];
@EinsteinSolver: [$@EinsteinSolver... -> \(
def new: ($ matching {|$fact|});
@: $;
$parts... -> @: ($@ notMatching {| $ |});
($new union $@) !
\)];
end isFact
operator (a nextTo&{byField:, bMinusA:} b)
data ES_temp__ <"1"> local
@EinsteinSolver: [$@EinsteinSolver... -> \(
def in: $;
def temp: {| $... -> {$, ES_temp__: ($(byField)::raw)"1"} |};
def numbers: [$temp({ES_temp__:})... -> $.ES_temp__];
$numbers... -> \(
def aNumber: $;
def bNumbers: [$bMinusA... -> ($ + $aNumber)"1"];
def new: ($temp matching {| {$a, ES_temp__: $aNumber} |});
@: ($new union (($temp notMatching {| $a |}) notMatching {| {ES_temp__: $aNumber} |}));
$numbers... -> \(<~ ?($bNumbers <[<=$>]>)> $! \) -> @: ($@ notMatching {| {$b, ES_temp__: $} |});
($in matching $@) !
\) !
\)];
end nextTo
source solutions&{required:}
templates resolve&{rows:}
when <?($rows <=1>)?($::count <=1>)> do $ !
when <?($::count <$rows..>)> do
def in: $;
def selected: [$...] -> $(1);
($in minus {|$selected|}) -> resolve&{rows: $rows} ! // Alternative solutions
@: $;
$selected... -> {$} -> @: ($@ notMatching {| $ |});
[$@ -> resolve&{rows: $rows-1}] -> \(
when <~=[]> do
$... -> {| $..., $selected |} !
\) !
end resolve
[$@EinsteinSolver... -> resolve&{rows: $required}] !
end solutions
end EinsteinSolver
def numbers: [1..5 -> (no: $)];
def nationalities: [['Englishman', 'Swede', 'Dane', 'Norwegian', 'German']... -> (nationality:$)];
def colours: [['red', 'green', 'white', 'yellow', 'blue']... -> (colour:$)];
def pets: [['dog', 'birds', 'cats', 'horse', 'zebra']... -> (pet:$)];
def drinks: [['tea', 'coffee', 'milk', 'beer', 'water']... -> (drink:$)];
def smokes: [['Pall Mall', 'Dunhill', 'Blend', 'Blue Master', 'Prince']... -> (smoke: $)];
def solutions: [$numbers, $nationalities, $colours, $pets, $drinks, $smokes] -> \(
def solver: $ -> EinsteinSolver;
{nationality: 'Englishman', colour: 'red'} -> !solver::isFact
{nationality: 'Swede', pet: 'dog'} -> !solver::isFact
{nationality: 'Dane', drink: 'tea'} -> !solver::isFact
({colour: 'green'} solver::nextTo&{byField: :(no:), bMinusA: [1]} {colour: 'white'}) -> !VOID
{drink: 'coffee', colour: 'green'} -> !solver::isFact
{smoke: 'Pall Mall', pet: 'birds'} -> !solver::isFact
{colour: 'yellow', smoke: 'Dunhill'} -> !solver::isFact
{no: 3, drink: 'milk'} -> !solver::isFact
{nationality: 'Norwegian', no: 1} -> !solver::isFact
({smoke: 'Blend'} solver::nextTo&{byField: :(no:), bMinusA: [-1, 1]} {pet: 'cats'}) -> !VOID
({smoke: 'Dunhill'} solver::nextTo&{byField: :(no:), bMinusA: [-1, 1]} {pet: 'horse'}) -> !VOID
{smoke: 'Blue Master', drink: 'beer'} -> !solver::isFact
{nationality: 'German', smoke: 'Prince'} -> !solver::isFact
({nationality: 'Norwegian'} solver::nextTo&{byField: :(no:), bMinusA: [-1, 1]} {colour: 'blue'}) -> !VOID
({drink: 'water'} solver::nextTo&{byField: :(no:), bMinusA: [-1, 1]} {smoke: 'Blend'}) -> !VOID
$solver::solutions&{required: 5}!
\);
$solutions... -> ($ matching {| {pet: 'zebra'} |}) ... -> 'The $.nationality; owns the zebra.
' -> !OUT::write
$solutions -> \[i]('Solution $i;:
$... -> '$;
';
'! \)... -> !OUT::write
'No more solutions
' -> !OUT::write
</syntaxhighlight>
{{out}}
<pre>
The German owns the zebra.
Solution 1:
{colour=green, drink=coffee, nationality=German, no=4, pet=zebra, smoke=Prince}
{colour=white, drink=beer, nationality=Swede, no=5, pet=dog, smoke=Blue Master}
{colour=blue, drink=tea, nationality=Dane, no=2, pet=horse, smoke=Blend}
{colour=yellow, drink=water, nationality=Norwegian, no=1, pet=cats, smoke=Dunhill}
{colour=red, drink=milk, nationality=Englishman, no=3, pet=birds, smoke=Pall Mall}
No more solutions
</pre>
===Manual "Norvig" solution===
{{trans|C#}}
The streaming syntax of Tailspin lends itself naturally to this solution
<syntaxhighlight lang="tailspin">
templates permutations
when <=1> do [1] !
otherwise
def n: $;
templates expand
def p: $;
1..$n -> \(def k: $;
[$p(1..$k-1)..., $n, $p($k..last)...] !\) !
end expand
$n - 1 -> permutations -> expand !
end permutations
def permutationsOf5: [5 -> permutations];
def nationalities: ['Englishman', 'Swede', 'Dane', 'Norwegian', 'German'];
def colours: ['red', 'green', 'white', 'yellow', 'blue'];
def pets: ['dog', 'birds', 'cats', 'horse', 'zebra'];
def drinks: ['tea', 'coffee', 'milk', 'beer', 'water'];
def smokes: ['Pall Mall', 'Dunhill', 'Blend', 'Blue Master', 'Prince'];
$permutationsOf5... -> $colours($) -> [$... -> {colour: $}]
-> \(<[(<{colour: <='green'>}>:<{colour: <='white'>}>)]> $! \)
-> \(def current: $;
$permutationsOf5... -> $nationalities($) -> \[i]({$current($i), nationality: $}! \) !
\)
-> \(<?($(1) <{nationality: <='Norwegian'>}>)> $! \)
-> \(<[<{nationality: <='Englishman'>, colour: <='red'>}>]> $! \)
-> \(<[(<{nationality: <='Norwegian'>}>:<{colour: <='blue'>}>)] | [(<{colour: <='blue'>}>:<{nationality: <='Norwegian'>}>)]> $! \)
-> \(def current: $;
$permutationsOf5... -> $drinks($) -> \[i]({$current($i), drink: $}! \) !
\)
-> \(<?($(3) <{drink: <='milk'>}>)> $! \)
-> \(<[<{drink: <='coffee'>, colour: <='green'>}>]> $! \)
-> \(<[<{drink: <='tea'>, nationality: <='Dane'>}>]> $! \)
-> \(def current: $;
$permutationsOf5... -> $pets($) -> \[i]({$current($i), pet: $}! \)!
\)
-> \(<[<{nationality: <='Swede'>, pet: <='dog'>}>]> $! \)
-> \(def current: $;
$permutationsOf5... -> $smokes($) -> \[i]({$current($i), smoke: $}! \)!
\)
-> \(<[<{smoke: <='Pall Mall'>, pet: <='birds'>}>]> $! \)
-> \(<[<{smoke: <='Dunhill'>, colour: <='yellow'>}>]> $! \)
-> \(<[(<{smoke: <='Blend'>}>:<{pet: <='cats'>}>)] | [(<{pet: <='cats'>}>:<{smoke: <='Blend'>}>)]> $! \)
-> \(<[(<{smoke: <='Dunhill'>}>:<{pet: <='horse'>}>)] | [(<{pet: <='horse'>}>:<{smoke: <='Dunhill'>}>)]> $! \)
-> \(<[<{smoke: <='Blue Master'>, drink: <='beer'>}>]> $! \)
-> \(<[<{smoke: <='Prince'>, nationality: <='German'>}>]> $! \)
-> \(<[(<{smoke: <='Blend'>}>:<{drink: <='water'>}>)] | [(<{drink: <='water'>}>:<{smoke: <='Blend'>}>)]> $! \)
-> \[i](when <{pet: <='zebra'>}> do 'The $.nationality; owns the zebra.$#10;' -> !OUT::write $!
otherwise $! \)
-> \[i]('$i;: $;'! \) -> '$... -> '$;$#10;';$#10;'
-> !OUT::write
</syntaxhighlight>
{{out}}
<pre>
The German owns the zebra.
1: {colour=yellow, drink=water, nationality=Norwegian, pet=cats, smoke=Dunhill}
2: {colour=blue, drink=tea, nationality=Dane, pet=horse, smoke=Blend}
3: {colour=red, drink=milk, nationality=Englishman, pet=birds, smoke=Pall Mall}
4: {colour=green, drink=coffee, nationality=German, pet=zebra, smoke=Prince}
5: {colour=white, drink=beer, nationality=Swede, pet=dog, smoke=Blue Master}
</pre>
=={{header|Tcl}}==
{{trans|Python}}
{{tcllib|struct::list}}<
# Implements the constants by binding them directly into the named procedures.
Line 6,757 ⟶ 7,551:
initConstants isPossible
main</
{{out}}
<pre>
Line 6,767 ⟶ 7,561:
Smoke: PallMall BlueMaster Blend Dunhill Prince
Pet: Bird Dog Horse Cat Zebra
</pre>
=={{header|Uiua}}==
Usese the same re-ordering of rules as a lot of other approaches. Builds and filters the list as it goes.
<syntaxhighlight lang="uiua">
Perms ← ☇1⍉∧(≡↻⇡⟜↯+1⟜⊂):¤¤°⊂⇡
Ps ← ≡⊏⊙¤Perms ⧻.
Ps "BGRWY" # Col = 0
▽⊸(=-1⊃(⊗@W|⊗@G)) # W right of G
/⊂⊞⊟ :Ps "DEGNS" # Nation = 1
▽⊸≡(=@N⊡0⊡1) # Norwegian in pos 0
▽⊸≡(=⊃(⊗@E⊡1|⊗@R⊡0)) # Red == English
▽⊸≡(=1⌵-⊃(⊗@N⊡1|⊗@B⊡0)) # Blue next to Norwegian
/⊂⊞⊂ :Ps"BCDHZ" # Pets = 2
▽⊸≡(=⊃(⊗@D⊡2|⊗@S⊡1)) # Swede owns dog
/⊂⊞⊂ :Ps"BCMTW" # Drinks = 3
▽⊸≡(=@M⊡2⊡3) # Milk in pos 2
▽⊸≡(=⊃(⊗@T⊡3|⊗@D⊡1)) # Dane drinks tea
▽⊸≡(=⊃(⊗@C⊡3|⊗@G⊡0)) # Green = Coffee
/⊂⊞⊂ :Ps"BbDpP" # Cigs = 4
▽⊸≡(=⊃(⊗@p⊡4|⊗@B⊡2)) # PallMall = Birds
▽⊸≡(=⊃(⊗@D⊡4|⊗@Y⊡0)) # Dunhill = Yellow
▽⊸≡(=⊃(⊗@b⊡4|⊗@B⊡3)) # BlueM = Beer
▽⊸≡(=⊃(⊗@P⊡4|⊗@G⊡1)) # Prince = German
▽⊸≡(=1⌵-⊃(⊗@B⊡4|⊗@C⊡2)) # Cat next to Blend
▽⊸≡(=1⌵-⊃(⊗@D⊡4|⊗@H⊡2)) # Horse next to Dunhill
▽⊸≡(=1⌵-⊃(⊗@B⊡4|⊗@W⊡3)) # Water next to Blend
&p $"Solutions found: _" ⧻.
&p$"_ owns the Z"⊡:⊡1,⊗@Z⊡2.⊢
&p"One line per house: "
&p"Col\tNat\tPet\tDrink\tCig"
≡(&p/(⊂⊂)"\t")⍉
</syntaxhighlight>
{{out}}
<pre>
Solutions found: 1
G owns the Z
One line per house:
Col Nat Pet Drink Cig
Y N C W D
B D H T B
R E B M p
G G Z C P
W S D B b
</pre>
=={{header|VBA}}==
{{trans|Phix}}
<syntaxhighlight lang="vb">Option Base 1
Public Enum attr
Colour = 1
Nationality
Beverage
Smoke
Pet
End Enum
Public Enum Drinks_
Beer = 1
Coffee
Milk
Tea
Water
End Enum
Public Enum nations
Danish = 1
English
German
Norwegian
Swedish
End Enum
Public Enum colors
Blue = 1
Green
Red
White
Yellow
End Enum
Public Enum tobaccos
Blend = 1
BlueMaster
Dunhill
PallMall
Prince
End Enum
Public Enum animals
Bird = 1
Cat
Dog
Horse
Zebra
End Enum
Public permutation As New Collection
Public perm(5) As Variant
Const factorial5 = 120
Public Colours As Variant, Nationalities As Variant, Drinks As Variant, Smokes As Variant, Pets As Variant
Private Sub generate(n As Integer, A As Variant)
If n = 1 Then
permutation.Add A
Else
For i = 1 To n
generate n - 1, A
If n Mod 2 = 0 Then
tmp = A(i)
A(i) = A(n)
A(n) = tmp
Else
tmp = A(1)
A(1) = A(n)
A(n) = tmp
End If
Next i
End If
End Sub
Function house(i As Integer, name As Variant) As Integer
Dim x As Integer
For x = 1 To 5
If perm(i)(x) = name Then
house = x
Exit For
End If
Next x
End Function
Function left_of(h1 As Integer, h2 As Integer) As Boolean
left_of = (h1 - h2) = -1
End Function
Function next_to(h1 As Integer, h2 As Integer) As Boolean
next_to = Abs(h1 - h2) = 1
End Function
Private Sub print_house(i As Integer)
Debug.Print i & ": "; Colours(perm(Colour)(i)), Nationalities(perm(Nationality)(i)), _
Drinks(perm(Beverage)(i)), Smokes(perm(Smoke)(i)), Pets(perm(Pet)(i))
End Sub
Public Sub Zebra_puzzle()
Colours = [{"blue","green","red","white","yellow"}]
Nationalities = [{"Dane","English","German","Norwegian","Swede"}]
Drinks = [{"beer","coffee","milk","tea","water"}]
Smokes = [{"Blend","Blue Master","Dunhill","Pall Mall","Prince"}]
Pets = [{"birds","cats","dog","horse","zebra"}]
Dim solperms As New Collection
Dim solutions As Integer
Dim b(5) As Integer, i As Integer
For i = 1 To 5: b(i) = i: Next i
'There are five houses.
generate 5, b
For c = 1 To factorial5
perm(Colour) = permutation(c)
'The green house is immediately to the left of the white house.
If left_of(house(Colour, Green), house(Colour, White)) Then
For n = 1 To factorial5
perm(Nationality) = permutation(n)
'The Norwegian lives in the first house.
'The English man lives in the red house.
'The Norwegian lives next to the blue house.
If house(Nationality, Norwegian) = 1 _
And house(Nationality, English) = house(Colour, Red) _
And next_to(house(Nationality, Norwegian), house(Colour, Blue)) Then
For d = 1 To factorial5
perm(Beverage) = permutation(d)
'The Dane drinks tea.
'They drink coffee in the green house.
'In the middle house they drink milk.
If house(Nationality, Danish) = house(Beverage, Tea) _
And house(Beverage, Coffee) = house(Colour, Green) _
And house(Beverage, Milk) = 3 Then
For s = 1 To factorial5
perm(Smoke) = permutation(s)
'In the yellow house they smoke Dunhill.
'The German smokes Prince.
'The man who smokes Blue Master drinks beer.
'They Drink water in a house next to the house where they smoke Blend.
If house(Colour, Yellow) = house(Smoke, Dunhill) _
And house(Nationality, German) = house(Smoke, Prince) _
And house(Smoke, BlueMaster) = house(Beverage, Beer) _
And next_to(house(Beverage, Water), house(Smoke, Blend)) Then
For p = 1 To factorial5
perm(Pet) = permutation(p)
'The Swede has a dog.
'The man who smokes Pall Mall has birds.
'The man who smokes Blend lives in the house next to the house with cats.
'In a house next to the house where they have a horse, they smoke Dunhill.
If house(Nationality, Swedish) = house(Pet, Dog) _
And house(Smoke, PallMall) = house(Pet, Bird) _
And next_to(house(Smoke, Blend), house(Pet, Cat)) _
And next_to(house(Pet, Horse), house(Smoke, Dunhill)) Then
For i = 1 To 5
print_house i
Next i
Debug.Print
solutions = solutions + 1
solperms.Add perm
End If
Next p
End If
Next s
End If
Next d
End If
Next n
End If
Next c
Debug.Print Format(solutions, "@"); " solution" & IIf(solutions > 1, "s", "") & " found"
For i = 1 To solperms.Count
For j = 1 To 5
perm(j) = solperms(i)(j)
Next j
Debug.Print "The " & Nationalities(perm(Nationality)(house(Pet, Zebra))) & " owns the Zebra"
Next i
End Sub</syntaxhighlight>{{out}}
<pre>1: yellow Norwegian water Dunhill cats
2: blue Dane tea Blend horse
3: red English milk Pall Mall birds
4: green German coffee Prince zebra
5: white Swede beer Blue Master dog
1 solution found
The German owns the Zebra</pre>
=={{header|V (Vlang)}}==
{{trans|Go}}
<syntaxhighlight lang="v (vlang)">type HouseSet = []House
struct House {
n Nationality
c Colour
a Animal
d Drink
s Smoke
}
// Define the possible values
enum Nationality {
english = 0
swede
dane
norwegian
german
}
enum Colour {
red = 0
green
white
yellow
blue
}
enum Animal {
dog = 0
birds
cats
horse
zebra
}
enum Drink {
tea = 0
coffee
milk
beer
water
}
enum Smoke {
pall_mall = 0
dunhill
blend
blue_master
prince
}
// And how to print them
const nationalities = [Nationality.english, Nationality.swede, Nationality.dane, Nationality.norwegian, Nationality.german]
const colours = [Colour.red, Colour.green, Colour.white, Colour.yellow, Colour.blue]
const animals = [Animal.dog, Animal.birds, Animal.cats, Animal.horse, Animal.zebra]
const drinks = [Drink.tea, Drink.coffee, Drink.milk, Drink.beer, Drink.water]
const smokes = [Smoke.pall_mall, Smoke.dunhill, Smoke.blend, Smoke.blue_master, Smoke.prince]
fn (h House) str() string {
return "${h.n:-9} ${h.c:-6} ${h.a:-5} ${h.d:-6} $h.s"
}
fn (hs HouseSet) str() string {
mut lines := []string{len: 0, cap: 5}
for i, h in hs {
s := "$i $h"
lines << s
}
return lines.join("\n")
}
// Simple brute force solution
fn simple_brute_force() (int, HouseSet) {
mut v := []House{}
for n in nationalities {
for c in colours {
for a in animals {
for d in drinks {
for s in smokes {
h := House{
n: n,
c: c,
a: a,
d: d,
s: s,
}
if !h.valid() {
continue
}
v << h
}
}
}
}
}
n := v.len
println("Generated $n valid houses")
mut combos := 0
mut first := 0
mut valid := 0
mut valid_set := []House{}
for a := 0; a < n; a++ {
if v[a].n != Nationality.norwegian { // Condition 10:
continue
}
for b := 0; b < n; b++ {
if b == a {
continue
}
if v[b].any_dups(v[a]) {
continue
}
for c := 0; c < n; c++ {
if c == b || c == a {
continue
}
if v[c].d != Drink.milk { // Condition 9:
continue
}
if v[c].any_dups(v[b], v[a]) {
continue
}
for d := 0; d < n; d++ {
if d == c || d == b || d == a {
continue
}
if v[d].any_dups(v[c], v[b], v[a]) {
continue
}
for e := 0; e < n; e++ {
if e == d || e == c || e == b || e == a {
continue
}
if v[e].any_dups(v[d], v[c], v[b], v[a]) {
continue
}
combos++
set := HouseSet([v[a], v[b], v[c], v[d], v[e]])
if set.valid() {
valid++
if valid == 1 {
first = combos
}
valid_set = set
//return set
}
}
}
}
}
}
println("Tested $first different combinations of valid houses before finding solution")
println("Tested $combos different combinations of valid houses in total")
return valid, valid_set
}
// any_dups returns true if h as any duplicate attributes with any of the specified houses
fn (h House) any_dups(list ...House) bool {
for b in list {
if h.n == b.n || h.c == b.c || h.a == b.a || h.d == b.d || h.s == b.s {
return true
}
}
return false
}
fn (h House) valid() bool {
// Condition 2:
if (h.n == Nationality.english && h.c != Colour.red) || (h.n != Nationality.english && h.c == Colour.red) {
return false
}
// Condition 3:
if (h.n == Nationality.swede && h.a != Animal.dog) || (h.n != Nationality.swede && h.a == Animal.dog) {
return false
}
// Condition 4:
if (h.n == Nationality.dane && h.d != Drink.tea) || (h.n != Nationality.dane && h.d == Drink.tea ){
return false
}
// Condition 6:
if (h.c == Colour.green && h.d != Drink.coffee) || (h.c != Colour.green && h.d == Drink.coffee) {
return false
}
// Condition 7:
if (h.a == Animal.birds && h.s != Smoke.pall_mall) || (h.a != Animal.birds && h.s == Smoke.pall_mall) {
return false
}
// Condition 8:
if (h.c == Colour.yellow && h.s != Smoke.dunhill) || (h.c != Colour.yellow && h.s == Smoke.dunhill) {
return false
}
// Condition 11:
if h.a == Animal.cats && h.s == Smoke.blend {
return false
}
// Condition 12:
if h.a == Animal.horse && h.s == Smoke.dunhill {
return false
}
// Condition 13:
if (h.d == Drink.beer && h.s != Smoke.blue_master) || (h.d != Drink.beer && h.s == Smoke.blue_master) {
return false
}
// Condition 14:
if (h.n == Nationality.german && h.s != Smoke.prince) || (h.n != Nationality.german && h.s == Smoke.prince) {
return false
}
// Condition 15:
if h.n == Nationality.norwegian && h.c == Colour.blue {
return false
}
// Condition 16:
if h.d == Drink.water && h.s == Smoke.blend {
return false
}
return true
}
fn (hs HouseSet) valid() bool {
mut ni := map[Nationality]int{}
mut ci := map[Colour]int{}
mut ai := map[Animal]int{}
mut di := map[Drink]int{}
mut si := map[Smoke]int{}
for i, h in hs {
ni[h.n] = i
ci[h.c] = i
ai[h.a] = i
di[h.d] = i
si[h.s] = i
}
// Condition 5:
if ci[Colour.green]+1 != ci[Colour.white] {
return false
}
// Condition 11:
if dist(ai[Animal.cats], si[Smoke.blend]) != 1 {
return false
}
// Condition 12:
if dist(ai[Animal.horse], si[Smoke.dunhill]) != 1 {
return false
}
// Condition 15:
if dist(ni[Nationality.norwegian], ci[Colour.blue]) != 1 {
return false
}
// Condition 16:
if dist(di[Drink.water], si[Smoke.blend]) != 1 {
return false
}
// Condition 9: (already tested elsewhere)
if hs[2].d != Drink.milk {
return false
}
// Condition 10: (already tested elsewhere)
if hs[0].n != Nationality.norwegian {
return false
}
return true
}
fn dist(a int, b int) int {
if a > b {
return a - b
}
return b - a
}
fn main() {
n, sol := simple_brute_force()
println("$n solution found")
println(sol)
}</syntaxhighlight>
{{out}}
<pre>
Generated 51 valid houses
Tested 652 different combinations of valid houses before finding solution
Tested 750 different combinations of valid houses in total
1 solution found
0 norwegian yellow cats water dunhill
1 dane blue horse tea blend
2 english red birds milk pall_mall
3 german green zebra coffee prince
4 swede white dog beer blue_master
</pre>
=={{header|Wren}}==
{{trans|Kotlin}}
{{libheader|Wren-fmt}}
<syntaxhighlight lang="wren">import "./fmt" for Fmt
var colors = ["Red", "Green", "White", "Yellow", "Blue"]
var nations = ["English", "Swede", "Danish", "Norwegian", "German"]
var animals = ["Dog", "Birds", "Cats", "Horse", "Zebra"]
var drinks = ["Tea", "Coffee", "Milk", "Beer", "Water"]
var smokes = ["Pall Mall", "Dunhill", "Blend", "Blue Master", "Prince"]
var p = List.filled(120, null) // stores all permutations of numbers 0..4
for (i in 0..119) p[i] = List.filled(5, -1)
var nextPerm = Fn.new { |perm|
var size = perm.count
var k = -1
for (i in size-2..0) {
if (perm[i] < perm[i + 1]) {
k = i
break
}
}
if (k == -1) return false // last permutation
for (l in size-1..k) {
if (perm[k] < perm[l]) {
perm.swap(k, l)
var m = k + 1
var n = size - 1
while (m < n) {
perm.swap(m, n)
m = m + 1
n = n - 1
}
break
}
}
return true
}
var check = Fn.new { |a1, a2, v1, v2|
for (i in 0..4) {
if (p[a1][i] == v1) return p[a2][i] == v2
}
return false
}
var checkLeft = Fn.new { |a1, a2, v1, v2|
for (i in 0..3) {
if (p[a1][i] == v1) return p[a2][i + 1] == v2
}
return false
}
var checkRight = Fn.new { |a1, a2, v1, v2|
for (i in 1..4) {
if (p[a1][i] == v1) return p[a2][i - 1] == v2
}
return false
}
var checkAdjacent = Fn.new { |a1, a2, v1, v2|
return checkLeft.call(a1, a2, v1, v2) || checkRight.call(a1, a2, v1, v2)
}
var printHouses = Fn.new { |c, n, a, d, s|
var owner = ""
System.print("House Color Nation Animal Drink Smokes")
System.print("===== ====== ========= ====== ====== ===========")
for (i in 0..4) {
var f = "$3d $-6s $-9s $-6s $-6s $-11s"
var l = [i + 1, colors[p[c][i]], nations[p[n][i]], animals[p[a][i]], drinks[p[d][i]], smokes[p[s][i]]]
Fmt.lprint(f, l)
if (animals[p[a][i]] == "Zebra") owner = nations[p[n][i]]
}
System.print("\nThe %(owner) owns the Zebra\n")
}
var fillHouses = Fn.new {
var solutions = 0
for (c in 0..119) {
if (!checkLeft.call(c, c, 1, 2)) continue // C5 : Green left of white
for (n in 0..119) {
if (p[n][0] != 3) continue // C10: Norwegian in First
if (!check.call(n, c, 0, 0)) continue // C2 : English in Red
if (!checkAdjacent.call(n, c, 3, 4)) continue // C15: Norwegian next to Blue
for (a in 0..119) {
if (!check.call(a, n, 0, 1)) continue // C3 : Swede has Dog
for (d in 0..119) {
if (p[d][2] != 2) continue // C9 : Middle drinks Milk
if (!check.call(d, n, 0, 2)) continue // C4 : Dane drinks Tea
if (!check.call(d, c, 1, 1)) continue // C6 : Green drinks Coffee
for (s in 0..119) {
if (!check.call(s, a, 0, 1)) continue // C7 : Pall Mall has Birds
if (!check.call(s, c, 1, 3)) continue // C8 : Yellow smokes Dunhill
if (!check.call(s, d, 3, 3)) continue // C13: Blue Master drinks Beer
if (!check.call(s, n, 4, 4)) continue // C14: German smokes Prince
if (!checkAdjacent.call(s, a, 2, 2)) continue // C11: Blend next to Cats
if (!checkAdjacent.call(s, a, 1, 3)) continue // C12: Dunhill next to Horse
if (!checkAdjacent.call(s, d, 2, 4)) continue // C16: Blend next to Water
solutions = solutions + 1
printHouses.call(c, n, a, d, s)
}
}
}
}
}
return solutions
}
var perm = [0, 1, 2, 3, 4]
for (i in 0..119) {
for (j in 0..4) p[i][j] = perm[j]
nextPerm.call(perm)
}
var solutions = fillHouses.call()
var plural = (solutions == 1) ? "" : "s"
System.print("%(solutions) solution%(plural) found")</syntaxhighlight>
{{out}}
<pre>
House Color Nation Animal Drink Smokes
===== ====== ========= ====== ====== ===========
1 Yellow Norwegian Cats Water Dunhill
2 Blue Danish Horse Tea Blend
3 Red English Birds Milk Pall Mall
4 Green German Zebra Coffee Prince
5 White Swede Dog Beer Blue Master
The German owns the Zebra
1 solution found
</pre>
Line 6,773 ⟶ 8,213:
Lists are used as associated arrays rather than hash tables. With only five entries, it doesn't really matter.
<
fcn c2 { people.find(English)==houses.find(Red) }
fcn c3 { people.find(Swede)==pets.find(Dog) }
Line 6,833 ⟶ 8,273:
.zip(titles,names))
{ println(list.apply(names.get):fmt(title,_.xplode())) }
}</
{{out}}
<pre>
|