Zebra puzzle

Zebra puzzle
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:

1. There are five houses.
2. The English man lives in the red house.
3. The Swede has a dog.
4. The Dane drinks tea.
5. The green house is immediately to the left of the white house.
6. They drink coffee in the green house.
7. The man who smokes Pall Mall has birds.
8. In the yellow house they smoke Dunhill.
9. In the middle house they drink milk.
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.
13. The man who smokes Blue Master drinks beer.
14. The German smokes Prince.
15. The Norwegian lives next to the blue house.
16. 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

Ada

Not the prettiest Ada, but its simple and very fast. Similar to my Dinesman's code, uses enums to keep things readable. <lang Ada>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;</lang>

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

BBC BASIC

Works with: BBC BASIC for Windows

<lang bbcbasic> 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</lang>

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

C

<lang c>#include <stdio.h>

1. 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 to make things quicker
              (ha[i][M] != English && ha[i][C] == Red ) ) )
           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;
           }
       }
   }
   return Invalid; // we only come here if none of the attr values assigned were valid

}

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;

}</lang> 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.

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. <lang perl>#!/usr/bin/perl

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 "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>

1. define N_ITEMS $l

struct item_t { int @k; } house[N_ITEMS] = Template: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 "

1. 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; }

1. ---- above should be generic for all similar puzzles ---- #

1. ---- below: per puzzle setup ---- #
2. 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) ] );

1. 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]);

1. "zebra lives *somewhere* relative to the Brit". It has no effect on
2. the logic. It's here just to make sure the code will insert a zebra
3. somewhere in the table (after all other conditions are met) so the
4. final print-out shows it. (the C code can be better structured, but
5. meh, I ain't reading it, so who cares).

pair(zebra, AEnglisk, [ -4 .. 4 ]);

1. write C code. If it's ugly to you: I didn't write; Perl did.

make_c;</lang>

output (ran as 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

C#

<lang csharp> // 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();
       }
   }

} </lang> 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

D

Translation of: Ada

Most foreach loops in this program are static. <lang d>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 (h1; EnumMembers!House)
     foreach (h2; EnumMembers!House)
       if (M[ca][h1] == a && M[cb][h2] == b)
         return h1 - h2;
   assert(0);
 }

 with (Content) with (Test)
   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 (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 (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 (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 (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 (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 (i; 0 .. n) {
   solve(M, t, n - 1);
   swap(M[t][n % 2 ? 0 : i], M[t][n - 1]);
 }

}

void main() {

 TM M;
 foreach (t; EnumMembers!Test)
   foreach (h; EnumMembers!House)
     M[t][h] = EnumMembers!Content[t * 5 + h];

 solve(M, Test.Drink, 5);

}</lang>

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.06 seconds or less.

Alternative Version

Translation of: Python

<lang d>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=[]) nothrow {
   if (s.length)
     foreach (i, 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 (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 (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]);
 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 (ref number; permsNumber)
   if (isPossible(&number))
     foreach (ref color; permsColor)
       if (isPossible(&number, &color))
         foreach (ref drink; permsDrink)
           if (isPossible(&number, &color, &drink))
             foreach (ref smoke; permsSmoke)
               if (isPossible(&number, &color, &drink, &smoke))
                 foreach (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();
                 }

}</lang>

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.76 seconds.

J

Propositions 1 .. 16 without 9,10 and15 <lang j>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</lang> Example <lang j> lof ┌─────────────────┬───────────┐ │┌┬┬──────┬─────┬┐│┌┬┬┬─────┬┐│ ││││coffee│green│││││││white│││ │└┴┴──────┴─────┴┘│└┴┴┴─────┴┘│ └─────────────────┴───────────┘</lang>

Collections of all variants of the propositions: <lang j>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</lang>

We start the row of houses with fixed properties 9, 10 and 15. <lang j>houses=: ((<'Norwegian') 0}ehs);((<'blue') 3 }ehs);((<'milk') 2}ehs);ehs;<ehs</lang>

Output:

<lang j> houses ┌───────────────┬──────────┬──────────┬──────┬──────┐ │┌─────────┬┬┬┬┐│┌┬┬┬────┬┐│┌┬┬────┬┬┐│┌┬┬┬┬┐│┌┬┬┬┬┐│ ││Norwegian││││││││││blue││││││milk││││││││││││││││││ │└─────────┴┴┴┴┘│└┴┴┴────┴┘│└┴┴────┴┴┘│└┴┴┴┴┘│└┴┴┴┴┘│ └───────────────┴──────────┴──────────┴──────┴──────┘</lang> Set of proposition variants: <lang j>constraints=: hcr;hcs;hlof;<hnext</lang> The worker and its helper verbs <lang j>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. )</lang>

Output:

<lang j> >"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│ └─────────┴─────┴──────┴──────┴──────────┘</lang> So, the German owns the zebra.

Alternative
A longer running solver by adding the zebra variants. <lang j>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 )</lang>

Output:

<lang j> 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│ └─────────┴─────┴──────┴──────┴──────────┘</lang>

Perl

Basically the same idea as C, though of course it's much easier to have Perl generate Perl code. <lang perl>#!/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; } }; }

1. ---- above should be generic for all similar puzzles ---- #

1. ---- below: per puzzle setup ---- #
2. 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) ] );

1. 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->();</lang>

Incidentally, the same logic can be used to solve the dwelling problem, if somewhat awkwardly: <lang perl>...

1. property names and values

setprops 'Who' => [ qw(baker cooper fletcher miller smith) ], 'Level' => [ qw(one two three four five) ];

1. 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->();</lang>

PicoLisp

<lang 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))</lang> Test: <lang PicoLisp>(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 ) ) )</lang>

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

Prolog

In Prolog we can specify the domain by selecting elements from it, making mutually exclusive choices for efficiency:

<lang Prolog>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.').</lang>

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.

Python

Translation of: D

<lang 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]],
   print

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()</lang>

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.

Alternative Version

<lang python>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)
                     print

main()</lang> 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

Tcl

Translation of: Python

Library: Tcllib (Package: struct::list)

<lang tcl>package require struct::list

1. Implements the constants by binding them directly into the named procedures.
2. 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</lang>

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