Backtracking Search - Automatic Generation of Combinatorial Test Data - page 67

answer is positive. All of the four strategies can be combined to guide the searching
without losing any non-isomorphic solution.
Since SCEH only restricts the frequency of each sub-combination, it has no in-
fluence on the other three strategies. Now we shall show that if a CA problem has
a solution, then we can always find at least one matrix which contains an init-block
and satisfies the constraints of double lexicographic order and LNH.
Suppose matrix A is a solution to a CA problem. First the rows are permuted
so that in the first b rows, each value combination from the first t columns occurs
exactly once, and these b rows are in non-descending lexicographic order (i.e., for
all 0 b , R i ≤ lex R i + 1 ). Now A is a CA with an init-block.

Then A is adjusted with the following four operations until all constraints of
double lexicographic order and LNH are satisfied. All these operations preserve that
A is a solution:

< i <

• Sort the columns outside the init-block so that the columns with the same level are

in non-descending lexicographic order.

• Sort the rows outside the init-block in non-descending lexicographic order.

• If R i 1 ( i 1 b ) share the same values in the first t cells, and

R i 1 > lex R i 2 , then swap R i 1 with R i 2 .

≤ b ) and R i 2 ( i 2 >

• In column C j ( t k ), denote the position of the first appearance of symbol s in

C j by FA s . If there are two symbols s 1 and s 2 such that s 1 <

< j ≤

s 2 and FA s 1 > FA s 2 ,

permute s 1 and s 2 .

The order of these operations is not important.
If we regard the matrix A as a vector

A =[ R 1 , R 2 ,..., R N ]

=[ ce 1 , 1 ,..., ce 1 k ,..., ce N , 1 ,..., ce N , k ] ,

then each adjustment makes A lexicographically smaller. Since the number of ma-
trices is bounded, the procedure will come to an end. Finally all the constraints are
satisfied.

6.3.6 Constraint Propagation

When searching for a CA, the requirments of CA and the SCEH strategy can be
directly utilized to detect inconsistency in constraint propagation. In order to reveal
deeper inconsistency, we need more insight into the structure of the problem. Here
we introduce a method based on graph theory.
Suppose we are processing column c . Consider a column combination C contain-
ing column c .Weuse X to represent the set of uncovered value combination of C
and Y to denote the set of unassigned cells. We can build a bipartite graph G with X
and Y as partite sets. The edges are defined as coverage relations: there is an edge