Truth table for the zebra puzzle

Question

I'm reading "Computer Science distilled" book and I've faced a trouble. Author suggests to solve Einstein's "Zebra puzzle" through truth table, but I can't figure out how. I can't find starting conditions and variables. Do you have any ideas of the smallest table possible? I suppose I can create only a 6^6 version

Answer 1

Take a look at the code I wrote for the puzzle-solvers package. It was made to solve a similar question right here on SO. Since it's a very small package, you can probably see how the code is written quite easily.

The code is the Solver class, which maintains a matrix of values and provides the methods you need to set up relationships that automatically prune the underlying graph of contradictory edges.

You can follow along with a detailed description of the logic from the docs. This really explains how the matrix representation of the graph is used to record the relationships in the rules. The gist of it is that each rule either sets up a direct link between two categories, which prunes all the contradictory edges, or eliminates an edge, which has implications as well.

Answer 2

I'm the author of the book the OP mentioned. I didn't mean for the reader to use only a big truth table to solve the Zebra Puzzle, but rather, so use it as a tool to detect situations that can never happen, and to better direct the exploration process.

Using a big truth table with variables representing a house/attribute state, you can spot a variable that, if true, would imply a lot of relevant states. It's best to test these variables for finding logical contradictions than simply bruteforcing all the variables.

I wrote a detailed blog post explaining how to solve the Zebra puzzle using only simple inferences and boolean algebra, here: https://code.energy/solving-zebra-puzzle/

Answer 3

The MiniZinc script below shows how to encode the zebra puzzle in terms of 25 decision variables. Each of them has a value 1..5. In terms of Boolean variables, 25*3 = 75 bits would be needed.

A direct Boolean encoding as suggested by @Stanislav Kralin would require 5*5*5 = 125 Boolean decision variables.

A somewhat more elegant version can be found here. It exhibits the same number of decision variables.

%  Zebra Puzzle in MiniZinc
%  https://en.wikipedia.org/wiki/Zebra_Puzzle

%  for all_different()
include "globals.mzn";

%  Number of houses (cf. constraint 1.)
int: n = 5;
set of int: House = 1..5;

%  Nationalities
var House: English;
var House: Spaniard;
var House: Ukranian;
var House: Norwegian;
var House: Japanese;

%  Beverages
var House: Coffee;
var House: Tea;
var House: Milk;
var House: Orange_Juice;
var House: Water;

%  Pets
var House: Dog;
var House: Horse;
var House: Snail;
var House: Fox;
var House: Zebra;

%  House colors
var House: Red;
var House: Yellow;
var House: Ivory;
var House: Blue;
var House: Green;

%  Cigarette brands
var House: Old_Gold;
var House: Kools;
var House: Chesterfield;
var House: Lucky_Strike;
var House: Parliaments;

%  Explicit constraints
% 1. There are five houses.

% 2. The Englishman lives in the red house.
constraint English = Red;

% 3. The Spaniard owns the dog.
constraint Spaniard = Dog;

% 4. Coffee is drunk in the green house.
constraint Coffee = Green;

% 5. The Ukranian drinks tea.
constraint Ukranian = Tea;

% 6. The green house is immediately to the right of the ivory house.
constraint Green = (Ivory + 1);

% 7. The Old Gold smoker owns snails.
constraint Old_Gold = Snail;

% 8. Kools are smoked in the yellow house.
constraint Kools = Yellow;

% 9. Milk is drunk in the middle house.
constraint Milk = (n + 1)/2;

% 10. The Norwegian lives in the first house.
constraint Norwegian = 1;

% 11. The man who smokes Chesterfields lives in the house next to the man with the fox.
constraint abs(Chesterfield - Fox) = 1;

% 12. Kools are smoked in the house next to the house where the horse is kept.
constraint abs(Kools - Horse) = 1;

% 13. The Lucky Strike smoker drinks orange juice.
constraint Lucky_Strike = Orange_Juice;

% 14. The Japanese smokes Parliaments.
constraint Japanese = Parliaments;

% 15. The Norwegian lives next to the blue house.
constraint abs(Norwegian - Blue) = 1;

%  Implicit constraints
%  each of the five houses is painted a different color
constraint all_different([Red, Blue, Yellow, Green, Ivory]);

%  inhabitants are of different national extractions
constraint all_different([English, Spaniard, Ukranian, Norwegian, Japanese]);

%  inhabitants own different pets
constraint all_different([Dog, Horse, Snail, Fox, Zebra]);

%  inhabitants drink different beverages 
constraint all_different([Coffee, Tea, Milk, Orange_Juice, Water]);

%  inhabitants smoke different brands of American cigarets [sic]
constraint all_different([Old_Gold, Kools, Chesterfield, Lucky_Strike, Parliaments]);

solve satisfy;

function string: take(int: h, array[1..n-1] of House: x, array[House] of string: s) =
  if x[1] = h then s[1] 
  elseif x[2] = h then s[2] 
  elseif x[3] = h then s[3] 
  elseif x[4] = h then s[4] 
  else s[5] endif;

output ["\nColor       "] ++
       [ take(h, [fix(Red), fix(Blue), fix(Green), fix(Ivory)], 
                 ["red          ", "blue         ", "green        ", "ivory        ", "yellow       "])| h in House] ++
       ["\nNationality "] ++
       [ take(h, [fix(English), fix(Spaniard), fix(Ukranian), fix(Norwegian)],
                 ["English      ", "Spaniard     ", "Ukranian     ", "Norwegian    ", "Japanese     "])| h in House] ++
       ["\nPet         "] ++
       [ take(h, [fix(Dog), fix(Horse), fix(Snail), fix(Fox)],
                 ["Dog          ", "Horse        ", "Snail        ", "Fox          ", "Zebra        "])| h in House] ++
       ["\nBeverage    "] ++
       [ take(h, [fix(Coffee), fix(Tea), fix(Milk), fix(Orange_Juice)],
                 ["Coffee       ", "Tea          ", "Milk         ", "Orange Juice ", "Water        "])| h in House] ++
       ["\nCigarette   "] ++
       [ take(h, [fix(Old_Gold), fix(Kools), fix(Chesterfield), fix(Lucky_Strike)],
                 ["Old Gold     ", "Kools        ", "Chesterfield ", "Lucky Strike ", "Parliaments  "])| h in House];

Answer 4

A typical riddle can be viewed as a k×n matrix and then encoded with k×n² boolean variables like here. Consider a variable P_ijm to be true if — and only if — the (i,j)-entry in the matrix has value m.

Obviously, you need a SAT solver to solve a riddle encoded in this way. I suppose the author suggests you to use truth tables just ironically, or for pedagogical reasons, or he/she asks you to implement techniques used in SAT solvers.

In order to reduce the number of “terms” involved one have to model this puzzle in a (decidable) fragment of first-order logic, e.g. Horn clauses (Prolog) or description logic (OWL reasoners).

Another example of such a “propositional explosion” of the number of terms is the propositional pigeonhole principle.