A Study of Selected Algorithms Against the Sherlock and Zebra Problems
CIS*4750 Course Project
Author: Daniel F. Dickinson
Date: 20030209
The binary constraint satisfaction problem (bcsp) is an important area of research because so many problems can be represented in this form [Kumar92]. For that reason this paper attempts to answer a number of questions about the use of bcsp’s using two different types of problem. The hypotheses that this paper studies are:
 Arc consistency, found using AC3 from [Kumar92], alone is sufficient to solve the Zebra problem.
 Arc consistency, found using AC3, alone is sufficient to solve the Sherlock problem.
 Backmarking with conflictdirected backjumping (as modified by [Kondrak97] and called BMCBJ2) is more efficient at solving the Zebra problem than making the problem arc consistent using AC3 for a large set of random instances of the Zebra problem.
 BMCBJ2 is more efficient at solving most cases in a large random sample of instances of the Sherlock problem than AC3.
 BMCBJ2 is more efficient at solving most cases in a large random sample of instances of the Zebra problem than the genetic algorithms developed by the author for an assignment for CIS*4750.
In order to test these hypotheses the author developed software which generated random Sherlock and Zebra problems and saved them to disk. The author also wrote implementations of the above algorithms which could read the problems from disk and solve them using the desired algorithm. This software was written and run in Java 2 SE using Sun’s JDK1.4 on a system with an AMDK62 300 CPU, 196MB of RAM, and running RedHat Linux 7.2 (Enigma). In addition to the Java software, script files were written which allowed the author to measure the CPU and systemonbehalfoftheprogram time and record it in a file suitable for import into a spreadsheet program.
 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} .
 Kconsistent 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].

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; OldGold, 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:
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} insamecolumnas V_{j} , V_{i} nextto V_{j} , V_{i} nexttoandrightof V_{j} , and V_{i} = knowncolumn } ^{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 OldGold 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} insamecolumnas V_{j} , V_{i} nextto V_{j} , V_{i} nexttoandrightof V_{j} , V_{i} nexttoandleftof V_{j} , V_{i} notsamecolumnas V_{j} , V_{i} notnextto V_{j} , V_{i} rightof V_{j} , V_{i} leftof V_{j} , V_{i} between V_{j} and V_{k} ^{2}, and V_{i} = knowncolumn } ^{3} where the constraint is true for a given i and j.
This section contains pseudocode of the algorithms used in the paper as well as a brief discussion of each algorithm.
These definition are based on the descriptions in [Prosser93] and [Kondrak97].
 v An array of values such that v[i] is the value assigned to V_{i} in the binary constraint satisfaction problem.
 n The number of variables actually in the problem. v[1] is the first variable and the last variable is v[n].
 domain An array such that domain[i] is the domain of of i (D_{i} from the bcsp).
 currentdomain An array such that currentdomain[i] is the set of values in D_{i} which has not yet been shown to be inconsistent in the current search process. currentdomain[i] is initialized to domain[i].
 C An n x n array such that C[i,j] contains the set of constraints between V_{i} and V_{j} in the bcsp. It corresponds to C_{i,j} in the bcsp.
 check(i,j) A function that returns true if the constraint between V_{i} and V_{j} is satisfied. (If there is no constraint between i and j then constraint is considered to be satisfied). Each call to check(i,j) is considered a consistency check for the measurements elsewhere in this paper.
 mcl An n x m (where m is the maximum domain size) array which holds the deepest variable that the instantiation v[i] = k was checked against (that is, mcl[i,k] = h was assigned when check(i,h) was performed)
 mbl In BMCBJ an array of size n which holds the shallowest past variable that changed value since v[i] was the current variable. In BMCBJ2 mbl is an n x m array in which mbl[i,j] holds the shallowest past variable that has changed value since v[i] last held the jth value in it’s domain.
 confset An array of size n such that confset[i] holds the subset of of the past variables in conflict (failed consistency checks) with V_{i} .
 rowpermutes A set containing all possible permutations of a row. The size of the set should be D_{r} ! where D_{r} is the domain of any variable in the row (the domain should be identical for each item in a row).
