Definitions for Zebra and Sherlock

General Definitions

• arc consistency The domains of a variable V_i is such that for each constraint C_i,j V_i is consistent with the constraint for some permissible value of V_j for every value in the domain of V_i That is for every value x in D_i (the domain of i) there exists some y in D_j such that C_i,j is satisfied. It is important to note that arc consistency is directional (that is (V_i , V_j ) being arc consistent does not mean (V_j , V_i ) is arc consistent).
• binary constraint satisfaction problem The binary constraint satisfaction problem, as used in this paper, involves finding a solution such that a set of variables { V₁ , V₂ , … , V_n }, each having a domain D_i such that V_i takes on a value from D_i , does not conflict with a set of binary constraints { C_1,1 , C_1,2 , …, C_1,n , …, C_2,1 , C_2,2 , …, C_2,n , …, C_n,1 , C_n,2 , …, C_n,n } where C_i,j is a constraint (relation) between V_i and V_j that must be true, and if C_i,j is null there is no constraint between V_i and V_j .
• K-consistent Choose any K - 1 variables that satisfy the constraints among those variables. Then choose any Kth variable. If there exists a value for this variable that satisfies all the constraints among these K variables then the constraint problem can be said to be K consistent. Paraphrased from [Kumar92].

Problem Definitions

• The Zebra Problem Is a standard test for constraint satisfaction algorithms. In [Prosser93] it is defined as follows:
  • V₁ - V₅ correspond to five houses; Red, Blue, Yellow, Green, and Ivory, respectively.
  • V₆ - V₁₀ correspond to five brands of cigarettes; Old-Gold, Parliament, Kools, Lucky, and Chesterfield, respectively.
  • V₁₁ - V₁₅ correspond to five nationalities: Norwegian, Ukrainian, Englishman, Spaniard, and Japanese, respectively.
  • V₁₆ - V₂₀ correspond to five pets: Zebra, Dog, Horse, Fox, and Snails, respectively.
  • V₂₁ - V₂₅ correspond to five drinks: Coffee, Tea, Water, Milk, Orange Juice, respectively. This can be represented in a tabular format as follows:

  R	B	Y	G	I		R	B	Y	G	I		R	B	Y	G	I		R	B	Y	G	I		R	B	Y	G	I
  O	P	K	L	C		O	P	K	L	C		O	P	K	L	C		O	P	K	L	C		O	P	K	L	C
  N	U	E	S	J		N	U	E	S	J		N	U	E	S	J		N	U	E	S	J		N	U	E	S	J
  Z	D	H	F	S		Z	D	H	F	S		Z	D	H	F	S		Z	D	H	F	S		Z	D	H	F	S
  C	T	W	M	O		C	T	W	M	O		C	T	W	M	O		C	T	W	M	O		C	T	W	M	O

Zebra Table

All instances of the Zebra have the following constraints:

• Each house is of a different colour,
• and is inhabited by a single person,
• who smokes a unique brand of cigarettes,
• has a preferred drink,
• and owns a pet. In addition to these constraints each instance of the Zebra problem has a subset of all valid constraints for the instance’s solution. The valid constraints for the Zebra Problem are chosen from the set { V_i in-same-column-as V_j , V_i next-to V_j , V_i next-to-and-right-of V_j , and V_i = known-column } ¹ where the constraint is true for a give i and j.

For the purposes of the paper, the query is, “Who lives in which house, smokes which brand of cigarette, is a citizen of which country, owns which pet, and drinks which drink?” The benchmark Zebra problem has the following constraints:

• The Englishman lives in the Red house.
• The Spaniard owns a Dog.
• Coffee is drunk in the Green house.
• The Ukrainian drinks tea.
• The Green house is to the immediate right of the Ivory house.
• The Old-Gold smoker owns Snails.
• Kools are smoked in the Yellow house.
• Milk is drunk in the middle house.
• The Norwegian lives in the first house on the left.
• The Chesterfield smoker lives next to the Fox owner.
• Kools are smoked in the house next to the house where the Horse is kept.
• The Lucky smoker drinks Orange Juice.
• The Japanese smokes Parliament.
• The Norwegian lives next to the Blue house.
• The Sherlock Problem Is based on a computer game called Sherlock. It is a variation of the Zebra problem with six choices and rows and has additional types of constraints. It can be defined as follows:
  • V₁ - V₆ correspond to six houses; Red, Blue, Yellow, Green, and Ivory, and Brown respectively.
  • V₇ - V₁₂ correspond to six nationalities: Norwegian, Ukrainian, Englishman, Spaniard, Japanese, and African respectively.
  • V₁₃ - V₁₈ correspond to six house numbers; 1, 2, 3, 4, 5, and 6 respectively.
  • V₁₉ - V₂₄ correspond to six fruits: Pear, Orange, Apple, Banana, Cherry, and Strawberry respectively.
  • V₂₅ - V₃₀ correspond to six road signs: Stop, Hospital, Speed Limit, One Way, Railroad Crossing, and Dead End respectively.
  • V₃₀ - V₃₆ correspond to six letters: H, O, L, M, E, and S respectively. This can be represented in a tabular format as follows:

  R	Bl	Y	G	I	Br		R	Bl	Y	G	I	Br		R	Bl	Y	G	I	Br		R	Bl	Y	G	I	Br		R	Bl	Y	G	I	Br		R	Bl	Y	G	I	Br
  N	U	E	S	J	A		N	U	E	S	J	A		N	U	E	S	J	A		N	U	E	S	J	A		N	U	E	S	J	A		N	U	E	S	J	A
  1	2	3	4	5	6		1	2	3	4	5	6		1	2	3	4	5	6		1	2	3	4	5	6		1	2	3	4	5	6		1	2	3	4	5	6
  P	O	A	B	C	S		P	O	A	B	C	S		P	O	A	B	C	S		P	O	A	B	C	S		P	O	A	B	C	S		P	O	A	B	C	S
  St	H	Sl	O	R	D		St	H	Sl	O	R	D		St	H	Sl	O	R	D		St	H	Sl	O	R	D		St	H	Sl	O	R	D		St	H	Sl	O	R	D
  H	O	L	M	E	S		H	O	L	M	E	S		H	O	L	M	E	S		H	O	L	M	E	S		H	O	L	M	E	S		H	O	L	M	E	S

Sherlock Table

All instances of the Sherlock have the following constraints:

• Each house is of a different colour,
• has a unique house number,
• and is inhabited by a single person,
• who has a favourite fruit,
• hates a particular road sign,
• and whose first name starts with a unique letter. In addition to these constraints each instance of the Sherlock problem has a subset of all valid constraints for the instance’s solution. The valid constraints for the Sherlock Problem are chosen from the set { V_i in-same-column-as V_j , V_i next-to V_j , V_i next-to-and-right-of V_j , V_i next-to-and-left-of V_j , V_i not-same-column-as V_j , V_i not-next-to V_j , V_i right-of V_j , V_i left-of V_j , V_i between V_j and V_k ², and V_i = known-column } ³ where the constraint is true for a given i and j.