A Study of Selected Algorithms Against the Sherlock and Zebra Problems

CIS*4750 Course Project

Author: Daniel F. Dickinson

Date: 2003-02-09

Introduction

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:

  1. Arc consistency, found using AC-3 from [Kumar92], alone is sufficient to solve the Zebra problem.

  2. Arc consistency, found using AC-3, alone is sufficient to solve the Sherlock problem.

  3. Backmarking with conflict-directed backjumping (as modified by [Kondrak97] and called BM-CBJ2) is more efficient at solving the Zebra problem than making the problem arc consistent using AC-3 for a large set of random instances of the Zebra problem.

  4. BM-CBJ2 is more efficient at solving most cases in a large random sample of instances of the Sherlock problem than AC-3.

  5. BM-CBJ2 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 AMD-K6-2 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 system-on-behalf-of-the-program time and record it in a file suitable for import into a spreadsheet program.

Table of Contents

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, 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:

    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

    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:

    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

    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.

Algorithms

This section contains pseudocode of the algorithms used in the paper as well as a brief discussion of each algorithm.

Definitions for the Algorithms

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 Vi 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 (Di from the bcsp).

  • current-domain An array such that current-domain[i] is the set of values in Di which has not yet been shown to be inconsistent in the current search process. current-domain[i] is initialized to domain[i].

  • C An n x n array such that C[i,j] contains the set of constraints between Vi and Vj in the bcsp. It corresponds to Ci,j in the bcsp.

  • check(i,j) A function that returns true if the constraint between Vi and Vj 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 BM-CBJ an array of size n which holds the shallowest past variable that changed value since v[i] was the current variable. In BM-CBJ2 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.

  • conf-set An array of size n such that conf-set[i] holds the subset of of the past variables in conflict (failed consistency checks) with Vi.

  • row-permutes A set containing all possible permutations of a row. The size of the set should be |Dr|! where Dr is the domain of any variable in the row (the domain should be identical for each item in a row).

Achieving Arc Consistency: AC-3

An algorithm used extensively in preparing in this paper is AC-3, 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 € Di, if there is no y € Dj such that Ci,j is true, x is removed from Di.

Procedure REVISE makes a given arc arc-consistent with the current set of constraints. Procedure AC-3 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. AC-3 reruns REVISE only for those arcs possibly affected by the elimination of a given arc.

procedure AC-3.

                            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 AC-3;

procedure 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;

Backmarking with Conflict-Directed Backjumping 2: BM-CBJ2

BM-CBJ2 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 re-checking for consistency.

The original algorithm, BM-CBJ, as it appears in [Prosser93], is presented below. Note that it consists of three functions: bccsp, bm-cbj-label, and bm-cbj-unlabel. Prosser used this format for conceptual clarity. It is easier to see the backtracking actions in this format than in a recursive function.

