3. 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, Ukranian, Englishman, Spandiard, 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:

Table 1. Zebra Table

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

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:

Table 2. Sherlock Table

R B Y G I BR B Y G I BR B Y G I BR B Y G I BR B Y G I BR B Y G I B
N U E S J AN U E S J AN U E S J AN U E S J AN U E S J AN U E S J A
1 2 3 4 5 61 2 3 4 5 61 2 3 4 5 61 2 3 4 5 61 2 3 4 5 61 2 3 4 5 6
P O A B C SP O A B C SP O A B C SP O A B C SP O A B C SP O A B C S
S H P O R DS H P O R DS H P O R DS H P O R DS H P O R DS H P O R D
H O L M E SH O L M E SH O L M E SH O L M E SH O L M E SH O L M E S

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.

Notes

[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.