Generate Random Problems

Jump to Table of Contents

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

Table of Contents