An algorithm used extensively in preparing in this paper is AC3, as presented by Kumar in [Kumar92]. This algorithm eliminates values from the domains of a given variable which cannot work based on the constraints and domains of the rest of the variables. The resulting constraint network is said to be arc consistent for all arcs (constraints).
The algorithm achieves arc consistency for all arcs by eliminating the values from the domain of a given variable which cannot be made consistent with the rest of the variables. That is, for each x € D_{i} , if there is no y € D_{j} such that C_{i,j} is true, x is removed from D_{i} .
Procedure REVISE makes a given arc arcconsistent with the current set of constraints. Procedure AC3 executes REVISE for every arc in the constraint problem. Note that it is not sufficient to execute REVISE once for each arc as eliminating an arc affects the validity of other arcs. AC3 reruns REVISE only for those arcs possibly affected by the elimination of a given arc.
procedure AC3.
begin AC3;
G := { All (i,j) such that Ci,j is not null }
Q := { All (Vi, Vj) such that (i, j) € G, i ≠ j }
while Q not empty
select and delete any arc (Vk, Vm) from Q;
if (REVISE(Vk, Vm) then
Q = Q union { (Vi, Vk) such that (i, k) € G, i ≠ k, i ≠ m) };
end if;
end while;
end AC3;
procedure REVISE(V_{i} , V_{j} ).
begin REVISE(Vi, Vj)
DELETE = false;
for each x is an element of Di do
if there is no such vj €; Dj such that (x, vj) is consistent,
then
delete x from Di;
DELETE = true;
end if;
end for;
return DELETE;
end REVISE;
BMCBJ2 is a modification of the algorithm in [Prosser93] based on information in [Kondrak97] and [Kondrak94]. It is a backtracking algorithm which keeps track of conflicts between variables and, when the current variable cannot be made consistent with a prior variable, jumps (skips multiple nodes rather than simply backtracking) back until a consistent node is reached. The algorithm also keeps track of successful and unsuccessful instantiations of a given variable with other variables and, when possible, uses this information to skip rechecking for consistency.
The original algorithm, BMCBJ, as it appears in [Prosser93], is presented below. Note that it consists of three functions: bccsp, bmcbjlabel, and bmcbjunlabel. Prosser used this format for conceptual clarity. It is easier to see the backtracking actions in this format than in a recursive function.
BMCBJ.
1 PROCEDURE bcssp (n, status)
2 BEGIN
3 consistent = true;
4 status = "unknown";
5 i = 1;
6 WHILE status = "unknown"
7 DO BEGIN
8 IF consistent
9 THEN i = label(i,consistent)
10 ELSE i = unlabel(i,consistent);
11 IF i > n
12 THEN status = "solution"
13 ELSE IF i = 0
14 THEN status = "impossible"
15 END
16 END;
Note label and unlabel in lines 9 and 10 are replaced by bmcbjlabel and bmcbjunlabel (which are presented below).
1 FUNCTION bmcbjlabel (i,consistent): INTEGER
2 BEGIN
3 consistent = false;
4 FOR K = EACH ELEMENT OF currentdomain[i] WHILE not consistent
5 DO BEGIN
6 consistent = mcl[i,k] ≥ mbl[j];
7 FOR h = mbl[i] TO i  1 WHILE consistent
8 DO BEGIN
9 v[i] = k;
10 consistent = check(i, h);
11 mcl[i,k] = h
12 END;
13 IF not consistent
14 THEN BEGIN
14.1 pushnew(mcl[i,k],confset[i]);
14.2 currentdomain[i] = remove(v[i],currentdomain[i])
14.3 END
15 END;
16 IF consistent THEN return(i+1) ELSE return(i)
17 END;
1 FUNCTION bmcbjunlabel(i,consistent): INTEGER
2 BEGIN
3 h = maxlist(confset[i]);
4 confset[h] = remove(h,union(confset[h],confset[i]));
4.1 mbl[i] = h;
4.2 FOR j = h + 1 TO n DO mbl[j] = min(mbl[j],h);
5 FOR j = h + 1 TO i
6 DO BEGIN
7 confset[j] = {0}
8 currentdomain[j] = domain[j];
9 END;
10 currentdomain[h] = remove(v[h],currentdomain[h]);
11 consistent = currentdomain[h] ≠ nil;
12 return(h)
13 END;
The modified algorithm, BMCBJ2 is presented below. It has been changed from BMCBJ as follows: Lines 9 and 10 of bcssp are modified to used bmcbj2label and bmcbj2unlabel instead of bmcbjlabel and bmcbjunlabel, in bmcbj2label lines 6, and 7 have been modified to use mbl[i][k] instead of mbl[i], line 9 has been moved to 6.1, line 6.2 has been added, line 4.1 has been deleted, and in bmcbj2unlabel line 4.2 has been replaced with lines 4.2.1  4.2.7.
The purpose of these changes is to correct a deficiency in BMCBJ. BMCBJ fails to account for the fact that backjumping means that not all values in the domain of a variable are tested (since backjumping occurs immediately when a conflict is found) and therefore redundant checks are performed. To correct this the mbl array needs to maintain a separate record of the shallowest variable whose value has changed since x_{i} was last instantiated with that value, for each variablevalue pair. This is achieved by making mbl a twodimensional array and recording instantiation points at bmcbj2label 6.2 instead of in bmcbj2unlabel (at 4.1).
The need for these changes and a general description of the changes required can be found in [Kondrak97], however there is no example in that paper. Code for a similar change to BMJ (backmarking with backjumping) can be found in [Kondrak94] and was invaluable in making the changes described in this paper.
BMCBJ2.
1 PROCEDURE bcssp (n, status)
2 BEGIN
3 consistent = true;
4 status = "unknown";
5 i = 1;
6 WHILE status = "unknown"
7 DO BEGIN
8 IF consistent
9 THEN i = bmcbj2label(i,consistent)
10 ELSE i = bmcbj2unlabel(i,consistent);
11 IF i > n
12 THEN status = "solution"
13 ELSE IF i = 0
14 THEN status = "impossible"
15 END
16 END;
1 FUNCTION bmcbj2label (i,consistent): INTEGER
2 BEGIN
3 consistent = false;
4 FOR K = EACH ELEMENT OF currentdomain[i] WHILE not consistent
5 DO BEGIN
6 consistent = mcl[i,k] ≥ mbl[j][k];
6.1 v[i] = k;
6.2 mbl[i][k] = i;
7 FOR h = mbl[i][k] TO i  1 WHILE consistent
8 DO BEGIN
10 consistent = check(i, h);
11 mcl[i,k] = h
12 END;
13 IF not consistent
14 THEN DO BEGIN
14.1 pushnew(mcl[i,k],confset[i]);
14.2 currentdomain[i] = remove(v[i],currentdomain[i])
14.3 END
15 END;
16 IF consistent THEN return(i+1) ELSE return(i)
17 END;
1 FUNCTION bmcbj2unlabel(i,consistent): INTEGER
2 BEGIN
3 h = maxlist(confset[i]);
4 confset[h] = remove(h,union(confset[h],confset[i]));
4.2.1 FOR j = h + 1 TO n
4.2.2 DO BEGIN
4.2.3 FOR 0 to m
4.2.4 DO BEGIN
4.2.5 mbl[j][m] = min(mbl[j][m],h);
4.2.6 END
4.2.7 END
5 FOR j = h + 1 TO i
6 DO BEGIN
7 confset[j] = {0}
8 currentdomain[j] = domain[j];
9 END;
10 currentdomain[h] = remove(v[h],currentdomain[h]);
11 consistent = currentdomain[h] ≠ nil;
12 return(h)
13 END;
This section describes the three genetic algorithms designed by this author to solve the Zebra and Sherlock problems for Assignment #3 for CIS*4750 at the University of Guelph. The first algorithm uses only mutation and is called, aptly enough, Mutate, the second algorithm uses crossover with mutation and is called Xover, while the third algorithm uses double crossover and is called DoubleX.
 Genetic Algorithm A genetic algorithm is paradigm modelled after evolutionary processes. A ‘population’ of possible solutions is generated and evaluated for fitness. A partiallyrandom selection of solutions is then taken (possibly multiple times, with the ‘most fit’ algorithms being used most often) and from that selection new solutions are generated and evaluated. This process is repeated until a solution which meets some terminal criterion is found.
 Mutation In the context of genetic algorithms mutations refers to a random change in some part of the individual (solution) such that a new individual (solution) is created.
 Crossover Crossover occurs during reproduction involving two parents. Some random point is selected up to which one parent’s ‘genetic’ information is is used and after which the other parent’s information is used.
 Death In a genetic algorithm death occurs when the individual is removed from the population (e.g. in a fixed size array with the least fit on the bottom, children replace the least fit individual which can be said to have died).
 calculatedistancefromconsistent This is the heuristic used to calculate fitness in the genetic algorithms discussed in this paper. When a solution violates a constraint, the number of columns one of the variables would have to move to be consistent is calculated (e.g. if there is a constraint that says the coffee is next to the zebra, but the coffee is in the same column as the zebra a distance of one is calculated).
 fitness An attempt measure of how close the solution is to a solution. In the following algorithms a higher number for fitness is worse and a lower value is better.
 chromosone For this paper chromosone is an array of size n whose contents correspond to the value of the variables in the constraint problem to be solved.
