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

2 4 Fig. 6.8 OA ( 8 , , 3 )

0000
0011
0101
0110
1001
1010
1100
111 1

For example, in Fig. 6.8 ,the8 × 3 sub-array formed by the first three columns of

2 4 OA ( 8 , , 3 ) is an init-block.

6.4.2 The Basic Procedure

The approach is based on backtracking search, finding an OA column by column .It
can be described as a recursive procedure in Algorithm 5.

Algorithm 5 Backtracking Search bool Col_Sch( j )
1: cons = Cons_Gen( j , oaSol );
2: while TRUE do
3: column =Solve( cons );

4: null then

5: return FA L S E ;
6: end if
7: Append( column , oaSol );
8:

if column ==

if j == k or Col_Sch( j + 1) then

9: return TRUE ;
10: end if
11: Delete( column , oaSol );
12: add Negate( column )to cons ;
13: end while

Suppose we are processing the j th column and currently the obtained partial
solution is denoted by oaSol . The function Cons_Gen ( j ) generates some constraints
(denoted by cons in the pseudo-code) which are both necessary and sufficient for the
j th column to satisfy the OA requirments. Then the function Solve ( cons )triesto
find a solution (denoted by column ). If such a solution exists, it is added to oaSol by
the function Append . When all the k columns are generated, an OA is obtained and
the function returns TRUE . Otherwise, oaSol is not completed, and the procedure is
executed recursively. If there is no solution to the th column, the algorithm

backtracks to the j th column, deletes column from oaSol , and tries to generate another
solution.

( j + 1 )