## 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, Ukrainian, Englishman, Spaniard, 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:

- V

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.

Note that all constraints are also present reversed (i.e. V

_{i}next-to-and-right-of V_{j}requires that V_{j}next-to-and-left-of V_{i}also be in the set of constraints.) ↩︎For the sake of simplicity this is replaced with V

_{i}next-to V_{j}, V_{i}next-to V_{k}, and V_{j}not-same-column-as V_{k}↩︎Note that all constraints are also present reversed. ↩︎