Wild Tech Garden
Doc

Generate random problems

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.

 1PROCEDURE GenerateStrongKProblem()
 2BEGIN
 3  row-permutations = generate-row-permutations()
 4  solution = generate-random-solution()
 5  1 = 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()
62END
 1PROCEDURE generate-random-solution()
 2BEGIN
 3FOR 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
11END
 1PROCEDURE has-one-solution()
 2BEGIN
 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
13END

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 behaviour 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 IF
  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;
 1FUNCTION cbj-label(i,consistent): INTEGER
 2BEGIN
 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)
16END;

GenerateRandomProblem

 1PROCEDURE GenerateStrongKProblem()
 2BEGIN
 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
19END GenerateStrongKProblem
 1PROCEDURE has-one-possible-solution()
 2BEGIN
 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
10END
 1PROCEDURE find-possible-clues()
 2BEGIN
 3  FOR vx = TO n
 4  DO BEGIN
 5    FOR vy = 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
16END find-possible-clues
Prev
Algorithms for solving Zebra and Sherlock
Next
Results for solving Zebra and Sherlock