## 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_{1}, V_{2}, … , 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
_{1}- V_{5}correspond to five houses; Red, Blue, Yellow, Green, and Ivory, respectively. - V
_{6}- V_{10}correspond to five brands of cigarettes; Old-Gold, Parliament, Kools, Lucky, and Chesterfield, respectively. - V
_{11}- V_{15}correspond to five nationalities: Norwegian, Ukranian, Englishman, Spandiard, and Japanese, respectively. - V
_{16}- V_{20}correspond to five pets: Zebra, Dog, Horse, Fox, and Snails, respectively. - V
_{21}- V_{25}correspond to five drinks: Coffee, Tea, Water, Milk, Orange Juice, respectively. This can be represented in a tabular format as follows:

- V

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 } [^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:

V

_{1}- V_{6}correspond to six houses; Red, Blue, Yellow, Green, and Ivory, and Brown respectively.V

_{7}- V_{12}correspond to six nationalities: Norwegian, Ukrainian, Englishman, Spaniard, Japanese, and African respectively.V

_{13}- V_{18}correspond to six house numbers; 1, 2, 3, 4, 5, and 6 respectively.V

_{19}- V_{24}correspond to six fruits: Pear, Orange, Apple, Banana, Cherry, and Strawberry respectively.V

_{25}- V_{30}correspond to six road signs: Stop, Hospital, Speed Limit, One Way, Railroad Crossing, and Dead End respectively.V

_{30}- V_{36}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}[^2], and V_{i}= known-column } [^3] where the constraint is true for a given i and j.