This is a simple algorithm that does asexual reproduction. A selection of the best fit, as well as a small number of the ‘least fit but not dying’, individuals are copied and then mutated to create children. The random selection of ‘least fit but not dying’ individuals is done to help prevent the algorithm from getting ‘stuck’ on a local minimum by boosting the probability a diverse population will exist. Experience gathered while watching the debug output during development reveals that this, unfortunately, has had limited success and that the mutationonly algorithm still tends to land a local minimum, and has poor chances of getting out.
The pseudocode for the algorithm is outlined below.
1 PROCEDURE Mutate()
2 FOR 1 TO max_population
3 DO BEGIN
4 select a solution from the set of possible solutions
5 END FOR
6 evaluatefitness()
7 fitnesssort()
8 WHILE bestsolutionisnotthesolution()
9 DO BEGIN
10 selectfitindividuals()
11 reproduce()
12 evaluatefitness()
13 fitnesssort()
14 END WHILE
15 outputsolution()
16 END PROCEDURE
1 PROCEDURE evaluatefitness()
2 FOR EACH variable i
3 DO BEGIN
4 IF domain[i] does not contain v[i]
5 THEN BEGIN
6 fitness += 200
7 END IF
8 END FOR
9 FOR EACH constraint
10 DO BEGIN
11 IF constraint ≠ "notequal"
12 THEN fitness += calculatedistancetoconsistent
13 ELSE
14 DO BEGIN
15 fitness += 25
16 END IF
17 END FOR
18 END evaluatefitness
1 PROCEDURE fitnesssort
2 place lowest fitness in population[0], next in population[1], etc.
3 END fitnesssort
1 PROCEDURE selectfitindividuals
2 calculaterelativeprobability()
3 FOR 0 to (numchildren  numpoorfit)
4 DO BEGIN
5 add population[getparent()] to parents
6 END FOR
7 FOR 0 to (numpoorfit)
8 DO BEGIN
9 add population[getpoorparent()] to parents
10 END FOR
11 END selectfitindividuals
1 PROCEDURE calculaterelativeprobability
2 totaltimesbetter = 0
3 FOR i = 0 TO populationsize  numtodie
4 DO BEGIN
5 timesbetter[i] = (maxfitness + 1  population[i].fitness)
6 totaltimesbetter += timesbetter[i]
7 END FOR
8 x = 1 ÷ totalTimesBetter
9 FOR i = 0 TO timesbetter.size
10 DO BEGIN
11 chancereproducing = timesbetter[i] × x
12 END FOR
13 END calculaterelativeprobability
1 PROCEDURE getparent()
2 parent = first accumlatedchancereproducing > random number between 0 and 1
3 END getparent
1 PROCEDURE getpoorparent()
2 parent = first (1  accumlatedchancereproducing) > random number between 0 and 1
3 END getparent
1 PROCEDURE reproduce()
2 FOR i = 1 to numparents
3 DO BEGIN
4 child = parents[i]
5 FOR j = 1 TO n
6 DO BEGIN
7 IF (random number between 0 and 1 < mutationprobability)
8 THEN BEGIN
9 child.chromosone[j] = random number between 1 and maxdomain
10 END IF
11 END FOR
12 population[maxpopulation  numchildren + i] = child
13 END FOR
14 END reproduce
This genetic algorithm replaces the asexual reproduction of Mutate with a two parent reproduction scheme using a combination of crossover and a chance of mutation of the result of the parent’s combined contributions.
Xover() is identical to Mutate(), except the name while select() and reproduce() have been modified to use two parents and crossover.
Xover proves to be much more robust than Mutate, solving problems much quicker and usually being able to solve the problem in a somewhat reasonable timeframe, rather than getting stuck on a local minimum and only getting out after an unlikely mutation.
1 PROCEDURE selectfitindividuals
2 calculaterelativeprobability()
3 FOR 0 to (numchildren ÷ 2)
4 DO BEGIN
5 parentnum = getparent()
6 add population[parentnum] to parents
7 add population[populationsize  numchildren  parentnum] to parents
8 END FOR
9 IF (parents.size < numchildren + 1)
10 THEN BEGIN
11 add population[getparent()]
12 END IF
13 END selectfitindividuals
1 PROCEDURE reproduce()
2 FOR i = 1 to (numparents  1) STEP 2
3 DO BEGIN
4 k = random number between 1 and n
5 FOR j = 1 to k
6 DO BEGIN
7 child1.chromosone[j] = parents[i].chromosone[j]
8 child2.chromosone[j] = parents[i + 1].chromosone[j]
9 END FOR
10 FOR j = k to n
11 DO BEGIN
12 child1.chromosone[j] = parents[i + 1].chromosone[j]
13 child2.chromosone[j] = parents[i].chromosone[j]
14 END FOR
15 FOR j = 1 TO n
16 DO BEGIN
17 IF (random number between 0 and 1 < mutationprobability)
18 THEN BEGIN
19 child1.chromosone[j] = random number between 1 and maxdomain
20 child2.chromosone[j] = random number between 1 and maxdomain
21 END IF
22 END FOR
23 population[maxpopulation  numchildren + i] = child1;
24 population[maxpopulation  numchildren + i + 1] = child2;
25 END FOR
26 END reproduce
This is a variation on Xover which uses two crossover points instead of only one. The only change to the algorithm from Xover is in the reproduce() function in which the second crossover point is added (lines 4.1, and 9.19.5 are added while lines 9 and 10 are modified). DoubleX() is exactly same as Xover() except the name.
DoubleX does not seem to be much different than Xover, and in fact may experience decreased performance. Unfortunately, due to run times required to test this question it has not been answered for this paper.
1 PROCEDURE reproduce()
2 FOR i = 1 to (numparents  1) STEP 2
3 DO BEGIN
4 k = random number between 1 and n
4.1 l = random number between k + 1 and n
5 FOR j = 1 to k
6 DO BEGIN
7 child1 = parents[i].chromosone[j]
8 child2 = parents[i + 1].chromosone[j]
9 END FOR
9.1 FOR j = k to l
9.2 DO BEGIN
9.3 child1 = parents[i + 1].chromosone[j]
9.4 child2 = parents[i].chromosone[j]
9.5 END FOR
10 FOR j = l to n
11 DO BEGIN
12 child1 = parents[i + 1].chromosone[j]
13 child2 = parents[i].chromosone[j]
14 END FOR
15 FOR j = 1 TO n
16 DO BEGIN
17 IF (random number between 0 and 1 < mutationprobability)
18 THEN BEGIN
19 child1.chromosone[j] = random number between 1 and maxdomain
20 child2.chromosone[j] = random number between 1 and maxdomain
21 END IF
22 END FOR
23 population[maxpopulation  numchildren + i] = child1;
24 population[maxpopulation  numchildren + i + 1] = child2;
25 END FOR
25 END reproduce
This section outlines the algorithms used to generate the problems the various algorithms were tested against.
 knownvars A set containing the variables for which a constraint involving them has been generated.
