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 n 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:

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 se { 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:

Sherlock problem definition

• 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:

Sherlock problem initial states

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.