## General Definitions

• arc consistency The domains of a variable Vi is such that for each constraint Ci,j Vi is consistent with the constraint for some permissible value of Vj for every value in the domain of Vi That is for every value x in Di (the domain of i) there exists some y in Dj such that Ci,j is satisfied. It is important to note that arc consistency is directional (that is (Vi , Vj ) being arc consistent does not mean (Vj , Vi ) 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 { V1 , V2 , … , Vn }, each having a domain Di such that Vi takes on a value from Di , does not conflict with a set of binary constraints { C1,1 , C1,2 , …, C1,n , …, C2,1 , C2,2 , …, C2,n , …, Cn,1 , Cn,2 , …, Cn,n } where Ci,j is a constraint (relation) between Vi and Vj that must be true, and if Ci,j is null there is no constraint between Vi and Vj .
• 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:
• V1 - V5 correspond to five houses; Red, Blue, Yellow, Green, and Ivory, respectively.
• V6 - V10 correspond to five brands of cigarettes; Old-Gold, Parliament, Kools, Lucky, and Chesterfield, respectively.
• V11 - V15 correspond to five nationalities: Norwegian, Ukrainian, Englishman, Spaniard, and Japanese, respectively.
• V16 - V20 correspond to five pets: Zebra, Dog, Horse, Fox, and Snails, respectively.
• V21 - V25 correspond to five drinks: Coffee, Tea, Water, Milk, Orange Juice, respectively. This can be represented in a tabular format as follows:

RBYGIRBYGIRBYGIRBYGIRBYGI
OPKLCOPKLCOPKLCOPKLCOPKLC
NUESJNUESJNUESJNUESJNUESJ
ZDHFSZDHFSZDHFSZDHFSZDHFS
CTWMOCTWMOCTWMOCTWMOCTWMO

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 { Vi in-same-column-as Vj , Vi next-to Vj , Vi next-to-and-right-of Vj , and Vi = known-column } 1 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:
• V1 - V6 correspond to six houses; Red, Blue, Yellow, Green, and Ivory, and Brown respectively.
• V7 - V12 correspond to six nationalities: Norwegian, Ukrainian, Englishman, Spaniard, Japanese, and African respectively.
• V13 - V18 correspond to six house numbers; 1, 2, 3, 4, 5, and 6 respectively.
• V19 - V24 correspond to six fruits: Pear, Orange, Apple, Banana, Cherry, and Strawberry respectively.
• V25 - V30 correspond to six road signs: Stop, Hospital, Speed Limit, One Way, Railroad Crossing, and Dead End respectively.
• V30 - V36 correspond to six letters: H, O, L, M, E, and S respectively. This can be represented in a tabular format as follows:
RBlYGIBrRBlYGIBrRBlYGIBrRBlYGIBrRBlYGIBrRBlYGIBr
NUESJANUESJANUESJANUESJANUESJANUESJA
123456123456123456123456123456123456
POABCSPOABCSPOABCSPOABCSPOABCSPOABCS
StHSlORDStHSlORDStHSlORDStHSlORDStHSlORDStHSlORD
HOLMESHOLMESHOLMESHOLMESHOLMESHOLMES

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 { Vi in-same-column-as Vj , Vi next-to Vj , Vi next-to-and-right-of Vj , Vi next-to-and-left-of Vj , Vi not-same-column-as Vj , Vi not-next-to Vj , Vi right-of Vj , Vi left-of Vj , Vi between Vj and Vk 2, and Vi = known-column } 3 where the constraint is true for a given i and j.

1. Note that all constraints are also present reversed (i.e. Vi next-to-and-right-of Vj requires that Vj next-to-and-left-of Vi also be in the set of constraints.) ↩︎

2. For the sake of simplicity this is replaced with Vi next-to Vj , Vi next-to Vk , and Vj not-same-column-as Vk  ↩︎

3. Note that all constraints are also present reversed. ↩︎

• 2:52 pm
• Daniel F. Dickinson