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

Fig. 6.9 Stack of p-sets

Column P-set
12 { 1, 2 }{ 3, 4 }

{ 5, 6 }{ 7, 8 }

13 { 1, 3 }{ 2, 4 }

{ 5, 7 }{ 6, 8 }

23 { 1, 5 }{ 2, 6 }

{ 3, 7 }{ 4, 8 }

Since the first t columns of oaSol are fixed in advance, the search procedure starts
at column t + 1, and the first call of the recursive function is Col_Sch ( t + 1).

6.4.2.1 Constraint Generation

( ≥ )

Assume that we have constructed m columns m t . How can we generate the

constraints for column m + 1?

Theorem 6.2 An OA ( N , s 1 · s 2 ... s k , t ) is also an OA ( N , s 1 · s 2 ... s k , t − 1 ) .

1 columns from an OA and partition the row indices by the row
vectors in the subarray, we can get s j 1 ×···×

If we extract t −

s j t − 1 mutually exclusive sets of equal
size. Each set of the partition is called a p-set induced by the subarray.
Example 6.6 Consider the OA in Fig. 6.8 . After the init-block is constructed, the p-
sets are demonstrated in Fig. 6.9 . For each 8

2 subarray in the init-block, there are
four p-sets induced. More specifically, the p-set {1, 2} is induced by the sub-array of
column 1 and column 2 because row 1 and row 2 in the sub-array share the same row
vector

×

. Similarly, if we examine the rest row vectors of column 1 and column
2, we would get the partition

0 , 0

{{ 1 , 2 } , { 3 , 4 } , { 5 , 6 } , { 7 , 8 }} .

Theorem 6.3 An N × ( m + 1 ) matrix is an OA ( N , s 1 · s 2 ... s m · s m + 1 , t ) iff the

( ,

s 1 · s 2 ... s m ,

)

matrix A m formed by its first m columns is an OA N t , and for each

× ( − ) +

N t 1 subarray of A m ,thes m + 1 symbols in column m 1 are equally distributed

within the rows in each p-set induced by the subarray.

According to Theorem 6.3 , firstly we should calculate all p-sets induced by all

N × ( t − 1 ) sub-arrays from the first m columns, then the constraints for column

m 1 can be obtained directly.

After the constraints are obtained, they can be checked by an efficient SAT solver
or pseudo-Boolean constraint solver [ 5 ].

+

6.4.3 Exploiting Symmetries

Like CAs, OAs also have row & column symmetries as well as symbol symmetries.
For example, Fig. 6.10 illustrates two isomorphic OAs.