This algorithm starts by generating a random solution. It then begins with two ‘anchor’ points (that is two variables whose domain has been set to the solution) which are added to the knownvars set (which starts empty). The algorithm then randomly picks a type of constraint (clue) to use (the clues have different probabilities of being picked), and for each known variable to unknown variable (the set of which is represented as ~knownvars below) combination checks if the clue vx constraint vy is a valid statement for the previously generated random solution. If the clue is valid then it is added to possibleclues. If, after checking all knownvar/unknownvar combinations, there are no possible clues the algorithm tries unknown only, and failing that known only.
Once the possible clues have been generated one of the possible clues is randomly picked for addition to the problem set. The process of picking a constraint and generating possible solution continues until AC3 is able to solve the problem.
1 PROCEDURE GenerateStrongKProblem()
2 BEGIN
3 rowpermutations = generaterowpermutations()
4 solution = generaterandomsolution()
5 x1 = random number between 1 and n
6 x2 = random number between 1 and n, x2 ≠ x1
7 set domain[x1] = v[x1]
8 set domain[x2] = v[x2]
9 add x1 and x2 to knownvars
10 given[x1] = v[x1]
11 given[x2] = v[x2]
12 WHILE ~hasonesolution()
13 DO BEGIN
14 clue = random constrainttype
15 FOR EACH vx IN knownvars
16 DO BEGIN
17 FOR EACH vy IN ~knownvars
18 DO BEGIN
19 IF check(vx, vy, clue)
20 THEN BEGIN
21 add (vx, vy) to possibleclues
22 END IF
23 END FOR
24 IF possibleclues is empty
25 THEN BEGIN
26 FOR EACH vx IN ~knownvars
27 DO BEGIN
28 FOR EACH vy IN ~knownvars, vy ≠ vx
29 DO BEGIN
30 IF check(vx, vy, clue)
31 THEN BEGIN
32 add (vx, vy) to possibleclues
33 END IF
34 END FOR
35 END FOR
36 END IF
37 IF possibleclues is empty
38 THEN BEGIN
39 FOR EACH vx IN knownvars
40 DO BEGIN
41 FOR EACH vy IN knownvars, vy ≠ vx
42 DO BEGIN
43 IF check(vx, vy, clue)
44 THEN BEGIN
45 add (vx, vy) to possibleclues
46 END IF
47 END FOR
48 END FOR
49 END IF
50 END FOR
51 newconstraint = choose a random arc from possibleclues
52 IF (clue == GIVEN)
53 THEN BEGIN
54 given[newconstraint.j] = v[newconstraint.j]
55 ELSE
56 BEGIN
57 constraints[newconstraint.i][newconstraint.j] = clue
58 constraints[newconstraint.j][newconstraint.i] = reverse(clue)
59 END IF
60 END WHILE
61 outputnewproblem()
62 END
1 PROCEDURE generaterandomsolution()
2 BEGIN
3 FOR i = 0 TO maxrows  1
4 DO BEGIN
5 choose random row from rowpermutations
6 FOR j = 0 TO row.size  1
7 DO BEGIN
8 v[i * maxrows + j + 1] = row[j]
9 END FOR
10 END FOR
11 END
1 PROCEDURE hasonesolution()
2 BEGIN
3 AC3()
4 done = TRUE
5 FOR i = 1 TO n
6 DO BEGIN
7 IF domain[i].size > 1
8 THEN BEGIN
9 done = FALSE
10 END IF
11 END FOR
12 return done
13 END
This algorithm picks random clues from the set of all clues until a modified form of CBJ (conflict directed backjumping) indicates that there is at most one solution. CBJ was chosen for modification because the process of modifying it was relatively straightforward whereas trying to change BMCBJ2 would have been more difficult (because of the backmarking).
This algorithm is a modified version of CBJ whichhas been modified from the presentation in [Prosser93] so that it detects if there is more than one solution. It accomplishes this by adding an array cbf of size n which is initialized to false and indicates when the conflict set (confset) for a given variable no longer means that the reason for the conflict is an invalid instantiation but rather that a solution was found. In such a case a single step back is the desired action rather than the backjumping behavior normally used by this algorithm.
In bcssp the following changes have been made: 4.1 has been added, 12 has been modified, 12.112.8 have been added, and 13.113.3 have been added. cbjlabel remains the same as in [Prosser93] while cbjunlabel is modified in the following fashion: 2.12.3 have been added with 3 and 4 being placed inside the else of 2.3. Also 8.1 and 11.1 have been added.
1 PROCEDURE bcssp (n, status)
2 BEGIN
3 consistent = true;
4 status = "unknown";
4.1 prevstatus = "unknown";
5 i = 1;
6 WHILE status = "unknown"
7 DO BEGIN
8 IF consistent
9 THEN i = label(i,consistent)
10 ELSE i = unlabel(i,consistent);
11 IF i > n
12 THEN IF prevstatus = "unknown"
12.1 THEN prevstatus = "solution"
12.2 FOR j = 0 TO n
12.3 DO BEGIN
2.4 cbf[j] = true
12.5 END FOR
12.6 i = n
12.7 ELSE IF prevstatus = "solution"
12.8 THEN status = "morethanonesolution"
13 ELSE IF i = 0
13.1 THEN IF prevstatus = "solution"
13.2 status = "solution"
13.3 ELSE
14 status = "impossible"
15 END IF
16 END
17 END;
1 FUNCTION cbjunlabel (i,consistent): INTEGER
2 BEGIN
2.1 IF cbf[i]
2.2 THEN h = i  1
2.3 ELSE
3 h = maxlist(confset[i])
4 confset[h] = remove(h,union(confset[h],confset[i]));
5 FOR j = h + 1 TO i
6 DO BEGIN
7 confset[i] = {0};
8 currentdomain[j] = domain[j]
8.1 cbf[j] = false
9 END;
10 currentdomain[h] = remove(v[h],currentdomain[h]);
11 consistent = currentdomain[h] ≠ nil;
11.1 cbf[j] = false
12 return(h)
13 END
14 END;
1 FUNCTION cbjlabel(i,consistent): INTEGER
2 BEGIN
3 consistent = false;
4 FOR v[i] = EACH ELEMENT OF currentdomain[i] WHILE not consistent
5 DO BEGIN
6 consistent = true;
7 FOR h = 1 TO i  1 WHILE consistent
8 DO consistent = check(i,h);
9 IF not consistent
10 THEN BEGIN
11 pushnew(h  1,confset[i]);
12 currentdomain[i] = remove(v[i],currentdomain[i])
13 END
14 END;
15 IF consistent THEN return(i+1) ELSE return(i)
16 END;
1 PROCEDURE GenerateStrongKProblem()
2 BEGIN
3 rowpermutations = generaterowpermutations()
4 solution = generaterandomsolution()
5 possibleclues = findpossibleclues()
6 WHILE (!hasonepossiblesolution())
7 DO BEGIN
8 newclue = pick random clue from possibleclues
9 IF newclue.type == GIVEN
10 THEN BEGIN
11 given[newclue.j] = v[newclue.j]
12 add v[newclue.j] to domain[newclue.j]
13 ELSE
14 BEGIN
15 constraints[newclue.i][newclue.j].add(newclue.type)
16 constraints[newclue.j][newclue.i].add(reverse(newclue.type))
17 END IF
18 END WHILE
19 END GenerateStrongKProblem
1 PROCEDURE hasonepossiblesolution()
2 BEGIN
3 result = bcssp(n)
4 IF (result = "solution")
5 THEN RETURN true
6 ELSE IF (result = "no solution")
7 THEN ERROREXIT("No solution possible.")
8 END IF
9 RETURN false
10 END
1 PROCEDURE findpossibleclues()
2 BEGIN
3 FOR vx = 1 TO n
4 DO BEGIN
5 FOR vy = 1 to n, vy ≠ vx
6 DO BEGIN
7 FOR EACH clue IN allowedrelations
8 DO BEGIN
9 IF check(vx, vy, clue)
10 THEN BEGIN
11 add (vx, clue, vy) to possibleclues
12 END IF
13 END FOR
14 END FOR
15 END FOR
16 END findpossibleclues
The hypothesis that achieving arc consistency using AC3 is sufficient to solve the Zebra problem can be quickly disproved using the benchmark Zebra problem presented earlier in this paper. Once arc consistency has been achieved there still remain several variables with more than one possible value in its domain. Similar results can be seen for the Sherlock problem by applying AC3 to a random case generated by the GenerateRandomProblem() procedure of the preceeding section.
One such sample problem appears in Appendix A
Kumar (in [Kumar92]) reports that arc consistency is not, in general, sufficient to find a solution (or that there is no solution). He then goes on to show that for a contraint graph having n nodes, it can be solved using only arc consistency, if the graph is nconsistent. He also shows that it is sometimes possible to solve a nnode bcsp with less than nconsistency.
Given that arc consistency by itself cannot solve all binary constraint problems it follows that an algorithm such as BMCBJ2 which can is better at solving the bcsp’s. Having said that, comparing the performance of AC3 to that of BMCBJ2 for problems that AC3 can solve is still an interesting exercise. Therefore, using problems generated using GenerateStrongKProblem(), we obtain the following results over 1000 test cases for each of the Zebra and Sherlock problem.
Measurement  AC3 vs. BMCBJ2 

