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	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()
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

See Also