Zebra puzzle
From Rosetta Code
You are encouraged to solve this task according to the task description, using any language you may know.
The 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 birds.
- 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 cats.
- 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 question is, who owns the zebra?
Additionally, list the solution for all the houses. Optionally, show the solution is unique.
cf. Dinesman's multiple-dwelling problem
Contents |
[edit] Ada
Not the prettiest Ada, but its simple and very fast. Similar to my Dinesman's code, uses enums to keep things readable.
with Ada.Text_IO; use Ada.Text_IO;
procedure Zebra is
type Content is (Beer, Coffee, Milk, Tea, Water,
Danish, English, German, Norwegian, Swedish,
Blue, Green, Red, White, Yellow,
Blend, BlueMaster, Dunhill, PallMall, Prince,
Bird, Cat, Dog, Horse, Zebra);
type Test is (Drink, Person, Color, Smoke, Pet);
type House is (One, Two, Three, Four, Five);
type Street is array (Test'Range, House'Range) of Content;
type Alley is access all Street;
procedure Print (mat : Alley) is begin
for H in House'Range loop
Put(H'Img&": ");
for T in Test'Range loop
Put(T'Img&"="&mat(T,H)'Img&" ");
end loop; New_Line; end loop;
end Print;
function FinalChecks (mat : Alley) return Boolean is
function Diff (A, B : Content; CA , CB : Test) return Integer is begin
for H1 in House'Range loop for H2 in House'Range loop
if mat(CA,H1) = A and mat(CB,H2) = B then
return House'Pos(H1) - House'Pos(H2);
end if;
end loop; end loop;
end Diff;
begin
if abs(Diff(Norwegian, Blue, Person, Color)) = 1
and Diff(Green, White, Color, Color) = -1
and abs(Diff(Horse, Dunhill, Pet, Smoke)) = 1
and abs(Diff(Water, Blend, Drink, Smoke)) = 1
and abs(Diff(Blend, Cat, Smoke, Pet)) = 1
then return True;
end if;
return False;
end FinalChecks;
function Constrained (mat : Alley; atest : Natural) return Boolean is begin
-- Tests seperated into levels for speed, not strictly necessary
-- As such, the program finishes in around ~0.02s
case Test'Val (atest) is
when Drink => -- Drink
if mat (Drink, Three) /= Milk then return False; end if;
return True;
when Person => -- Drink+Person
for H in House'Range loop
if (mat(Person,H) = Norwegian and H /= One)
or (mat(Person,H) = Danish and mat(Drink,H) /= Tea)
then return False; end if;
end loop;
return True;
when Color => -- Drink+People+Color
for H in House'Range loop
if (mat(Person,H) = English and mat(Color,H) /= Red)
or (mat(Drink,H) = Coffee and mat(Color,H) /= Green)
then return False; end if;
end loop;
return True;
when Smoke => -- Drink+People+Color+Smoke
for H in House'Range loop
if (mat(Color,H) = Yellow and mat(Smoke,H) /= Dunhill)
or (mat(Smoke,H) = BlueMaster and mat(Drink,H) /= Beer)
or (mat(Person,H) = German and mat(Smoke,H) /= Prince)
then return False; end if;
end loop;
return True;
when Pet => -- Drink+People+Color+Smoke+Pet
for H in House'Range loop
if (mat(Person,H) = Swedish and mat(Pet,H) /= Dog)
or (mat(Smoke,H) = PallMall and mat(Pet,H) /= Bird)
then return False; end if;
end loop;
return FinalChecks(mat); -- Do the next-to checks
end case;
end Constrained;
procedure Solve (mat : Alley; t, n : Natural) is
procedure Swap (I, J : Natural) is
temp : constant Content := mat (Test'Val (t), House'Val (J));
begin
mat (Test'Val (t), House'Val (J)) := mat (Test'Val (t), House'Val (I));
mat (Test'Val (t), House'Val (I)) := temp;
end Swap;
begin
if n = 1 and Constrained (mat, t) then -- test t passed
if t < 4 then Solve (mat, t + 1, 5); -- Onto next test
else Print (mat); return; -- Passed and t=4 means a solution
end if;
end if;
for i in 0 .. n - 1 loop -- The permutations part
Solve (mat, t, n - 1);
if n mod 2 = 1 then Swap (0, n - 1);
else Swap (i, n - 1); end if;
end loop;
end Solve;
myStreet : aliased Street;
myAlley : constant Alley := myStreet'Access;
begin
for i in Test'Range loop for j in House'Range loop -- Init Matrix
myStreet (i,j) := Content'Val(Test'Pos(i)*5 + House'Pos(j));
end loop; end loop;
Solve (myAlley, 0, 5); -- start at test 0 with 5 options
end Zebra;
- Output:
ONE: DRINK=WATER PERSON=NORWEGIAN COLOR=YELLOW SMOKE=DUNHILL PET=CAT TWO: DRINK=TEA PERSON=DANISH COLOR=BLUE SMOKE=BLEND PET=HORSE THREE: DRINK=MILK PERSON=ENGLISH COLOR=RED SMOKE=PALLMALL PET=BIRD FOUR: DRINK=COFFEE PERSON=GERMAN COLOR=GREEN SMOKE=PRINCE PET=ZEBRA FIVE: DRINK=BEER PERSON=SWEDISH COLOR=WHITE SMOKE=BLUEMASTER PET=DOG
[edit] BBC BASIC
REM The names (only used for printing the results):
DIM Drink$(4), Nation$(4), Colr$(4), Smoke$(4), Animal$(4)
Drink$() = "Beer", "Coffee", "Milk", "Tea", "Water"
Nation$() = "Denmark", "England", "Germany", "Norway", "Sweden"
Colr$() = "Blue", "Green", "Red", "White", "Yellow"
Smoke$() = "Blend", "BlueMaster", "Dunhill", "PallMall", "Prince"
Animal$() = "Birds", "Cats", "Dog", "Horse", "Zebra"
REM Some single-character tags:
a$ = "A" : b$ = "B" : c$ = "C" : d$ = "D" : e$ = "E"
REM BBC BASIC Doesn't have enumerations!
Beer$=a$ : Coffee$=b$ : Milk$=c$ : Tea$=d$ : Water$=e$
Denmark$=a$ : England$=b$ : Germany$=c$ : Norway$=d$ : Sweden$=e$
Blue$=a$ : Green$=b$ : Red$=c$ : White$=d$ : Yellow$=e$
Blend$=a$ : BlueMaster$=b$ : Dunhill$=c$ : PallMall$=d$ : Prince$=e$
Birds$=a$ : Cats$=b$ : Dog$=c$ : Horse$=d$ : Zebra$=e$
REM Create the 120 permutations of 5 objects:
DIM perm$(120), x$(4) : x$() = a$, b$, c$, d$, e$
REPEAT
p% += 1
perm$(p%) = x$(0)+x$(1)+x$(2)+x$(3)+x$(4)
UNTIL NOT FNperm(x$())
REM Express the statements as conditional expressions:
ex2$ = "INSTR(Nation$,England$) = INSTR(Colr$,Red$)"
ex3$ = "INSTR(Nation$,Sweden$) = INSTR(Animal$,Dog$)"
ex4$ = "INSTR(Nation$,Denmark$) = INSTR(Drink$,Tea$)"
ex5$ = "INSTR(Colr$,Green$+White$) <> 0"
ex6$ = "INSTR(Drink$,Coffee$) = INSTR(Colr$,Green$)"
ex7$ = "INSTR(Smoke$,PallMall$) = INSTR(Animal$,Birds$)"
ex8$ = "INSTR(Smoke$,Dunhill$) = INSTR(Colr$,Yellow$)"
ex9$ = "MID$(Drink$,3,1) = Milk$"
ex10$ = "LEFT$(Nation$,1) = Norway$"
ex11$ = "ABS(INSTR(Smoke$,Blend$)-INSTR(Animal$,Cats$)) = 1"
ex12$ = "ABS(INSTR(Smoke$,Dunhill$)-INSTR(Animal$,Horse$)) = 1"
ex13$ = "INSTR(Smoke$,BlueMaster$) = INSTR(Drink$,Beer$)"
ex14$ = "INSTR(Nation$,Germany$) = INSTR(Smoke$,Prince$)"
ex15$ = "ABS(INSTR(Nation$,Norway$)-INSTR(Colr$,Blue$)) = 1"
ex16$ = "ABS(INSTR(Smoke$,Blend$)-INSTR(Drink$,Water$)) = 1"
REM Solve:
solutions% = 0
TIME = 0
FOR nation% = 1 TO 120
Nation$ = perm$(nation%)
IF EVAL(ex10$) THEN
FOR colr% = 1 TO 120
Colr$ = perm$(colr%)
IF EVAL(ex5$) IF EVAL(ex2$) IF EVAL(ex15$) THEN
FOR drink% = 1 TO 120
Drink$ = perm$(drink%)
IF EVAL(ex9$) IF EVAL(ex4$) IF EVAL(ex6$) THEN
FOR smoke% = 1 TO 120
Smoke$ = perm$(smoke%)
IF EVAL(ex14$) IF EVAL(ex13$) IF EVAL(ex16$) IF EVAL(ex8$) THEN
FOR animal% = 1 TO 120
Animal$ = perm$(animal%)
IF EVAL(ex3$) IF EVAL(ex7$) IF EVAL(ex11$) IF EVAL(ex12$) THEN
PRINT "House Drink Nation Colour Smoke Animal"
FOR house% = 1 TO 5
PRINT ; house% ,;
PRINT Drink$(ASCMID$(Drink$,house%)-65),;
PRINT Nation$(ASCMID$(Nation$,house%)-65),;
PRINT Colr$(ASCMID$(Colr$,house%)-65),;
PRINT Smoke$(ASCMID$(Smoke$,house%)-65),;
PRINT Animal$(ASCMID$(Animal$,house%)-65)
NEXT
solutions% += 1
ENDIF
NEXT animal%
ENDIF
NEXT smoke%
ENDIF
NEXT drink%
ENDIF
NEXT colr%
ENDIF
NEXT nation%
PRINT '"Number of solutions = "; solutions%
PRINT "Solved in " ; TIME/100 " seconds"
END
DEF FNperm(x$())
LOCAL i%, j%
FOR i% = DIM(x$(),1)-1 TO 0 STEP -1
IF x$(i%) < x$(i%+1) EXIT FOR
NEXT
IF i% < 0 THEN = FALSE
j% = DIM(x$(),1)
WHILE x$(j%) <= x$(i%) j% -= 1 : ENDWHILE
SWAP x$(i%), x$(j%)
i% += 1
j% = DIM(x$(),1)
WHILE i% < j%
SWAP x$(i%), x$(j%)
i% += 1
j% -= 1
ENDWHILE
= TRUE
Output:
House Drink Nation Colour Smoke Animal 1 Water Norway Yellow Dunhill Cats 2 Tea Denmark Blue Blend Horse 3 Milk England Red PallMall Birds 4 Coffee Germany Green Prince Zebra 5 Beer Sweden White BlueMasterDog Number of solutions = 1 Solved in 0.12 seconds
[edit] C
#include <stdio.h>
#include <string.h>
enum HouseStatus {Invalid, Underfull, Valid};
enum Attrib {C, M, D, A, S};
// Unfilled attributes are represented by -1
enum Colors {Red, Green, White, Yellow, Blue};
enum Mans {English, Swede, Dane, German, Norwegian};
enum Drinks {Tea, Coffee, Milk, Beer, Water};
enum Animals {Dog, Birds, Cats, Horse, Zebra};
enum Smokes {PallMall, Dunhill, Blend, BlueMaster, Prince};
void printHouses(int ha[5][5])
{
const char *Color [] = {"Red", "Green", "White", "Yellow", "Blue"};
const char *Man [] = {"English", "Swede", "Dane", "German", "Norwegian"};
const char *Drink [] = {"Tea", "Coffee", "Milk", "Beer", "Water"};
const char *Animal[] = {"Dog", "Birds", "Cats", "Horse", "Zebra"};
const char *Smoke [] = {"PallMall", "Dunhill", "Blend", "BlueMaster", "Prince"};
printf("%-10.10s%-10.10s%-10.10s%-10.10s%-10.10s%-10.10s\n",
"House", "Color", "Man", "Drink", "Animal", "Smoke");
for(int i=0; i<5; i++) {
printf("%-10d", i);
if (ha[i][C]>=0)
printf("%-10.10s", Color[ha[i][C]]);
else
printf("%-10.10s", "-");
if (ha[i][M]>=0)
printf("%-10.10s", Man[ha[i][M]]);
else
printf("%-10.10s", "-");
if (ha[i][D]>=0)
printf("%-10.10s", Drink[ha[i][D]]);
else
printf("%-10.10s", "-");
if (ha[i][A]>=0)
printf("%-10.10s", Animal[ha[i][A]]);
else
printf("%-10.10s", "-");
if (ha[i][S]>=0)
printf("%-10.10s\n", Smoke[ha[i][S]]);
else
printf("-\n");
}
}
int checkHouses(int ha[5][5])
{
int c_add=0, c_or=0;
int m_add=0, m_or=0;
int d_add=0, d_or=0;
int a_add=0, a_or=0;
int s_add=0, s_or=0;
// Cond 9: In the middle house they drink milk
if ( ha[2][D] >= 0 && ha[2][D] != Milk )
return Invalid;
// Cond 10: The Norwegian lives in the first house
if ( ha[0][M] >= 0 && ha[0][M] != Norwegian )
return Invalid;
for (int i=0; i<5; i++) {
// Uniqueness tests
if (ha[i][C] >= 0) {
c_add += (1<<ha[i][C]);
c_or |= (1<<ha[i][C]);
}
if (ha[i][M] >= 0) {
m_add += (1<<ha[i][M]);
m_or |= (1<<ha[i][M]);
}
if (ha[i][D] >= 0) {
d_add += (1<<ha[i][D]);
d_or |= (1<<ha[i][D]);
}
if (ha[i][A] >= 0) {
a_add += (1<<ha[i][A]);
a_or |= (1<<ha[i][A]);
}
if (ha[i][S] >= 0) {
s_add += (1<<ha[i][S]);
s_or |= (1<<ha[i][S]);
}
// Cond 2: The English man lives in the red house
if ( ( ha[i][M] >= 0 && ha[i][C] >= 0 ) &&
( (ha[i][M] == English && ha[i][C] != Red ) || // checking both
(ha[i][M] != English && ha[i][C] == Red ) ) ) // to make things quicker
return Invalid;
// Cond 3: The Swede has a dog
if ( ( ha[i][M] >= 0 && ha[i][A] >= 0 ) &&
((ha[i][M] == Swede && ha[i][A] != Dog )||
(ha[i][M] != Swede && ha[i][A] == Dog ) ) )
return Invalid;
// Cond 4: The Dane drinks tea
if ( ( ha[i][M] >= 0 && ha[i][D] >= 0 ) &&
((ha[i][M] == Dane && ha[i][D] != Tea )||
(ha[i][M] != Dane && ha[i][D] == Tea ) ) )
return Invalid;
// Cond 5: The green house is immediately to the left of the white house
if ( ( i>0 && ha[i][C] >= 0 /*&& ha[i-1][C] >= 0 */) &&
((ha[i-1][C] == Green && ha[i][C] != White )||
(ha[i-1][C] != Green && ha[i][C] == White ) ) )
return Invalid;
// Cond 6: drink coffee in the green house
if ( ( ha[i][C] >= 0 && ha[i][D] >= 0 ) &&
((ha[i][C] == Green && ha[i][D] != Coffee )||
(ha[i][C] != Green && ha[i][D] == Coffee ) ) )
return Invalid;
// Cond 7: The man who smokes Pall Mall has birds
if ( ( ha[i][S] >= 0 && ha[i][A] >= 0 ) &&
((ha[i][S] == PallMall && ha[i][A] != Birds )||
(ha[i][S] != PallMall && ha[i][A] == Birds ) ) )
return Invalid;
// Cond 8: In the yellow house they smoke Dunhill
if ( ( ha[i][S] >= 0 && ha[i][C] >= 0 ) &&
((ha[i][S] == Dunhill && ha[i][C] != Yellow )||
(ha[i][S] != Dunhill && ha[i][C] == Yellow ) ) )
return Invalid;
// Cond 11: The man who smokes Blend lives in the house next to the house with cats
if (ha[i][S] == Blend) {
if (i==0 && ha[i+1][A]>=0&&ha[i+1][A]!=Cats)
return Invalid;
else if (i==4 && ha[i-1][A]!=Cats)
return Invalid;
else if (ha[i+1][A]>=0&&ha[i+1][A]!=Cats&&ha[i-1][A]!=Cats)
return Invalid;
}
// Cond 12: In a house next to the house where they have a horse, they smoke Dunhill
if (ha[i][S] == Dunhill) {
if (i==0 && ha[i+1][A]>=0&&ha[i+1][A]!=Horse)
return Invalid;
else if (i==4 && ha[i-1][A]!=Horse)
return Invalid;
else if (ha[i+1][A]>=0&&ha[i+1][A]!=Horse&&ha[i-1][A]!=Horse)
return Invalid;
}
// Cond 13: The man who smokes Blue Master drinks beer
if ( ( ha[i][S] >= 0 && ha[i][D] >= 0 ) &&
((ha[i][S] == BlueMaster && ha[i][D] != Beer )||
(ha[i][S] != BlueMaster && ha[i][D] == Beer ) ) )
return Invalid;
// Cond 14: The German smokes Prince
if ( ( ha[i][M] >= 0 && ha[i][S] >= 0 ) &&
((ha[i][M] == German && ha[i][S] != Prince )||
(ha[i][M] != German && ha[i][S] == Prince ) ) )
return Invalid;
// Cond 15: The Norwegian lives next to the blue house
if ( ha[i][M] == Norwegian &&
((i<4&&ha[i+1][C]>=0&&ha[i+1][C]!=Blue) ||
(i>0&&ha[i-1][C]!=Blue)))
return Invalid;
// Cond 16: They drink water in a house next to the house where they smoke Blend.
if (ha[i][S] == Blend) {
if (i==0 && ha[i+1][D]>=0&&ha[i+1][D]!=Water)
return Invalid;
else if (i==4 && ha[i-1][D]!=Water)
return Invalid;
else if (ha[i+1][D]>=0&&ha[i+1][D]!=Water&&ha[i-1][D]!=Water)
return Invalid;
}
}
if ((c_add != c_or)||(m_add != m_or)||(d_add != d_or)
||(a_add != a_or)||(s_add != s_or)) {
return Invalid;
}
if ((c_add != 0b11111)||(m_add != 0b11111)||(d_add != 0b11111)
||(a_add != 0b11111)||(s_add != 0b11111)) {
return Underfull;
}
return Valid;
}
int bruteFill(int ha[5][5], int hno, int attr)
{
int stat = checkHouses(ha);
if (( stat == Valid)||(stat == Invalid))
return stat;
int hb[5][5];
memcpy(hb, ha, sizeof(int)*5*5);
for (int i=0; i<5; i++) {
hb[hno][attr] = i;
stat = checkHouses(hb);
if (stat != Invalid) {
int nexthno, nextattr;
if (attr<4) {
nextattr = attr+1;
nexthno = hno;
} else {
nextattr = 0;
nexthno = hno+1;
}
stat = bruteFill(hb, nexthno, nextattr);
if (stat != Invalid) {
memcpy(ha, hb, sizeof(int)*5*5);
return stat;
}
}
}
// we only come here if none of the attr values assigned were valid
return Invalid;
}
int main(void)
{
int ha[5][5]={{-1,-1,-1,-1,-1},{-1,-1,-1,-1,-1},{-1,-1,-1,-1,-1},
{-1,-1,-1,-1,-1},{-1,-1,-1,-1,-1}};
bruteFill(ha, 0, 0);
printHouses(ha);
return 0;
}
Output:
% gcc -Wall -O3 -std=c99 zebra.c -o zebra && time ./zebra 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 ./zebra 0.00s user 0.00s system 0% cpu 0.002 total
The execution time is too small to be reliably measured on my machine.
[edit] C Generated from Perl
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.
#!/usr/bin/perloutput (ran as
use utf8;
no strict;
my (%props, %name, @pre, @conds, @works, $find_all_solutions);
sub do_consts {
local $";
for my $p (keys %props) {
my @s = @{ $props{$p} };
$" = ", ";
print "enum { ${p}_none = 0, @s };\n";
$" = '", "';
print "const char *string_$p [] = { \"###\", \"@s\" };\n\n";
}
print "#define FIND_BY(p) \\
int find_by_##p(int v) { \\
int i; \\
for (i = 0; i < N_ITEMS; i++) \\
if (house[i].p == v) return i; \\
return -1; }\n";
print "FIND_BY($_)" for (keys %props);
local $" = ", ";
my @k = keys %props;
my $sl = 0;
for (keys %name) {
if (length > $sl) { $sl = length }
}
my $fmt = ("%".($sl + 1)."s ") x @k;
my @arg = map { "string_$_"."[house[i].$_]" } @k;
print << "SNIPPET";
int work0(void) {
int i;
for (i = 0; i < N_ITEMS; i++)
printf("%d $fmt\\n", i, @arg);
puts(\"\");
return 1;
}
SNIPPET
}
sub setprops {
%props = @_;
my $l = 0;
my @k = keys %props;
for my $p (@k) {
my @s = @{ $props{$p} };
if ($l && $l != @s) {
die "bad length @s";
}
$l = @s;
$name{$_} = $p for @s;
}
local $" = ", ";
print "#include <stdio.h>
#define N_ITEMS $l
struct item_t { int @k; } house[N_ITEMS] = {{0}};\n";
}
sub pair {NB. h =.~.&> compose&.>~/y,<h
my ($c1, $c2, $diff) = @_;
$diff //= [0];
$diff = [$diff] unless ref $diff;
push @conds, [$c1, $c2, $diff];
}
sub make_conditions {
my $idx = 0;
my $return1 = $find_all_solutions ? "" : "return 1";
print "
#define TRY(a, b, c, d, p, n) \\
if ((b = a d) >= 0 && b < N_ITEMS) { \\
if (!house[b].p) { \\
house[b].p = c; \\
if (n()) $return1; \\
house[b].p = 0; \\
}}
";
while (@conds) {
my ($c1, $c2, $diff) = @{ pop @conds };
my $p2 = $name{$c2} or die "bad prop $c2";
if ($c1 =~ /^\d+$/) {
push @pre, "house[$c1].$p2 = $c2;";
next;
}
my $p1 = $name{$c1} or die "bad prop $c1";
my $next = "work$idx";
my $this = "work".++$idx;
print "
/* condition pair($c1, $c2, [@$diff]) */
int $this(void) {
int a = find_by_$p1($c1);
int b = find_by_$p2($c2);
if (a != -1 && b != -1) {
switch(b - a) {
";
print "case $_: " for @$diff;
print "return $next(); default: return 0; }\n } if (a != -1) {";
print "TRY(a, b, $c2, +($_), $p2, $next);" for @$diff;
print " return 0; } if (b != -1) {";
print "TRY(b, a, $c1, -($_), $p1, $next);" for @$diff;
print "
return 0; }
/* neither condition is set; try all possibles */
for (a = 0; a < N_ITEMS; a++) {
if (house[a].$p1) continue;
house[a].$p1 = $c1;
";
print "TRY(a, b, $c2, +($_), $p2, $next);" for @$diff;
print " house[a].$p1 = 0; } return 0; }";
}
print "int main() { @pre return !work$idx(); }";
}
sub make_c {
do_consts;
make_conditions;
}
# ---- above should be generic for all similar puzzles ---- #
# ---- below: per puzzle setup ---- #
# property names and values
setprops (
'nationality' # Svensk n. a Swede, not a swede (kålrot).
# AEnglisk (from middle Viking "Æŋløsåksen") n. a Brit.
=> [ qw(Deutsch Svensk Norske Danske AEnglisk) ],
'pet' => [ qw(birds dog horse zebra cats) ],
'drink' => [ qw(water tea milk beer coffee) ],
'smoke' => [ qw(dunhill blue_master prince blend pall_mall) ],
'color' => [ qw(red green yellow white blue) ]
);
# constraints
pair(AEnglisk, red);
pair(Svensk, dog);
pair(Danske, tea);
pair(green, white, 1); # "to the left of" can mean either 1 or -1: ambiguous
pair(coffee, green);
pair(pall_mall, birds);
pair(yellow, dunhill);
pair(2, milk);
pair(0, Norske);
pair(blend, cats, [-1, 1]);
pair(horse, dunhill, [-1, 1]);
pair(blue_master, beer); # Nicht das Deutsche Bier trinken? Huh.
pair(Deutsch, prince);
pair(Norske, blue, [-1, 1]);
pair(water, blend, [-1, 1]);
# "zebra lives *somewhere* relative to the Brit". It has no effect on
# the logic. It's here just to make sure the code will insert a zebra
# somewhere in the table (after all other conditions are met) so the
# final print-out shows it. (the C code can be better structured, but
# meh, I ain't reading it, so who cares).
pair(zebra, AEnglisk, [ -4 .. 4 ]);
# write C code. If it's ugly to you: I didn't write; Perl did.
make_c;
perl test.pl | gcc -Wall -x c -; ./a.out):0 dunhill cats yellow water Norske 1 blend horse blue tea Danske 2 pall_mall birds red milk AEnglisk 3 prince zebra green coffee Deutsch 4 blue_master dog white beer Svensk
[edit] C#
// Solve Zebra Puzzle
//
// Nigel Galloway. May 26th., 2012
//
using Microsoft.SolverFoundation.Solvers;
namespace Zebra
{
class Zebra
{
static readonly int[] Houses = new int[] {0,1,2,3,4};
enum Colour { Blue, Green, White, Red, Yellow };
enum Drink { Beer, Coffee, Milk, Tea, Water };
enum Nationality { English, Danish, German, Norwegian, Swedish };
enum Smoke { Blend, BlueMaster, Dunhill, PallMall, Prince };
enum Pet { Bird, Cat, Dog, Horse, Zebra };
static CspTerm[][] U(ConstraintSystem S)
{
CspTerm[][] ret = S.CreateBooleanArray(new object(), Houses.Length, Houses.Length);
for (int i = 0; i < Zebra.Houses.Length; i++)
{
CspTerm[] r = S.CreateBooleanVector(new object(), Houses.Length); ;
CspTerm[] c = S.CreateBooleanVector(new object(), Houses.Length); ;
for (int j = 0; j < Houses.Length; j++)
{
r[j] = ret[i][j];
c[j] = ret[j][i];
}
S.AddConstraints(S.Equal(1, S.Sum(r)));
S.AddConstraints(S.Equal(1, S.Sum(c)));
}
return ret;
}
static int P(ConstraintSolverSolution soln, CspTerm[][] x, int house)
{
object h;
foreach(int i in Houses)
{
soln.TryGetValue(x[house][i], out h);
if ((int)h == 1)
{
return i;
}
}
return 0;
}
static void Main(string[] args)
{
ConstraintSystem K = ConstraintSystem.CreateSolver();
CspTerm[][] colour = U(K);
CspTerm[][] drink = U(K);
CspTerm[][] nationality = U(K);
CspTerm[][] smoke = U(K);
CspTerm[][] pet = U(K);
K.AddConstraints(
K.Equal(colour[1][(int)Colour.White], colour[0][(int)Colour.Green]),
K.Equal(0, colour[0][(int)Colour.White]),
K.Equal(1, drink[2][(int)Drink.Milk]),
K.Equal(1, nationality[0][(int)Nationality.Norwegian]),
K.Greater(1, K.Sum(smoke[0][(int)Smoke.Blend], pet[0][(int)Pet.Cat]) - K.Sum(smoke[1][(int)Smoke.Blend], pet[1][(int)Pet.Cat])),
K.Greater(1, K.Sum(smoke[4][(int)Smoke.Blend], pet[4][(int)Pet.Cat]) - K.Sum(smoke[3][(int)Smoke.Blend], pet[3][(int)Pet.Cat])),
K.Greater(1, K.Sum(smoke[0][(int)Smoke.Blend], drink[0][(int)Drink.Water]) - K.Sum(smoke[1][(int)Smoke.Blend], drink[1][(int)Drink.Water])),
K.Greater(1, K.Sum(smoke[4][(int)Smoke.Blend], drink[4][(int)Drink.Water]) - K.Sum(smoke[3][(int)Smoke.Blend], drink[3][(int)Drink.Water])),
K.Greater(1, K.Sum(smoke[0][(int)Smoke.Dunhill], pet[0][(int)Pet.Horse]) - K.Sum(smoke[1][(int)Smoke.Dunhill], pet[1][(int)Pet.Horse])),
K.Greater(1, K.Sum(smoke[4][(int)Smoke.Dunhill], pet[4][(int)Pet.Horse]) - K.Sum(smoke[3][(int)Smoke.Dunhill], pet[3][(int)Pet.Horse])),
K.Greater(1, K.Sum(nationality[0][(int)Nationality.Norwegian], colour[0][(int)Colour.Blue]) - K.Sum(nationality[1][(int)Nationality.Norwegian], colour[1][(int)Colour.Blue])),
K.Greater(1, K.Sum(nationality[4][(int)Nationality.Norwegian], colour[4][(int)Colour.Blue]) - K.Sum(nationality[3][(int)Nationality.Norwegian], colour[3][(int)Colour.Blue]))
);
for (int h = 1; h < 4; h++)
{
K.AddConstraints(
K.Equal(colour[h+1][(int)Colour.White], colour[h][(int)Colour.Green]),
K.Greater(1, K.Sum(smoke[h][(int)Smoke.Blend], pet[h][(int)Pet.Cat]) -
K.Sum(smoke[h - 1][(int)Smoke.Blend], smoke[h + 1][(int)Smoke.Blend], pet[h - 1][(int)Pet.Cat], pet[h + 1][(int)Pet.Cat])),
K.Greater(1, K.Sum(smoke[h][(int)Smoke.Dunhill], pet[h][(int)Pet.Horse]) -
K.Sum(smoke[h - 1][(int)Smoke.Dunhill], smoke[h + 1][(int)Smoke.Dunhill], pet[h - 1][(int)Pet.Horse], pet[h + 1][(int)Pet.Horse])),
K.Greater(1, K.Sum(smoke[h][(int)Smoke.Blend], drink[h][(int)Drink.Water]) -
K.Sum(smoke[h - 1][(int)Smoke.Blend], smoke[h + 1][(int)Smoke.Blend], drink[h - 1][(int)Drink.Water], drink[h+1][(int)Drink.Water])),
K.Greater(1, K.Sum(nationality[h][(int)Nationality.Norwegian], colour[h][(int)Colour.Blue]) -
K.Sum(nationality[h-1][(int)Nationality.Norwegian], nationality[h+1][(int)Nationality.Norwegian], colour[h-1][(int)Colour.Blue], colour[h+1][(int)Colour.Blue]))
);
}
foreach (int h in Houses)
{
K.AddConstraints(
K.Equal(colour[h][(int)Colour.Red], nationality[h][(int)Nationality.English]),
K.Equal(pet[h][(int)Pet.Dog], nationality[h][(int)Nationality.Swedish]),
K.Equal(drink[h][(int)Drink.Tea], nationality[h][(int)Nationality.Danish]),
K.Equal(drink[h][(int)Drink.Coffee], colour[h][(int)Colour.Green]),
K.Equal(smoke[h][(int)Smoke.PallMall], pet[h][(int)Pet.Bird]),
K.Equal(smoke[h][(int)Smoke.Dunhill], colour[h][(int)Colour.Yellow]),
K.Equal(smoke[h][(int)Smoke.BlueMaster], drink[h][(int)Drink.Beer]),
K.Equal(smoke[h][(int)Smoke.Prince], nationality[h][(int)Nationality.German])
);
}
ConstraintSolverSolution soln = K.Solve(new ConstraintSolverParams());
System.Console.WriteLine("House Colour Drink Nationality Smokes Pet");
System.Console.WriteLine("_____ ______ _____ ___________ ______ ___");
foreach (int h in Houses)
{
System.Console.WriteLine("{0,5} {1,-6} {2,-6} {3,-11} {4,-10} {5,-10}",
h+1, (Colour)P(soln, colour, h), (Drink)P(soln, drink, h), (Nationality)P(soln, nationality, h), (Smoke)P(soln, smoke, h), (Pet)P(soln, pet, h));
}
System.Console.ReadLine();
}
}
}
Produces:
House Colour Drink Nationality Smokes Pet
_____ ______ _____ ___________ ______ ___
1 Yellow Water Norwegian Dunhill Cat
2 Blue Tea Danish Blend Horse
3 Red Milk English PallMall Bird
4 Green Coffee German Prince Zebra
5 White Beer Swedish BlueMaster Dog
[edit] D
Most foreach loops in this program are static.
import std.stdio, std.traits, std.algorithm, std.math;
enum Content { Beer, Coffee, Milk, Tea, Water,
Danish, English, German, Norwegian, Swedish,
Blue, Green, Red, White, Yellow,
Blend, BlueMaster, Dunhill, PallMall, Prince,
Bird, Cat, Dog, Horse, Zebra }
enum Test { Drink, Person, Color, Smoke, Pet }
enum House { One, Two, Three, Four, Five }
alias Content[EnumMembers!Test.length][EnumMembers!House.length] TM;
bool finalChecks(in ref TM M) pure nothrow {
int diff(in Content a, in Content b, in Test ca, in Test cb)
nothrow {
foreach (immutable h1; EnumMembers!House)
foreach (immutable h2; EnumMembers!House)
if (M[ca][h1] == a && M[cb][h2] == b)
return h1 - h2;
assert(0); // Useless but required.
}
with (Content) with (Test) { // Braces required (8414).
return abs(diff(Norwegian, Blue, Person, Color)) == 1 &&
diff(Green, White, Color, Color) == -1 &&
abs(diff(Horse, Dunhill, Pet, Smoke)) == 1 &&
abs(diff(Water, Blend, Drink, Smoke)) == 1 &&
abs(diff(Blend, Cat, Smoke, Pet)) == 1;
}
}
bool constrained(in ref TM M, in Test atest) pure nothrow {
with (Content) with (Test) with (House)
final switch (atest) {
case Drink:
return M[Drink][Three] == Milk;
case Person:
foreach (immutable h; EnumMembers!House)
if ((M[Person][h] == Norwegian && h != One) ||
(M[Person][h] == Danish && M[Drink][h] != Tea))
return false;
return true;
case Color:
foreach (immutable h; EnumMembers!House)
if ((M[Person][h] == English && M[Color][h] != Red) ||
(M[Drink][h] == Coffee && M[Color][h] != Green))
return false;
return true;
case Smoke:
foreach (immutable h; EnumMembers!House)
if ((M[Color][h] == Yellow && M[Smoke][h] != Dunhill) ||
(M[Smoke][h] == BlueMaster && M[Drink][h] != Beer) ||
(M[Person][h] == German && M[Smoke][h] != Prince))
return false;
return true;
case Pet:
foreach (immutable h; EnumMembers!House)
if ((M[Person][h] == Swedish && M[Pet][h] != Dog) ||
(M[Smoke][h] == PallMall && M[Pet][h] != Bird))
return false;
return finalChecks(M);
}
}
void show(in ref TM M) {
foreach (h; EnumMembers!House) {
writef("%5s: ", h);
foreach (immutable t; EnumMembers!Test)
writef("%10s ", M[t][h]);
writeln();
}
}
void solve(ref TM M, in Test t, in size_t n) {
if (n == 1 && constrained(M, t)) {
if (t < 4) {
solve(M, [EnumMembers!Test][t + 1], 5);
} else {
show(M);
return;
}
}
foreach (immutable i; 0 .. n) {
solve(M, t, n - 1);
swap(M[t][n % 2 ? 0 : i], M[t][n - 1]);
}
}
void main() {
TM M;
foreach (immutable t; EnumMembers!Test)
foreach (immutable h; EnumMembers!House)
M[t][h] = EnumMembers!Content[t * 5 + h];
solve(M, Test.Drink, 5);
}
- Output:
One: Water Norwegian Yellow Dunhill Cat Two: Tea Danish Blue Blend Horse Three: Milk English Red PallMall Bird Four: Coffee German Green Prince Zebra Five: Beer Swedish White BlueMaster Dog
Run-time about 0.04 seconds.
[edit] Alternative Version
import std.stdio, std.math, std.traits, std.typetuple;
const(T[N][]) permutationsFixed(T, size_t N)(in T[N] items)
pure nothrow {
const(T[N])[] result;
T[N] row;
void perms(in T[] s, in T[] prefix=null) nothrow {
if (s.length)
foreach (immutable i, immutable c; s)
perms(s[0 .. i] ~ s[i+1 .. $], prefix ~ c);
else {
row[] = prefix[];
result ~= row;
}
}
perms(items);
return result;
}
enum Number : uint { One, Two, Three, Four, Five }
enum Color : uint { Red, Green, Blue, White, Yellow }
enum Drink : uint { Milk, Coffee, Water, Beer, Tea }
enum Smoke : uint { PallMall, Dunhill, Blend, BlueMaster, Prince }
enum Pet : uint { Dog, Cat, Zebra, Horse, Bird }
enum Nation : uint { British, Swedish, Danish, Norvegian, German }
bool isPossible(immutable(Number[5])* number,
immutable(Color[5])* color=null,
immutable(Drink[5])* drink=null,
immutable(Smoke[5])* smoke=null,
immutable(Pet[5])* pet=null
) pure nothrow {
if ((number && (*number)[Nation.Norvegian] != Number.One) ||
(color && (*color)[Nation.British] != Color.Red) ||
(drink && (*drink)[Nation.Danish] != Drink.Tea) ||
(smoke && (*smoke)[Nation.German] != Smoke.Prince) ||
(pet && (*pet)[Nation.Swedish] != Pet.Dog))
return false;
if (!number || !color || !drink || !smoke || !pet)
return true;
foreach (immutable i; 0 .. 5) {
if (((*color)[i] == Color.Green && (*drink)[i] != Drink.Coffee) ||
((*smoke)[i] == Smoke.PallMall && (*pet)[i] != Pet.Bird) ||
((*color)[i] == Color.Yellow && (*smoke)[i] != Smoke.Dunhill) ||
((*number)[i] == Number.Three && (*drink)[i] != Drink.Milk) ||
((*smoke)[i] == Smoke.BlueMaster && (*drink)[i] != Drink.Beer)||
((*color)[i] == Color.Blue && (*number)[i] != Number.Two))
return false;
foreach (immutable j; 0 .. 5) {
if ((*color)[i] == Color.Green && (*color)[j] == Color.White &&
(*number)[j] - (*number)[i] != 1)
return false;
immutable int diff = abs((*number)[i] - (*number)[j]);
if (((*smoke)[i] == Smoke.Blend &&
(*pet)[j] == Pet.Cat && diff != 1) ||
((*pet)[i] == Pet.Horse &&
(*smoke)[j] == Smoke.Dunhill && diff != 1) ||
((*smoke)[i] == Smoke.Blend &&
(*drink)[j] == Drink.Water && diff != 1))
return false;
}
}
return true;
}
void main() {
static immutable perms = permutationsFixed!(uint, 5)([0,1,2,3,4]);
// Not nice casts.
static permsNumber = cast(immutable(Number[5][]))perms;
static permsColor = cast(immutable(Color[5][]))perms;
static permsDrink = cast(immutable(Drink[5][]))perms;
static permsSmoke = cast(immutable(Smoke[5][]))perms;
static permsPet = cast(immutable(Pet[5][]))perms;
immutable nation = [EnumMembers!Nation];
foreach (immutable ref number; permsNumber)
if (isPossible(&number))
foreach (immutable ref color; permsColor)
if (isPossible(&number, &color))
foreach (immutable ref drink; permsDrink)
if (isPossible(&number, &color, &drink))
foreach (immutable ref smoke; permsSmoke)
if (isPossible(&number, &color, &drink, &smoke))
foreach (immutable ref pet; permsPet)
if (isPossible(&number,&color,&drink,&smoke,&pet)) {
writeln("Found a solution:");
foreach (x; TypeTuple!(nation, number, color,
drink, smoke, pet))
writefln("%6s: %12s%12s%12s%12s%12s",
(Unqual!(typeof(x[0]))).stringof,
x[0], x[1], x[2], x[3], x[4]);
writeln();
}
}
- Output:
Found a solution: Nation: British Swedish Danish Norvegian German Number: Three Five Two One Four Color: Red White Blue Yellow Green Drink: Milk Beer Tea Water Coffee Smoke: PallMall BlueMaster Blend Dunhill Prince Pet: Bird Dog Horse Cat Zebra
Run-time about 0.72 seconds.
[edit] Haskell
import Control.Applicative ((<$>), (<*>))
import Control.Monad
import Data.List ((\\), isInfixOf)
-- types
data House = House
{ color :: Color
, man :: Man
, pet :: Pet
, drink :: Drink
, smoke :: Smoke
}
deriving (Eq, Show)
data Color = Red | Green | Blue | Yellow | White
deriving (Eq, Show, Enum, Bounded)
data Man = Eng | Swe | Dan | Nor | Deu
deriving (Eq, Show, Enum, Bounded)
data Pet = Dog | Birds | Cats | Horse | Zebra
deriving (Eq, Show, Enum, Bounded)
data Drink = Coffee | Tea | Milk | Beer | Water
deriving (Eq, Show, Enum, Bounded)
data Smoke = PallMall | Dunhill | Blend | BlueMaster | Prince
deriving (Eq, Show, Enum, Bounded)
main :: IO ()
main = mapM_ print . reverse $ head solutions
solutions :: [[House]]
solutions = do
hs <- foldM (\houses pos -> do
h <- house houses
forM_ (checks pos)
$ \(p,q) -> when (p h) (guard $ q h)
>> when (q h) (guard $ p h)
return (h:houses)) [] [1..5]
forM_ postChecks $ guard . ($ hs)
return hs
house :: [House] -> [House]
house houses =
House <$> iter color <*> iter man <*> iter pet <*> iter drink <*> iter smoke
where
iter getter = [minBound ..] \\ map getter houses
-- immediate checks
checks :: Int -> [(House -> Bool, House -> Bool)]
checks pos =
[ (man `is` Eng , color `is` Red ) -- 2
, (man `is` Swe , pet `is` Dog ) -- 3
, (man `is` Dan , drink `is` Tea ) -- 4
, (color `is` Green , drink `is` Coffee ) -- 6
, (pet `is` Birds , smoke `is` PallMall ) -- 7
, (color `is` Yellow, smoke `is` Dunhill ) -- 8
, (const $ pos == 3 , drink `is` Milk ) -- 9
, (const $ pos == 1 , man `is` Nor ) -- 10
, (drink `is` Beer , smoke `is` BlueMaster) -- 13
, (man `is` Deu , smoke `is` Prince ) -- 14
]
-- final checks
postChecks :: [[House] -> Bool]
postChecks =
-- NOTE: list of houses is generated "from tail"
[ ([White, Green] `isInfixOf`) . map color -- 5
, (smoke `is` Blend ) `nextTo` (pet `is` Cats ) -- 11
, (smoke `is` Dunhill) `nextTo` (pet `is` Horse) -- 12
, (color `is` Blue ) `nextTo` (man `is` Nor ) -- 15
, (smoke `is` Blend ) `nextTo` (drink `is` Water) -- 16
]
nextTo :: (House -> Bool) -> (House -> Bool) -> [House] -> Bool
nextTo p q hs
| (_:h:_) <- dropWhile (not . match) hs = match h
| otherwise = False
where
match h = p h || q h
is :: Eq a => (House -> a) -> a -> House -> Bool
getter `is` value = (== value) . getter
- Output:
House {color = Yellow, man = Nor, pet = Cats, drink = Water, smoke = Dunhill}
House {color = Blue, man = Dan, pet = Horse, drink = Tea, smoke = Blend}
House {color = Red, man = Eng, pet = Birds, drink = Milk, smoke = PallMall}
House {color = Green, man = Deu, pet = Zebra, drink = Coffee, smoke = Prince}
House {color = White, man = Swe, pet = Dog, drink = Beer, smoke = BlueMaster}
[edit] J
Propositions 1 .. 16 without 9,10 and15
ehs=: 5$a:
cr=: (('English';'red') 0 3} ehs);<('Dane';'tea') 0 2}ehs
cr=: cr, (('German';'Prince') 0 4}ehs);<('Swede';'dog') 0 1 }ehs
cs=: <('PallMall';'birds') 4 1}ehs
cs=: cs, (('yellow';'Dunhill') 3 4}ehs);<('BlueMaster';'beer') 4 2}ehs
lof=: (('coffee';'green')2 3}ehs);<(<'white')3}ehs
next=: <((<'Blend') 4 }ehs);<(<'water')2}ehs
next=: next,<((<'Blend') 4 }ehs);<(<'cats')1}ehs
next=: next,<((<'Dunhill') 4}ehs);<(<'horse')1}ehs
Example
lof
┌─────────────────┬───────────┐
│┌┬┬──────┬─────┬┐│┌┬┬┬─────┬┐│
││││coffee│green│││││││white│││
│└┴┴──────┴─────┴┘│└┴┴┴─────┴┘│
└─────────────────┴───────────┘
Collections of all variants of the propositions:
hcr=: (<ehs),. (A.~i.@!@#)cr
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.
houses=: ((<'Norwegian') 0}ehs);((<'blue') 3 }ehs);((<'milk') 2}ehs);ehs;<ehs
- Output:
houses
┌───────────────┬──────────┬──────────┬──────┬──────┐
│┌─────────┬┬┬┬┐│┌┬┬┬────┬┐│┌┬┬────┬┬┐│┌┬┬┬┬┐│┌┬┬┬┬┐│
││Norwegian││││││││││blue││││││milk││││││││││││││││││
│└─────────┴┴┴┴┘│└┴┴┴────┴┘│└┴┴────┴┴┘│└┴┴┴┴┘│└┴┴┴┴┘│
└───────────────┴──────────┴──────────┴──────┴──────┘
Set of proposition variants:
constraints=: hcr;hcs;hlof;<hnext
The worker and its helper verbs
select=: ~.@(,: #~ ,&(0~:#))
filter=: #~*./@:(2>#S:0)"1
compose=: [: filter f. [: ,/ select f. L:0"1"1 _
solve=: 4 :0
h=. ,:x
whilst. 0=# z do.
for_e. y do. h=. h compose > e end.
z=.(#~1=[:+/"1 (0=#)S:0"1) h=.~. h
end.
)
- Output:
>"0 houses solve constraints
┌─────────┬─────┬──────┬──────┬──────────┐
│Norwegian│cats │water │yellow│Dunhill │
├─────────┼─────┼──────┼──────┼──────────┤
│Dane │horse│tea │blue │Blend │
├─────────┼─────┼──────┼──────┼──────────┤
│English │birds│milk │red │PallMall │
├─────────┼─────┼──────┼──────┼──────────┤
│German │ │coffee│green │Prince │
├─────────┼─────┼──────┼──────┼──────────┤
│Swede │dog │beer │white │BlueMaster│
└─────────┴─────┴──────┴──────┴──────────┘
So, the German owns the zebra.
Alternative
A longer running solver by adding the zebra variants.
zebra=: (-i.5)|."0 1 (<(<'zebra') 1}ehs),4$<ehs
solve3=: 4 :0
p=. *./@:((0~:#)S:0)
f=. [:~.&.> [: compose&.>~/y&, f.
z=. f^:(3>[:#(#~p"1)&>)^:_ <,:x
>"0 (#~([:*./[:;[:<@({.~:}.)\.;)"1)(#~p"1); z
)
- Output:
houses solve3 constraints,<zebra
┌─────────┬─────┬──────┬──────┬──────────┐
│Norwegian│cats │water │yellow│Dunhill │
├─────────┼─────┼──────┼──────┼──────────┤
│Dane │horse│tea │blue │Blend │
├─────────┼─────┼──────┼──────┼──────────┤
│English │birds│milk │red │PallMall │
├─────────┼─────┼──────┼──────┼──────────┤
│German │zebra│coffee│green │Prince │
├─────────┼─────┼──────┼──────┼──────────┤
│Swede │dog │beer │white │BlueMaster│
└─────────┴─────┴──────┴──────┴──────────┘
[edit] Perl
Basically the same idea as C, though of course it's much easier to have Perl generate Perl code.
#!/usr/bin/perl
use utf8;
use strict;
binmode STDOUT, ":utf8";
my (@tgt, %names);
sub setprops {
my %h = @_;
my @p = keys %h;
for my $p (@p) {
my @v = @{ $h{$p} };
@tgt = map(+{idx=>$_-1, map{ ($_, undef) } @p}, 1 .. @v)
unless @tgt;
$names{$_} = $p for @v;
}
}
my $solve = sub {
for my $i (@tgt) {
printf("%12s", ucfirst($i->{$_} // "¿Qué?"))
for reverse sort keys %$i;
print "\n";
}
"there is only one" # <--- change this to a false value to find all solutions (if any)
};
sub pair {
my ($a, $b, @v) = @_;
if ($a =~ /^(\d+)$/) {
$tgt[$1]{ $names{$b} } = $b;
return;
}
@v = (0) unless @v;
my %allowed;
$allowed{$_} = 1 for @v;
my ($p1, $p2) = ($names{$a}, $names{$b});
my $e = $solve;
$solve = sub { # <--- sorta like how TeX \let...\def macro
my ($x, $y);
($x) = grep { $_->{$p1} eq $a } @tgt;
($y) = grep { $_->{$p2} eq $b } @tgt;
$x and $y and
return $allowed{ $x->{idx} - $y->{idx} } && $e->();
my $try_stuff = sub {
my ($this, $p, $v, $sign) = @_;
for (@v) {
my $i = $this->{idx} + $sign * $_;
next unless $i >= 0 && $i < @tgt && !$tgt[$i]{$p};
local $tgt[$i]{$p} = $v;
$e->() and return 1;
}
return
};
$x and return $try_stuff->($x, $p2, $b, 1);
$y and return $try_stuff->($y, $p1, $a, -1);
for $x (@tgt) {
next if $x->{$p1};
local $x->{$p1} = $a;
$try_stuff->($x, $p2, $b, 1) and return 1;
}
};
}
# ---- above should be generic for all similar puzzles ---- #
# ---- below: per puzzle setup ---- #
# property names and values
setprops (
# Svensk n. a Swede, not a swede (kålrot).
# AEnglisk (from middle Viking "Æŋløsåksen") n. a Brit.
'Who' => [ qw(Deutsch Svensk Norske Danske AEnglisk) ],
'Pet' => [ qw(birds dog horse zebra cats) ],
'Drink' => [ qw(water tea milk beer coffee) ],
'Smoke' => [ qw(dunhill blue_master prince blend pall_mall) ],
'Color' => [ qw(red green yellow white blue) ]
);
# constraints
pair qw( AEnglisk red );
pair qw( Svensk dog );
pair qw( Danske tea );
pair qw( green white 1 ); # "to the left of" can mean either 1 or -1: ambiguous
pair qw( coffee green );
pair qw( pall_mall birds );
pair qw( yellow dunhill );
pair qw( 2 milk );
pair qw( 0 Norske );
pair qw( blend cats -1 1 );
pair qw( horse dunhill -1 1 );
pair qw( blue_master beer ); # Nicht das Deutsche Bier trinken? Huh.
pair qw( Deutsch prince );
pair qw( Norske blue -1 1 );
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
'Who' => [ qw(baker cooper fletcher miller smith) ],
'Level' => [ qw(one two three four five) ];
# constraints
pair qw(0 one);
pair qw(1 two);
pair qw(2 three);
pair qw(3 four);
pair qw(4 five);
pair qw(baker five -4 -3 -2 -1 1 2 3 4);
pair qw(cooper one -4 -3 -2 -1 1 2 3 4);
pair qw(fletcher one -4 -3 -2 -1 1 2 3 4);
pair qw(fletcher five -4 -3 -2 -1 1 2 3 4);
pair qw(miller cooper -1 -2 -3 -4);
pair qw(smith fletcher 4 3 2 -2 -3 -4);
pair qw(cooper fletcher 4 3 2 -2 -3 -4);
$solve->();
[edit] PicoLisp
(be match (@House @Person @Drink @Pet @Cigarettes)
(permute (red blue green yellow white) @House)
(left-of @House white @House green)
(permute (Norwegian English Swede German Dane) @Person)
(has @Person English @House red)
(equal @Person (Norwegian . @))
(next-to @Person Norwegian @House blue)
(permute (tea coffee milk beer water) @Drink)
(has @Drink tea @Person Dane)
(has @Drink coffee @House green)
(equal @Drink (@ @ milk . @))
(permute (dog birds cats horse zebra) @Pet)
(has @Pet dog @Person Swede)
(permute (Pall-Mall Dunhill Blend Blue-Master Prince) @Cigarettes)
(has @Cigarettes Pall-Mall @Pet birds)
(has @Cigarettes Dunhill @House yellow)
(next-to @Cigarettes Blend @Pet cats)
(next-to @Cigarettes Dunhill @Pet horse)
(has @Cigarettes Blue-Master @Drink beer)
(has @Cigarettes Prince @Person German)
(next-to @Drink water @Cigarettes Blend) )
(be has ((@A . @X) @A (@B . @Y) @B))
(be has ((@ . @X) @A (@ . @Y) @B)
(has @X @A @Y @B) )
(be right-of ((@A . @X) @A (@ @B . @Y) @B))
(be right-of ((@ . @X) @A (@ . @Y) @B)
(right-of @X @A @Y @B) )
(be left-of ((@ @A . @X) @A (@B . @Y) @B))
(be left-of ((@ . @X) @A (@ . @Y) @B)
(left-of @X @A @Y @B) )
(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:
(pilog '((match @House @Person @Drink @Pet @Cigarettes))
(let Fmt (-8 -11 -8 -7 -11)
(tab Fmt "HOUSE" "PERSON" "DRINKS" "HAS" "SMOKES")
(mapc '(@ (pass tab Fmt))
@House @Person @Drink @Pet @Cigarettes ) ) )
Output:
HOUSE PERSON DRINKS HAS SMOKES yellow Norwegian water cats Dunhill blue Dane tea horse Blend red English milk birds Pall-Mall green German coffee zebra Prince white Swede beer dog Blue-Master
[edit] Prolog
In Prolog we can specify the domain by selecting elements from it, making mutually exclusive choices for efficiency:
select([A|As],S):- select(A,S,S1),select(As,S1).
select([],_).
next_to(A,B,C):- left_of(A,B,C) ; left_of(B,A,C).
left_of(A,B,C):- append(_,[A,B|_],C).
zebra(Owns, HS):- % color,nation,pet,drink,smokes
HS = [h(_,norwegian,_,_,_),_,h(_,_,_,milk,_),_,_],
select( [h(red,englishman,_,_,_),h(_,swede,dog,_,_),h(_,dane,_,tea,_),
h(_,german,_,_,prince)], HS),
select( [h(_,_,birds,_,pallmall),h(yellow,_,_,_,dunhill),
h(_,_,_,beer,bluemaster)], HS),
left_of( h(green,_,_,coffee,_),h(white,_,_,_,_), HS),
next_to( h(_,_,_,_,dunhill), h(_,_,horse,_,_), HS),
next_to( h(_,_,_,_,blend), h(_,_,cats, _,_), HS),
next_to( h(_,_,_,_,blend), h(_,_,_,water,_), HS),
next_to( h(_,norwegian,_,_,_), h(blue,_,_,_,_), HS),
member( h(_,Owns,zebra,_,_), HS).
:- zebra(Who, HS), maplist(writeln,HS), nl, write(Who), nl, nl, fail
;
write('No more solutions.').
Output:
h(yellow, norwegian, cats, water, dunhill) h(blue, dane, horse, tea, blend) h(red, englishman, birds, milk, pallmall) h(green, german, zebra, coffee, prince) h(white, swede, dog, beer, bluemaster) german No more solutions.
Works with SWI-Prolog. More verbose line-for-line translation of the specification works as well.
[edit] Python
import psyco; psyco.full()
class Content: elems= """Beer Coffee Milk Tea Water
Danish English German Norwegian Swedish
Blue Green Red White Yellow
Blend BlueMaster Dunhill PallMall Prince
Bird Cat Dog Horse Zebra""".split()
class Test: elems= "Drink Person Color Smoke Pet".split()
class House: elems= "One Two Three Four Five".split()
for c in (Content, Test, House):
c.values = range(len(c.elems))
for i, e in enumerate(c.elems):
exec "%s.%s = %d" % (c.__name__, e, i)
def finalChecks(M):
def diff(a, b, ca, cb):
for h1 in House.values:
for h2 in House.values:
if M[ca][h1] == a and M[cb][h2] == b:
return h1 - h2
assert False
return abs(diff(Content.Norwegian, Content.Blue,
Test.Person, Test.Color)) == 1 and \
diff(Content.Green, Content.White,
Test.Color, Test.Color) == -1 and \
abs(diff(Content.Horse, Content.Dunhill,
Test.Pet, Test.Smoke)) == 1 and \
abs(diff(Content.Water, Content.Blend,
Test.Drink, Test.Smoke)) == 1 and \
abs(diff(Content.Blend, Content.Cat,
Test.Smoke, Test.Pet)) == 1
def constrained(M, atest):
if atest == Test.Drink:
return M[Test.Drink][House.Three] == Content.Milk
elif atest == Test.Person:
for h in House.values:
if ((M[Test.Person][h] == Content.Norwegian and
h != House.One) or
(M[Test.Person][h] == Content.Danish and
M[Test.Drink][h] != Content.Tea)):
return False
return True
elif atest == Test.Color:
for h in House.values:
if ((M[Test.Person][h] == Content.English and
M[Test.Color][h] != Content.Red) or
(M[Test.Drink][h] == Content.Coffee and
M[Test.Color][h] != Content.Green)):
return False
return True
elif atest == Test.Smoke:
for h in House.values:
if ((M[Test.Color][h] == Content.Yellow and
M[Test.Smoke][h] != Content.Dunhill) or
(M[Test.Smoke][h] == Content.BlueMaster and
M[Test.Drink][h] != Content.Beer) or
(M[Test.Person][h] == Content.German and
M[Test.Smoke][h] != Content.Prince)):
return False
return True
elif atest == Test.Pet:
for h in House.values:
if ((M[Test.Person][h] == Content.Swedish and
M[Test.Pet][h] != Content.Dog) or
(M[Test.Smoke][h] == Content.PallMall and
M[Test.Pet][h] != Content.Bird)):
return False
return finalChecks(M)
def show(M):
for h in House.values:
print "%5s:" % House.elems[h],
for t in Test.values:
print "%10s" % Content.elems[M[t][h]],
def solve(M, t, n):
if n == 1 and constrained(M, t):
if t < 4:
solve(M, Test.values[t + 1], 5)
else:
show(M)
return
for i in xrange(n):
solve(M, t, n - 1)
M[t][0 if n % 2 else i], M[t][n - 1] = \
M[t][n - 1], M[t][0 if n % 2 else i]
def main():
M = [[None] * len(Test.elems) for _ in xrange(len(House.elems))]
for t in Test.values:
for h in House.values:
M[t][h] = Content.values[t * 5 + h]
solve(M, Test.Drink, 5)
main()
- Output:
One: Water Norwegian Yellow Dunhill Cat Two: Tea Danish Blue Blend Horse Three: Milk English Red PallMall Bird Four: Coffee German Green Prince Zebra Five: Beer Swedish White BlueMaster Dog
Runtime about 0.18 seconds.
[edit] Alternative Version
from itertools import permutations
import psyco
psyco.full()
class Number:elems= "One Two Three Four Five".split()
class Color: elems= "Red Green Blue White Yellow".split()
class Drink: elems= "Milk Coffee Water Beer Tea".split()
class Smoke: elems= "PallMall Dunhill Blend BlueMaster Prince".split()
class Pet: elems= "Dog Cat Zebra Horse Bird".split()
class Nation:elems= "British Swedish Danish Norvegian German".split()
for c in (Number, Color, Drink, Smoke, Pet, Nation):
for i, e in enumerate(c.elems):
exec "%s.%s = %d" % (c.__name__, e, i)
def is_possible(number, color, drink, smoke, pet):
if number and number[Nation.Norvegian] != Number.One:
return False
if color and color[Nation.British] != Color.Red:
return False
if drink and drink[Nation.Danish] != Drink.Tea:
return False
if smoke and smoke[Nation.German] != Smoke.Prince:
return False
if pet and pet[Nation.Swedish] != Pet.Dog:
return False
if not number or not color or not drink or not smoke or not pet:
return True
for i in xrange(5):
if color[i] == Color.Green and drink[i] != Drink.Coffee:
return False
if smoke[i] == Smoke.PallMall and pet[i] != Pet.Bird:
return False
if color[i] == Color.Yellow and smoke[i] != Smoke.Dunhill:
return False
if number[i] == Number.Three and drink[i] != Drink.Milk:
return False
if smoke[i] == Smoke.BlueMaster and drink[i] != Drink.Beer:
return False
if color[i] == Color.Blue and number[i] != Number.Two:
return False
for j in xrange(5):
if (color[i] == Color.Green and
color[j] == Color.White and
number[j] - number[i] != 1):
return False
diff = abs(number[i] - number[j])
if smoke[i] == Smoke.Blend and pet[j] == Pet.Cat and diff != 1:
return False
if pet[i]==Pet.Horse and smoke[j]==Smoke.Dunhill and diff != 1:
return False
if smoke[i]==Smoke.Blend and drink[j]==Drink.Water and diff!=1:
return False
return True
def show_row(t, data):
print "%6s: %12s%12s%12s%12s%12s" % (
t.__name__, t.elems[data[0]],
t.elems[data[1]], t.elems[data[2]],
t.elems[data[3]], t.elems[data[4]])
def main():
perms = list(permutations(range(5)))
for number in perms:
if is_possible(number, None, None, None, None):
for color in perms:
if is_possible(number, color, None, None, None):
for drink in perms:
if is_possible(number, color, drink, None, None):
for smoke in perms:
if is_possible(number, color, drink, smoke, None):
for pet in perms:
if is_possible(number, color, drink, smoke, pet):
print "Found a solution:"
show_row(Nation, range(5))
show_row(Number, number)
show_row(Color, color)
show_row(Drink, drink)
show_row(Smoke, smoke)
show_row(Pet, pet)
main()
Output:
Found a solution: Nation: British Swedish Danish Norvegian German Number: Three Five Two One Four Color: Red White Blue Yellow Green Drink: Milk Beer Tea Water Coffee Smoke: PallMall BlueMaster Blend Dunhill Prince Pet: Bird Dog Horse Cat Zebra
[edit] Racket
#lang racket
(require racklog)
(define %select
(%rel (x xs S S1)
[(x (cons x xs) xs)]
[(x (cons S xs) (cons S S1)) (%select x xs S1)]
[((cons x xs) S)
(%select x S S1)
(%select xs S1)]
[('() (_))]))
(define %next-to
(%rel (A B C)
[(A B C)
(%or (%left-of A B C)
(%left-of B A C))]))
(define %left-of
(%rel (A B C)
[(A B C) (%append (_) (cons A (cons B (_))) C)]))
(define %zebra
(%rel (Owns HS)
[(Owns HS)
(%is HS (list (list (_) 'norwegian (_) (_) (_))
(_)
(list (_) (_) (_) 'milk (_))
(_) (_)))
(%select (list (list 'red 'englishman (_) (_) (_))
(list (_) 'swede 'dog (_) (_))
(list (_) 'dane (_) 'tea (_))
(list (_) 'german (_) (_) 'prince))
HS)
(%select (list (list (_) (_) 'birds (_) 'pallmall)
(list 'yellow (_) (_) (_) 'dunhill)
(list (_) (_) (_) 'beer 'bluemaster))
HS)
(%left-of (list 'green (_) (_) 'coffee (_))
(list 'white (_) (_) (_) (_))
HS)
(%next-to (list (_) (_) (_) (_) 'dunhill)
(list (_) (_) 'horse (_) (_))
HS)
(%next-to (list (_) (_) (_) (_) 'blend)
(list (_) (_) 'cats (_) (_))
HS)
(%next-to (list (_) (_) (_) (_) 'blend)
(list (_) (_) (_) 'water (_))
HS)
(%next-to (list (_) 'norwegian (_) (_) (_))
(list 'blue (_) (_) (_) (_))
HS)
(%member (list (_) Owns 'zebra (_) (_)) HS)]))
(%which (Who HS) (%zebra Who HS))
Output:
'((Who . german) (HS (yellow norwegian cats water dunhill) (blue dane horse tea blend) (red englishman birds milk pallmall) (green german zebra coffee prince) (white swede dog beer bluemaster)))
[edit] Tcl
package require struct::list
# Implements the constants by binding them directly into the named procedures.
# This is much faster than the alternatives!
proc initConstants {args} {
global {}
set remap {}
foreach {class elems} {
Number {One Two Three Four Five}
Color {Red Green Blue White Yellow}
Drink {Milk Coffee Water Beer Tea}
Smoke {PallMall Dunhill Blend BlueMaster Prince}
Pet {Dog Cat Horse Bird Zebra}
Nation {British Swedish Danish Norwegian German}
} {
set i -1
foreach e $elems {lappend remap "\$${class}($e)" [incr i]}
set ($class) $elems
}
foreach procedure $args {
proc $procedure [info args $procedure] \
[string map $remap [info body $procedure]]
}
}
proc isPossible {number color drink smoke pet} {
if {[llength $number] && [lindex $number $Nation(Norwegian)] != $Number(One)} {
return false
} elseif {[llength $color] && [lindex $color $Nation(British)] != $Color(Red)} {
return false
} elseif {[llength $drink] && [lindex $drink $Nation(Danish)] != $Drink(Tea)} {
return false
} elseif {[llength $smoke] && [lindex $smoke $Nation(German)] != $Smoke(Prince)} {
return false
} elseif {[llength $pet] && [lindex $pet $Nation(Swedish)] != $Pet(Dog)} {
return false
}
if {!([llength $number] && [llength $color] && [llength $drink] && [llength $smoke] && [llength $pet])} {
return true
}
for {set i 0} {$i < 5} {incr i} {
if {[lindex $color $i] == $Color(Green) && [lindex $drink $i] != $Drink(Coffee)} {
return false
} elseif {[lindex $smoke $i] == $Smoke(PallMall) && [lindex $pet $i] != $Pet(Bird)} {
return false
} elseif {[lindex $color $i] == $Color(Yellow) && [lindex $smoke $i] != $Smoke(Dunhill)} {
return false
} elseif {[lindex $number $i] == $Number(Three) && [lindex $drink $i] != $Drink(Milk)} {
return false
} elseif {[lindex $smoke $i] == $Smoke(BlueMaster) && [lindex $drink $i] != $Drink(Beer)} {
return false
} elseif {[lindex $color $i] == $Color(Blue) && [lindex $number $i] != $Number(Two)} {
return false
}
for {set j 0} {$j < 5} {incr j} {
if {[lindex $color $i] == $Color(Green) && [lindex $color $j] == $Color(White) && [lindex $number $j] - [lindex $number $i] != 1} {
return false
}
set diff [expr {abs([lindex $number $i] - [lindex $number $j])}]
if {[lindex $smoke $i] == $Smoke(Blend) && [lindex $pet $j] == $Pet(Cat) && $diff != 1} {
return false
} elseif {[lindex $pet $i] == $Pet(Horse) && [lindex $smoke $j] == $Smoke(Dunhill) && $diff != 1} {
return false
} elseif {[lindex $smoke $i] == $Smoke(Blend) && [lindex $drink $j] == $Drink(Water) && $diff != 1} {
return false
}
}
}
return true
}
proc showRow {t data} {
upvar #0 ($t) elems
puts [format "%6s: %12s%12s%12s%12s%12s" $t \
[lindex $elems [lindex $data 0]] \
[lindex $elems [lindex $data 1]] \
[lindex $elems [lindex $data 2]] \
[lindex $elems [lindex $data 3]] \
[lindex $elems [lindex $data 4]]]
}
proc main {} {
set perms [struct::list permutations {0 1 2 3 4}]
foreach number $perms {
if {![isPossible $number {} {} {} {}]} continue
foreach color $perms {
if {![isPossible $number $color {} {} {}]} continue
foreach drink $perms {
if {![isPossible $number $color $drink {} {}]} continue
foreach smoke $perms {
if {![isPossible $number $color $drink $smoke {}]} continue
foreach pet $perms {
if {[isPossible $number $color $drink $smoke $pet]} {
puts "Found a solution:"
showRow Nation {0 1 2 3 4}
showRow Number $number
showRow Color $color
showRow Drink $drink
showRow Smoke $smoke
showRow Pet $pet
puts ""
}
}
}
}
}
}
}
initConstants isPossible
main
- Output:
Found a solution: Nation: British Swedish Danish Norwegian German Number: Three Five Two One Four Color: Red White Blue Yellow Green Drink: Milk Beer Tea Water Coffee Smoke: PallMall BlueMaster Blend Dunhill Prince Pet: Bird Dog Horse Cat Zebra
