## Preface

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
2.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 IF
16 END
17 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
14 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
```