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

fifth column, violating the second constraint, hence Matrix B will not be encoun-
tered during the search. In Matrix C, the first row is lexicographically greater than
the fifth row, violating the third constraint, so Matrix C will be precluded too.

6.3.3.2 Symbol Symmetries

For an arbitrary column c in a CA, all the cells in c share the same domain D c =

{ 0 , 1 , 2 ,..., d c − 1 } , and these | D c | symbols are interchangeable, thus results in

2 | D c | −

1 symmetries. In constraint programming, symbol symmetries are also called
symmetries of indistinguishable values, which can be tackled by imposing value
precedence [ 4 , 9 ].
The LNH (Least Number Heuristic) [ 12 , 13 ] is a fairly simple yet powerful strat-
egy to impose value precedence in a dynamic way. It is based on the observation
that, at the early stages of the search, many symbols (which have not yet been used
in the search) are essentially the same. Thus when choosing a value for a new cell,
there is no need to consider all the symbols in the domain. It makes no difference to
assign the symbol e or e to the cell, if neither of them has been previously assigned.
When processing column c , all the unused symbols are indistinguishable for the
unassigned cells. We use a program variable mdn c to represent the largest symbol that
has been assigned in column c . Then the candidate domain for the next unassigned
cell is 1) is a representative of all currently

unused symbols. The variable mdn c is initially set to

{ 0 , 1 , 2 ,..., mdn c + 1 } . In fact, ( mdn c +

−

1 and dynamically updated
during the search. Since in the first t columns, all symbols are covered by the init-
block, LNH can only be applied to columns outside the init-block.
Acctually, the effect of LNH strategy is equivalent to imposing the following
constraint:

ce i + 1 , c ≤ MAX { ce 1 , c ,..., ce i , c }+ 1

where t < c < k and 0 < i < N .

6.3.4 Sub-combination Equalization Heuristic

Meagher and Stevens [ 6 ] conjectured that it is always possible to find a pairwise
CA where the symbols in a row have balanced frequencies of occurrence (which is
called Balanced Covering Array). Yan and Zhang [ 10 ] generalized the conjecture to
CAs of strength t and proposed a hypothesis named sub-combination equalization.
Based on observations, the hypothesis suggests that in any s ( s

t ) columns of the
CA, each value combination appears almost the same number of times.

<

Definition 6.3 ( Sub-combination ) In a CA, a sub-combination of size s is a vector
of s values from s columns, denoted as SC C , where V is the vector of values and C