BM-CBJ.

                        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 bm-cbj-label and bm-cbj-unlabel (which are presented below).

                        1 FUNCTION bm-cbj-label (i,consistent): INTEGER
                        2 BEGIN
                        3       consistent = false;
                        4       FOR K = EACH ELEMENT OF current-domain[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],conf-set[i]);
                        14.2            current-domain[i] = remove(v[i],current-domain[i])
                        14.3            END
                        15          END;
                        16      IF consistent THEN return(i+1) ELSE return(i)
                        17 END;

                        1 FUNCTION bm-cbj-unlabel(i,consistent): INTEGER
                        2 BEGIN
                        3       h = max-list(conf-set[i]);
                        4       conf-set[h] = remove(h,union(conf-set[h],conf-set[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           conf-set[j] = {0}
                        8           current-domain[j] = domain[j];
                        9           END;
                        10      current-domain[h] = remove(v[h],current-domain[h]);
                        11      consistent = current-domain[h] ≠ nil;
                        12      return(h)
                        13  END;

The modified algorithm, BM-CBJ2 is presented below. It has been changed from BM-CBJ as follows: Lines 9 and 10 of bcssp are modified to used bm-cbj2-label and bm-cbj2-unlabel instead of bm-cbj-label and bm-cbj-unlabel, in bm-cbj2-label 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 bm-cbj2-unlabel 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 BM-CBJ. BM-CBJ 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 xi was last instantiated with that value, for each variable-value pair. This is achieved by making mbl a two-dimensional array and recording instantiation points at bm-cbj2-label 6.2 instead of in bm-cbj2-unlabel (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.

BM-CBJ2.

                        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 = bm-cbj2-label(i,consistent)
                        10      ELSE i = bm-cbj2-unlabel(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 bm-cbj2-label (i,consistent): INTEGER
                        2 BEGIN
                        3       consistent = false;
                        4       FOR K = EACH ELEMENT OF current-domain[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 BEGIN
                        14.1            pushnew(mcl[i,k],conf-set[i]);
                        14.2            current-domain[i] = remove(v[i],current-domain[i])
                        14.3            END
                        15          END;
                        16      IF consistent THEN return(i+1) ELSE return(i)
                        17 END;

                        1       FUNCTION bm-cbj2-unlabel(i,consistent): INTEGER
                        2       BEGIN
                        3          h = max-list(conf-set[i]);
                        4           conf-set[h] = remove(h,union(conf-set[h],conf-set[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               conf-set[j] = {0}
                        8               current-domain[j] = domain[j];
                        9               END;
                        10          current-domain[h] = remove(v[h],current-domain[h]);
                        11          consistent = current-domain[h] ≠ nil;
                        12          return(h)
                        13      END;

Genetic Algorithms

Summary

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.

Definitions for Genetic Algorithms

  • Genetic Algorithm A genetic algorithm is paradigm modelled after evolutionary processes. A ‘population’ of possible solutions is generated and evaluated for fitness. A partially-random 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).

  • calculate-distance-from-consistent 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.

Mutate

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 mutation-only 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    evaluate-fitness()
                        7    fitness-sort()
                        8    WHILE best-solution-is-not-the-solution()
                        9        DO BEGIN
                        10       select-fit-individuals()
                        11       reproduce()
                        12       evaluate-fitness()
                        13       fitness-sort()
                        14    END WHILE
                        15    output-solution()
                        16 END PROCEDURE

                        1 PROCEDURE evaluate-fitness()
                        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 ≠ "not-equal"
                        12           THEN fitness += calculate-distance-to-consistent
                        13       ELSE
                        14           BEGIN
                        15           fitness += 25
                        16       END IF
                        17   END FOR
                        18 END evaluate-fitness

                        1 PROCEDURE fitness-sort
                        2    place lowest fitness in population[0], next in population[1], etc.
                        3 END fitness-sort

                        1 PROCEDURE select-fit-individuals
                        2    calculate-relative-probability()
                        3    FOR 0 to (num-children - num-poor-fit)
                        4        DO BEGIN
                        5        add population[get-parent()] to parents
                        6    END FOR
                        7    FOR 0 to (num-poor-fit)
                        8        DO BEGIN
                        9        add population[get-poor-parent()] to parents
                        10   END FOR
                        11 END select-fit-individuals

                        1 PROCEDURE calculate-relative-probability
                        2    total-times-better = 0
                        3    FOR i = 0 TO population-size - num-to-die
                        4        DO BEGIN
                        5        times-better[i] = (max-fitness + 1 - population[i].fitness)
                        6        total-times-better += times-better[i]
                        7    END FOR
                        8    x = 1 ÷ totalTimesBetter
                        9    FOR i = 0 TO times-better.size
                        10       DO BEGIN
                        11       chance-reproducing = times-better[i] × x
                        12   END FOR
                        13 END calculate-relative-probability

                        1 PROCEDURE get-parent()
                        2    parent = first accumlated-chance-reproducing > random number between 0 and 1
                        3 END get-parent

                        1 PROCEDURE get-poor-parent()
                        2    parent = first (1 - accumlated-chance-reproducing) > random number between 0 and 1
                        3 END get-parent

                        1 PROCEDURE reproduce()
                        2    FOR i = 1 to num-parents
                        3        DO BEGIN
                        4        child = parents[i]
                        5        FOR j = 1 TO n
                        6            DO BEGIN
                        7            IF (random number between 0 and 1 < mutation-probability)
                        8                THEN BEGIN
                        9                    child.chromosone[j] = random number between 1 and max-domain
                        10           END IF
                        11       END FOR
                        12       population[max-population - num-children + i] = child
                        13   END FOR
                        14 END reproduce

Xover

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 time-frame, rather than getting stuck on a local minimum and only getting out after an unlikely mutation.

                        1 PROCEDURE select-fit-individuals
                        2    calculate-relative-probability()
                        3    FOR 0 to (num-children ÷ 2)
                        4        DO BEGIN
                        5        parent-num = get-parent()
                        6        add population[parent-num] to parents
                        7        add population[population-size - num-children - parent-num] to parents
                        8    END FOR
                        9    IF (parents.size < num-children + 1)
                        10       THEN BEGIN
                        11       add population[get-parent()]
                        12   END IF
                        13 END select-fit-individuals

                        1 PROCEDURE reproduce()
                        2    FOR i = 1 to (num-parents - 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 < mutation-probability)
                        18               THEN BEGIN
                        19                   child1.chromosone[j] = random number between 1 and max-domain
                        20                   child2.chromosone[j] = random number between 1 and max-domain
                        21           END IF
                        22       END FOR
                        23       population[max-population - num-children + i] = child1;
                        24       population[max-population - num-children + i + 1] = child2;
                        25   END FOR
                        26 END reproduce

DoubleX

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.1-9.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 (num-parents - 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 < mutation-probability)
                            18               THEN BEGIN
                            19                   child1.chromosone[j] = random number between 1 and max-domain
                            20                   child2.chromosone[j] = random number between 1 and max-domain
                            21           END IF
                            22       END FOR
                            23       population[max-population - num-children + i] = child1;
                            24       population[max-population - num-children + i + 1] = child2;
                            25   END FOR
                            25 END reproduce

Generate Random Problems

This section outlines the algorithms used to generate the problems the various algorithms were tested against.

  • known-vars A set containing the variables for which a constraint involving them has been generated.

Generate Strongly K-consistent Problems

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 known-vars 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 ~known-vars 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 possible-clues. If, after checking all known-var/unknown-var 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 AC-3 is able to solve the problem.

                        1 PROCEDURE GenerateStrongKProblem()
                        2 BEGIN
                        3   row-permutations = generate-row-permutations()
                        4   solution = generate-random-solution()
                        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 known-vars
                        10  given[x1] = v[x1]
                        11  given[x2] = v[x2]
                        12  WHILE ~has-one-solution()
                        13      DO BEGIN
                        14      clue = random constraint-type
                        15      FOR EACH vx IN known-vars
                        16          DO BEGIN
                        17          FOR EACH vy IN ~known-vars
                        18              DO BEGIN
                        19              IF check(vx, vy, clue)
                        20                  THEN BEGIN
                        21                  add (vx, vy) to possible-clues
                        22              END IF
                        23          END FOR
                        24          IF possible-clues is empty
                        25              THEN BEGIN
                        26              FOR EACH vx IN ~known-vars
                        27                  DO BEGIN
                        28                  FOR EACH vy IN ~known-vars, vy ≠ vx
                        29                      DO BEGIN
                        30                      IF check(vx, vy, clue)
                        31                          THEN BEGIN
                        32                          add (vx, vy) to possible-clues
                        33                      END IF
                        34                  END FOR
                        35              END FOR
                        36          END IF
                        37          IF possible-clues is empty
                        38              THEN BEGIN
                        39              FOR EACH vx IN known-vars
                        40                  DO BEGIN
                        41                  FOR EACH vy IN known-vars, vy ≠ vx
                        42                      DO BEGIN
                        43                      IF check(vx, vy, clue)
                        44                          THEN BEGIN
                        45                          add (vx, vy) to possible-clues
                        46                      END IF
                        47                  END FOR
                        48              END FOR
                        49          END IF
                        50      END FOR
                        51      new-constraint = choose a random arc from possible-clues
                        52      IF (clue == GIVEN)
                        53          THEN BEGIN
                        54          given[new-constraint.j] = v[new-constraint.j]
                        55      ELSE
                        56          BEGIN
                        57          constraints[new-constraint.i][new-constraint.j] = clue
                        58          constraints[new-constraint.j][new-constraint.i] = reverse(clue)
                        59      END IF
                        60  END WHILE
                        61      output-new-problem()
                        62 END

                        1 PROCEDURE generate-random-solution()
                        2 BEGIN
                        3   FOR i = 0 TO max-rows - 1
                        4       DO BEGIN
                        5       choose random row from row-permutations
                        6       FOR j = 0 TO row.size - 1
                        7           DO BEGIN
                        8           v[i * max-rows + j + 1] = row[j]
                        9       END FOR
                        10  END FOR
                        11 END

                        1 PROCEDURE has-one-solution()
                        2 BEGIN
                        3       AC-3()
                        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

Generate ‘Totally Random’ Problems

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 BM-CBJ2 would have been more difficult (because of the backmarking).

CBJ-Multi

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 (conf-set) 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.1-12.8 have been added, and 13.1-13.3 have been added. cbj-label remains the same as in [Prosser93] while cbj-unlabel is modified in the following fashion: 2.1-2.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 prev-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 IF prev-status = "unknown"
                            12.1                THEN prev-status = "solution"
                            12.2                FOR j = 0 TO n
                            12.3                    DO BEGIN
                            12.4                    cbf[j] = true
                            12.5                    END FOR
                            12.6                i = n
                            12.7            ELSE IF prev-status = "solution"
                            12.8                THEN status = "more-than-one-solution"
                            13          ELSE IF i = 0
                            13.1            THEN IF prev-status = "solution"
                            13.2                status = "solution"
                            13.3            ELSE
                            14                  status = "impossible"
                            15      END
                            16  END;

                            1   FUNCTION cbj-unlabel (i,consistent): INTEGER
                            2   BEGIN
                            2.1     IF cbf[i]
                            2.2         THEN h = i - 1
                            2.3     ELSE
                            3           h = max-list(conf-set[i])
                            4           conf-set[h] = remove(h,union(conf-set[h],conf-set[i]));
                            5       FOR j = h + 1 TO i
                            6       DO BEGIN
                            7           conf-set[i] = {0};
                            8           current-domain[j] = domain[j]
                            8.1         cbf[j] = false
                            9           END;
                            10      current-domain[h] = remove(v[h],current-domain[h]);
                            11      consistent = current-domain[h] ≠ nil;
                            11.1    cbf[j] = false
                            12      return(h)
                            13 END;

                            1 FUNCTION cbj-label(i,consistent): INTEGER
                            2 BEGIN
                            3   consistent = false;
                            4   FOR v[i] = EACH ELEMENT OF current-domain[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,conf-set[i]);
                            12              current-domain[i] = remove(v[i],current-domain[i])
                            13              END
                            14          END;
                            15      IF consistent THEN return(i+1) ELSE return(i)
                            16 END;

GenerateRandomProblem
                            1 PROCEDURE GenerateStrongKProblem()
                            2 BEGIN
                            3   row-permutations = generate-row-permutations()
                            4   solution = generate-random-solution()
                            5   possible-clues = find-possible-clues()
                            6   WHILE (!has-one-possible-solution())
                            7       DO BEGIN
                            8       new-clue = pick random clue from possible-clues
                            9       IF new-clue.type == GIVEN
                            10          THEN BEGIN
                            11          given[new-clue.j] = v[new-clue.j]
                            12          add v[new-clue.j] to domain[new-clue.j]
                            13      ELSE
                            14          BEGIN
                            15          constraints[new-clue.i][new-clue.j].add(new-clue.type)
                            16          constraints[new-clue.j][new-clue.i].add(reverse(new-clue.type))
                            17      END IF
                            18  END WHILE
                            19 END GenerateStrongKProblem

                            1 PROCEDURE has-one-possible-solution()
                            2 BEGIN
                            3   result = bcssp(n)
                            4   IF (result = "solution")
                            5       THEN RETURN true
                            6   ELSE IF (result = "no solution")
                            7       THEN ERROR-EXIT("No solution possible.")
                            8   END IF
                            9   RETURN false
                            10 END

                            1 PROCEDURE find-possible-clues()
                            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 allowed-relations
                            8              DO BEGIN
                            9              IF check(vx, vy, clue)
                            10                  THEN BEGIN
                            11                  add (vx, clue, vy) to possible-clues
                            12              END IF
                            13          END FOR
                            14      END FOR
                            15  END FOR
                            16 END find-possible-clues

Results

Hypotheses 1 and 2

The hypothesis that achieving arc consistency using AC-3 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 AC-3 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 n-consistent. He also shows that it is sometimes possible to solve a n-node bcsp with less than n-consistency.

Hypotheses 3 and 4

Given that arc consistency by itself cannot solve all binary constraint problems it follows that an algorithm such as BM-CBJ2 which can is better at solving the bcsp’s. Having said that, comparing the performance of AC-3 to that of BM-CBJ2 for problems that AC-3 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.

MeasurementAC-3BM-CBJ2
Fewer Checks (number of cases)25975
Less Time (number of cases)277710
Average Number of Checks234103755
Minimum Number of Checks9876137
Maximum Number of Checks42086134394
Average Time (CPU + System) (seconds)1.771.72
Minimum Time (CPU + System) (seconds)1.571.39
Maximum Time (CPU + System) (seconds)1.985.24

AC-3 vs. BM-CBJ2: Zebra

MeasurementAC-3BM-CBJ2
Fewer Checks (number of cases)124876
Less Time (number of cases)417573
Average Number of Checks89090139170
Minimum Number of Checks33529294
Maximum Number of Checks16439161250399
Average Time (CPU + System) (seconds)2.164.67
Minimum Time (CPU + System) (seconds)1.831.50
Maximum Time (CPU + System) (seconds)2.561145.12

AC-3 vs. BM-CBJ2: Sherlock

What is most interesting about the results is the fact that in a small number cases BM-CBJ2 is much worse than AC-3, so much so that for Sherlock most of the performance measures look worse for BM-CBJ2 than AC-3 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.

Hypothesis 5

The hypothesis that BM-CBJ2 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: BM-CBJ2 < 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.

AlgorithmBM-CBJ2MutateXoverDoubleX
BM-CBJ2--500500500500500500
Mutate00--83917377
Xover00417408--227223
DoubleX00427423273277--

Times one algorithm (row) bettered another (column)

MeasurementBM-CBJ2MutateXoverDoubleX
Average Number of Checks35541258885538974293315161
Minimum Number of Checks412541110379620499423
Maximum Number of Checks15093132081622323868611212341720
Average Time (CPU + System) (seconds)2.1762.6522.0019.30
Minimum Time (CPU + System) (seconds)1.825.444.665.14
Maximum Time (CPU + System) (seconds)6.49686.841603.49986.12

Zebra, BM-CBJ2 vs Mutate vs Xover vs DoubleX

Conclusions and Future Work

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 currerent solution (using AC-3 for strongly k-consistent generation and CBJ-Multi for ‘totally random’ problems) was developed.

The genetic algorithm development proved easier although a genetic algorithm which bested BM-CBJ2 was not found in producing this paper (a possible route to take for this is to make the chromosones more complex, rather than simply being the solution to the bcsp). BM-CBJ2 proved to be the best complete (i.e. works for all problems) algorithm as AC-3 cannot always find a solution, but for strongly k-consistent problems AC-3 was found to be the better choice for both the Zebra and the Sherlock problems. If determining k-consistency 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 cross-section of real-world 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 k-consistent (and therefore solveable by AC-3).

Additional questions include the value of AC-3 preprocessing, which according to [Kumar92] is a common practise, and how BM-CBJ2 stacks up against both other backtracking algorithms ( [Kondrak97]proves that BM-CBJ2 performs fewer constraint checks but whether is is faster depends on whether the reduction in constraint checking comes with a greater overhead cost). BM-CBJ2 also needs to be compared to other algorithms out there. In addition, this paper makes no attempt to compare variable instantiation orders for BM-CBJ2, and it is known that variable instantiation order can have a significant performance impact on backtracking and backjumping algorithms [Prosser93].

Bibliography

[Kondrak94] Kondrak Grzegorz A Theoretical Evaluation of Selected Backtracking Algorithms. Technical Report TR94-10, University of Alberta Fall 1994.

[Kondrak97] Kondrak Grzegorz van Beek Peter A Theoretical Evaluation of Selected Backtracking Algorithms. Artificial Intelligence 89: 365-387, 1997.

[Kumar92] Kumar Vipin Algorithms for Constraint Satisfaction Problems: A Survey. AI Magazine Vol 13, Issue 1: 32-44, 1992.

[Prosser93] Prosser Patrick Hybrid Algorithms for the Constraint Satisfaction Problem Computational Intelligence Vol 9, Number 3: 268-299, 1993.

Sample Sherlock Problem

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 not-next-same 2
                1 not-equal 2
                1 not-equal 3
                1 not-equal 4
                1 not-equal 5
                1 not-equal 6
                1 not-next-to 14
                1 not-same-col 26
                1 same-col 33
                2 not-next-same 1
                2 not-equal 1
                2 not-equal 3
                2 not-equal 4
                2 not-equal 5
                2 not-equal 6
                2 left-of 13
                2 left-of 25
                2 not-next-to 35
                3 not-equal 1
                3 not-equal 2
                3 left-of 4
                3 not-equal 4
                3 not-equal 5
                3 not-equal 6
                3 next-right 30
                3 not-next-same 36
                4 not-equal 1
                4 not-equal 2
                4 right-of 3
                4 not-equal 3
                4 not-equal 5
                4 not-equal 6
                4 not-same-col 19
                4 not-same-col 20
                4 not-next-to 25
                4 right-of 30
                5 not-equal 1
                5 not-equal 2
                5 not-equal 3
                5 not-equal 4
                5 not-equal 6
                5 not-same-col 14
                5 not-next-same 25
                5 not-same-col 33
                5 next-to 34
                6 not-equal 1
                6 not-equal 2
                6 not-equal 3
                6 not-equal 4
                6 not-equal 5
                6 not-next-to 17
                6 not-next-to 24
                6 not-same-col 29
                7 not-equal 8
                7 not-equal 9
                7 not-equal 10
                7 not-equal 11
                7 not-equal 12
                7 not-next-to 15
                7 left-of 22
                7 left-of 28
                7 left-of 35
                8 not-equal 7
                8 not-equal 9
                8 not-equal 10
                8 not-equal 11
                8 not-equal 12
                8 not-same-col 17
                8 not-next-same 22
                8 not-same-col 33
                9 not-equal 7
                9 not-equal 8
                9 not-equal 10
                9 not-equal 11
                9 not-equal 12
                9 not-same-col 21
                10 not-equal 7
                10 not-equal 8
                10 not-equal 9
                10 not-equal 11
                10 not-equal 12
                10 not-same-col 32
                10 not-next-to 34
                10 same-col 34
                11 not-equal 7
                11 not-equal 8
                11 not-equal 9
                11 not-equal 10
                11 not-equal 12
                11 not-next-same 15
                11 next-to 33
                12 not-equal 7
                12 not-equal 8
                12 not-equal 9
                12 not-equal 10
                12 not-equal 11
                12 next-right 16
                12 not-same-col 23
                13 right-of 2
                13 next-left 14
                13 not-equal 14
                13 not-equal 15
                13 not-equal 16
                13 not-equal 17
                13 not-equal 18
                13 not-next-same 25
                13 not-same-col 30
                13 not-next-to 31
                13 not-next-to 36
                14 not-next-to 1
                14 not-same-col 5
                14 next-right 13
                14 not-equal 13
                14 not-equal 15
                14 not-equal 16
                14 not-equal 17
                14 not-equal 18
                15 not-next-to 7
                15 not-next-same 11
                15 not-equal 13
                15 not-equal 14
                15 not-equal 16
                15 not-equal 17
                15 not-equal 18
                15 not-next-same 20
                15 right-of 25
                15 not-same-col 36
                16 next-left 12
                16 not-equal 13
                16 not-equal 14
                16 not-equal 15
                16 not-equal 17
                16 not-equal 18
                16 not-same-col 31
                16 not-next-same 34
                16 next-to 35
                16 next-left 35
                17 not-next-to 6
                17 not-same-col 8
                17 not-equal 13
                17 not-equal 14
                17 not-equal 15
                17 not-equal 16
                17 not-equal 18
                17 not-next-to 21
                17 not-same-col 24
                17 not-next-same 26
                18 not-equal 13
                18 not-equal 14
                18 not-equal 15
                18 not-equal 16
                18 not-equal 17
                18 next-left 21
                18 not-next-same 22
                19 not-same-col 4
                19 right-of 20
                19 not-next-same 20
                19 not-equal 20
                19 not-equal 21
                19 not-equal 22
                19 not-equal 23
                19 not-equal 24
                19 not-same-col 29
                20 not-same-col 4
                20 not-next-same 15
                20 left-of 19
                20 not-next-same 19
                20 not-equal 19
                20 not-equal 21
                20 not-equal 22
                20 not-next-same 23
                20 not-equal 23
                20 left-of 24
                20 not-equal 24
                20 not-next-same 32
                20 not-next-to 36
                21 not-same-col 9
                21 not-next-to 17
                21 next-right 18
                21 not-equal 19
                21 not-equal 20
                21 not-equal 22
                21 not-equal 23
                21 not-equal 24
                21 not-next-to 27
                22 right-of 7
                22 not-next-same 8
                22 not-next-same 18
                22 not-equal 19
                22 not-equal 20
                22 not-equal 21
                22 not-equal 23
                22 not-equal 24
                22 not-next-same 27
                23 not-same-col 12
                23 not-equal 19
                23 not-next-same 20
                23 not-equal 20
                23 not-equal 21
                23 not-equal 22
                23 not-equal 24
                23 not-next-same 33
                24 not-next-to 6
                24 not-same-col 17
                24 not-equal 19
                24 right-of 20
                24 not-equal 20
                24 not-equal 21
                24 not-equal 22
                24 not-equal 23
                24 not-same-col 29
                25 right-of 2
                25 not-next-to 4
                25 not-next-same 5
                25 not-next-same 13
                25 left-of 15
                25 not-equal 26
                25 not-equal 27
                25 not-equal 28
                25 not-equal 29
                25 not-equal 30
                25 not-next-to 31
                26 not-same-col 1
                26 not-next-same 17
                26 not-equal 25
                26 not-equal 27
                26 not-equal 28
                26 not-equal 29
                26 not-equal 30
                26 next-to 33
                27 not-next-to 21
                27 not-next-same 22
                27 not-equal 25
                27 not-equal 26
                27 not-equal 28
                27 not-equal 29
                27 not-equal 30
                28 right-of 7
                28 not-equal 25
                28 not-equal 26
                28 not-equal 27
                28 not-equal 29
                28 not-equal 30
                28 same-col 34
                29 not-same-col 6
                29 not-same-col 19
                29 not-same-col 24
                29 not-equal 25
                29 not-equal 26
                29 not-equal 27
                29 not-equal 28
                29 not-equal 30
                30 next-left 3
                30 left-of 4
                30 not-same-col 13
                30 not-equal 25
                30 not-equal 26
                30 not-equal 27
                30 not-equal 28
                30 not-equal 29
                30 left-of 35
                31 not-next-to 13
                31 not-same-col 16
                31 not-next-to 25
                31 not-equal 32
                31 not-equal 33
                31 not-equal 34
                31 not-equal 35
                31 not-equal 36
                32 not-same-col 10
                32 not-next-same 20
                32 not-equal 31
                32 not-equal 33
                32 not-equal 34
                32 not-equal 35
                32 not-equal 36
                33 same-col 1
                33 not-same-col 5
                33 not-same-col 8
                33 next-to 11
                33 not-next-same 23
                33 next-to 26
                33 not-equal 31
                33 not-equal 32
                33 not-equal 34
                33 not-equal 35
                33 not-equal 36
                34 next-to 5
                34 not-next-to 10
                34 same-col 10
                34 not-next-same 16
                34 same-col 28
                34 not-equal 31
                34 not-equal 32
                34 not-equal 33
                34 not-equal 35
                34 not-equal 36
                35 not-next-to 2
                35 right-of 7
                35 next-to 16
                35 next-right 16
                35 right-of 30
                35 not-equal 31
                35 not-equal 32
                35 not-equal 33
                35 not-equal 34
                35 not-same-col 36
                35 not-next-same 36
                35 not-equal 36
                36 not-next-same 3
                36 not-next-to 13
                36 not-same-col 15
                36 not-next-to 20
                36 not-equal 31
                36 not-equal 32
                36 not-equal 33
                36 not-equal 34
                36 not-same-col 35
                36 not-next-same 35
                36 not-equal 35

  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.

If you wish you can download the source code for selected algorithms against the Sherlock and Zebra problems and related programs.