Fewer Checks (number of cases)  25975 
Less Time (number of cases)  277710 
Average Number of Checks  234103755 
Minimum Number of Checks  9876137 
Maximum Number of Checks  42086134394 
Average Time (CPU + System) (seconds)  1.771.72 
Minimum Time (CPU + System) (seconds)  1.571.39 
Maximum Time (CPU + System) (seconds)  1.985.24 
AC3 vs. BMCBJ2: Zebra
Measurement  AC3 vs. BMCBJ2 

Fewer Checks (number of cases)  124876 
Less Time (number of cases)  417573 
Average Number of Checks  89090139170 
Minimum Number of Checks  33529294 
Maximum Number of Checks  16439161250399 
Average Time (CPU + System) (seconds)  2.164.67 
Minimum Time (CPU + System) (seconds)  1.831.50 
Maximum Time (CPU + System) (seconds)  2.561145.12 
AC3 vs. BMCBJ2: Sherlock
What is most interesting about the results is the fact that in a small number cases BMCBJ2 is much worse than AC3, so much so that for Sherlock most of the performance measures look worse for BMCBJ2 than AC3 despite the fact that it was better more than half the time. Exploring the properties of the problems that result in such bad performance is a useful future exercise.
The hypothesis that BMCBJ2 is more efficient at solving most of a large random sample of of Zebra problems is true, as can be seen below. Further, we can see that the algorithm tested can be ordered, both in terms of constraint checks and in terms of time, as follows: BMCBJ2 < DoubleX < Xover < Mutate although DoubleX is only slightly better than Xover. The change to Xover to get DoubleX is not a clear winner, but crossover plus mutation is without a doubt better than mutation alone. The numerical results follow.
Measurement  BMCBJ2  Mutate  Xover  DoubleX 

