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

Fig. 6.7 ANew
CA ( 24 , 2 12

000000000000
000100011111
001001100111
001110101001
010010110011
010101101010
011001011001
011100110100
100011001011
100101110001
101000111010
101101001100
110000101101
110110011000
111011100000
111100000011
000011111100
001111010010
010111000101
011010001110
100110100110
101010010101
110001010110
111111111111

, 4 )

6.4 Backtracking Search for Generating Orthogonal Arrays

Since orthogonal arrays are a special kind of covering arrays, their generation tech-
niques resemble a lot. However, if we encode the requirements on orthogonal arrays
using propositional formulas, there will be too many variables and clauses. Thus it
is not wise to transform the whole problem into the satisfiability problem and use a
SAT solver to find an orthogonal array.
In this section, we describe an approach proposed by Ma and Zhang [ 5 ]. A related
work is done by Schoen, Eendebak and Nguyen [ 8 ] who proposed an algorithm to
enumerate a minimum complete set of non-isomorphic orthogonal arrays. We shall
not describe that algorithm in detail, because in software testing, we usually need
just one orthogonal array.

6.4.1 Preprocessing

Assume that we are trying tofind anOA s k

are sorted in non-increasing order. Noticing the fact that in the first t columns all
combinations of s 1 ,...,

( N , s 1 · s 2 ... s k , t ) , and the levels s 1 , s 2 ,...,

N
s 1 ×···×

λ =

s t times, we can gen-
erate an init-block directly by enumerating all possibilities, each of which

s t symbols should appear

λ

times.