N-queens
The problem of placing n queens on an (n x n) chessboard
is a classical problem where the model-oracle can be given
by three constraints (noted m_ct1,m_ct2 and m_ct3), the
first one insures that all queens are placed differently on their
column, the second and the third constraint insure that no
two queens are placed on the same upper or lower-diagonal
on the chessboard. We improved this model by adding new
data structures, redundant, surrogate and global constraints.
We have produced 7 different faulty CPUTs for
n-queens using fault injection.
tab3. Fault detection and localization of n-queens problem.
TEST | LOCALIZATION | ||||
---|---|---|---|---|---|
G.rulers | #_constr. | fault_injected | non.conf._detected | fault localization | time |
CPUT1 | 12 | p1_ct11 | sol(CPUT1)=emptyset | (rev(p1_ct11), emptyset) | 2.09s |
CPUT2 | 12 | p2_ct12 | sol(CPUT2)=emptyset | (rev(p2_ct12), emptyset) | 1.64s |
CPUT3 | 12 | p3_ct11 | sol(CPUT3)=emptyset | (rev(p3_ct11), emptyset) | 1.57s |
CPUT4 | 12 | p4_ct12 | sol(CPUT4)=emptyset | (rev(p4_ct12),emptyset) | 1.59s |
CPUT5 | 6 | p5_ct3 |
[1 5 1 1 4 8 8 4] | (rev(p5_ct3),emptyset) | 0.62s |
CPUT6 | 3 | p6_ct3 | [7 8 3 2 4 1 5 6] | (rev(P6), (m_ct2,m_ct3)) | 4.12s |
CPUT7 | 2 | p7_ct1 | [8 4 3 6 5 7 2 1] | (rev(P7),(m_ct2,m_ct3)) | 3.01s |
Correction:
- Mutant1 ==> (ct11, Emptyset)
- Mutant2==> (ct12, Emptyset)
- Mutant3==> (ct11, Emptyset)
- Mutant4==> (ct12, Emptyset)
- Mutant5==> (ct4, 28 EC )
- Mutant6==> (Emptyset, 56 EC)
- Mutant7==> (Emptyset, 56 EC)
All our experiments were performed on Intel Core2 Duo CPU 2.40Ghz machine with 2.00 GB of RAM.