Average Number of Checks  3554  12588855  3897429  3315161 
Minimum Number of Checks  412  541110  379620  499423 
Maximum Number of Checks  15093  132081622  323868611  212341720 
Average Time (CPU + System) (seconds)  2.17  62.65  22.00  19.30 
Minimum Time (CPU + System) (seconds)  1.82  5.44  4.66  5.14 
Maximum Time (CPU + System) (seconds)  6.49  686.84  1603.49  986.12 
Zebra, BMCBJ2 vs Mutate vs Xover vs DoubleX
This paper studied a number of hypothesis, and in the process developed some algorithms. The algorithms for generating random problems proved to be harder to develop than expected. Original attempts involved attempts to use a heuristic rather than solving the bcsp for each new addition of a constraint, but that failed so the current solution (using AC3 for strongly kconsistent generation and CBJMulti for ‘totally random’ problems) was developed.
The genetic algorithm development proved easier although a genetic algorithm which bested BMCBJ2 was not found in producing this paper (a possible route to take for this is to make the chromasones more complex, rather than simply being the solution to the bcsp). BMCBJ2 proved to be the best complete (i.e. works for all problems) algorithm as AC3 cannot always find a solution, but for strongly kconsistent problems AC3 was found to be the better choice for both the Zebra and the Sherlock problems. If determining kconsistency before solving the problem proves to be both possible and efficient a hybrid approach could prove to be ideal.
Further work on random problem generation is needed. It would, example, be useful to test the ‘totally random’ problems to determine if they are a good crosssection of realworld problems, or if they tend to cluster around a particular type of problem. In addition, it could be informative to determine how many of good random selection of problems are strongly kconsistent (and therefore solveable by AC3).
Additional questions include the value of AC3 preprocessing, which according to [Kumar92] is a common practise, and how BMCBJ2 stacks up against both other backtracking algorithms ([Kondrak97] proves that BMCBJ2 performs fewer constraint checks but whether is is faster depends on whether the reduction in constraint checking comes with a greater overhead cost). BMCBJ2 also needs to be compared to other algorithms out there. In addition, this paper makes no attempt to compare variable instantiation orders for BMCBJ2, and it is known that variable instantiation order can have a significant performance impact on backtracking and backjumping algorithms [Prosser93].
[Kondrak94] Kondrak Grzegorz A Theoretical Evaluation of Selected Backtracking Algorithms. Technical Report TR9410, University of Alberta Fall 1994.
[Kondrak97] Kondrak Grzegorz van Beek Peter A Theoretical Evaluation of Selected Backtracking Algorithms. Artificial Intelligence 89: 365387, 1997.
[Kumar92] Kumar Vipin Algorithms for Constraint Satisfaction Problems: A Survey. AI Magazine Vol 13, Issue 1: 3244, 1992.
[Prosser93] Prosser Patrick Hybrid Algorithms for the Constraint Satisfaction Problem Computational Intelligence Vol 9, Number 3: 268299, 1993.
This is a problem for which arc consistency is insufficient to solve the problem.
S
2 is 1
9 is 1
11 is 2
17 is 2
20 is 3
21 is 2
22 is 4
24 is 5
27 is 6
28 is 5
1 notnextsame 2
1 notequal 2
1 notequal 3
1 notequal 4
1 notequal 5
1 notequal 6
1 notnextto 14
1 notsamecol 26
1 samecol 33
2 notnextsame 1
2 notequal 1
2 notequal 3
2 notequal 4
2 notequal 5
2 notequal 6
2 leftof 13
2 leftof 25
2 notnextto 35
3 notequal 1
3 notequal 2
3 leftof 4
3 notequal 4
3 notequal 5
3 notequal 6
3 nextright 30
3 notnextsame 36
4 notequal 1
4 notequal 2
4 rightof 3
4 notequal 3
4 notequal 5
4 notequal 6
4 notsamecol 19
4 notsamecol 20
4 notnextto 25
4 rightof 30
5 notequal 1
5 notequal 2
5 notequal 3
5 notequal 4
5 notequal 6
5 notsamecol 14
5 notnextsame 25
5 notsamecol 33
5 nextto 34
6 notequal 1
6 notequal 2
6 notequal 3
6 notequal 4
6 notequal 5
6 notnextto 17
6 notnextto 24
6 notsamecol 29
7 notequal 8
7 notequal 9
7 notequal 10
7 notequal 11
7 notequal 12
7 notnextto 15
7 leftof 22
7 leftof 28
7 leftof 35
8 notequal 7
8 notequal 9
8 notequal 10
8 notequal 11
8 notequal 12
8 notsamecol 17
8 notnextsame 22
8 notsamecol 33
9 notequal 7
9 notequal 8
9 notequal 10
9 notequal 11
9 notequal 12
9 notsamecol 21
10 notequal 7
10 notequal 8
10 notequal 9
10 notequal 11
10 notequal 12
10 notsamecol 32
10 notnextto 34
10 samecol 34
11 notequal 7
11 notequal 8
11 notequal 9
11 notequal 10
11 notequal 12
11 notnextsame 15
11 nextto 33
12 notequal 7
12 notequal 8
12 notequal 9
12 notequal 10
12 notequal 11
12 nextright 16
12 notsamecol 23
13 rightof 2
13 nextleft 14
13 notequal 14
13 notequal 15
13 notequal 16
13 notequal 17
13 notequal 18
13 notnextsame 25
13 notsamecol 30
13 notnextto 31
13 notnextto 36
14 notnextto 1
14 notsamecol 5
14 nextright 13
14 notequal 13
14 notequal 15
14 notequal 16
14 notequal 17
14 notequal 18
15 notnextto 7
15 notnextsame 11
15 notequal 13
15 notequal 14
15 notequal 16
15 notequal 17
15 notequal 18
15 notnextsame 20
15 rightof 25
15 notsamecol 36
16 nextleft 12
16 notequal 13
16 notequal 14
16 notequal 15
16 notequal 17
16 notequal 18
16 notsamecol 31
16 notnextsame 34
16 nextto 35
16 nextleft 35
17 notnextto 6
17 notsamecol 8
17 notequal 13
17 notequal 14
17 notequal 15
17 notequal 16
17 notequal 18
17 notnextto 21
17 notsamecol 24
17 notnextsame 26
18 notequal 13
18 notequal 14
18 notequal 15
18 notequal 16
18 notequal 17
18 nextleft 21
18 notnextsame 22
19 notsamecol 4
19 rightof 20
19 notnextsame 20
19 notequal 20
19 notequal 21
19 notequal 22
19 notequal 23
19 notequal 24
19 notsamecol 29
20 notsamecol 4
20 notnextsame 15
20 leftof 19
20 notnextsame 19
20 notequal 19
20 notequal 21
20 notequal 22
20 notnextsame 23
20 notequal 23
20 leftof 24
20 notequal 24
20 notnextsame 32
20 notnextto 36
21 notsamecol 9
21 notnextto 17
21 nextright 18
21 notequal 19
21 notequal 20
21 notequal 22
21 notequal 23
21 notequal 24
21 notnextto 27
22 rightof 7
22 notnextsame 8
22 notnextsame 18
22 notequal 19
22 notequal 20
22 notequal 21
22 notequal 23
22 notequal 24
22 notnextsame 27
23 notsamecol 12
23 notequal 19
23 notnextsame 20
23 notequal 20
23 notequal 21
23 notequal 22
23 notequal 24
23 notnextsame 33
24 notnextto 6
24 notsamecol 17
24 notequal 19
24 rightof 20
24 notequal 20
24 notequal 21
24 notequal 22
24 notequal 23
24 notsamecol 29
25 rightof 2
25 notnextto 4
25 notnextsame 5
25 notnextsame 13
25 leftof 15
25 notequal 26
25 notequal 27
25 notequal 28
25 notequal 29
25 notequal 30
25 notnextto 31
26 notsamecol 1
26 notnextsame 17
26 notequal 25
26 notequal 27
26 notequal 28
26 notequal 29
26 notequal 30
26 nextto 33
27 notnextto 21
27 notnextsame 22
27 notequal 25
27 notequal 26
27 notequal 28
27 notequal 29
27 notequal 30
28 rightof 7
28 notequal 25
28 notequal 26
28 notequal 27
28 notequal 29
28 notequal 30
28 samecol 34
29 notsamecol 6
29 notsamecol 19
29 notsamecol 24
29 notequal 25
29 notequal 26
29 notequal 27
29 notequal 28
29 notequal 30
30 nextleft 3
30 leftof 4
30 notsamecol 13
30 notequal 25
30 notequal 26
30 notequal 27
30 notequal 28
30 notequal 29
30 leftof 35
31 notnextto 13
31 notsamecol 16
31 notnextto 25
31 notequal 32
31 notequal 33
31 notequal 34
31 notequal 35
31 notequal 36
32 notsamecol 10
32 notnextsame 20
32 notequal 31
32 notequal 33
32 notequal 34
32 notequal 35
32 notequal 36
33 samecol 1
33 notsamecol 5
33 notsamecol 8
33 nextto 11
33 notnextsame 23
33 nextto 26
33 notequal 31
33 notequal 32
33 notequal 34
33 notequal 35
33 notequal 36
34 nextto 5
34 notnextto 10
34 samecol 10
34 notnextsame 16
34 samecol 28
34 notequal 31
34 notequal 32
34 notequal 33
34 notequal 35
34 notequal 36
35 notnextto 2
35 rightof 7
35 nextto 16
35 nextright 16
35 rightof 30
35 notequal 31
35 notequal 32
35 notequal 33
35 notequal 34
35 notsamecol 36
35 notnextsame 36
35 notequal 36
36 notnextsame 3
36 notnextto 13
36 notsamecol 15
36 notnextto 20
36 notequal 31
36 notequal 32
36 notequal 33
36 notequal 34
36 notsamecol 35
36 notnextsame 35
36 notequal 35
If you wish you can download the source code for selected algorithms against the Sherlock and Zebra problems and related programs.

Note that all constraints are also present reversed (i.e. V_{i} nexttoandrightof V_{j} requires that V_{j} nexttoandleftof V_{i} also be in the set of constraints.) ↩︎

For the sake of simplicity this is replaced with V_{i} nextto V_{j} , V_{i} nextto V_{k} , and V_{j} notsamecolumnas V_{k} ↩︎

Note that all constraints are also present reversed. ↩︎