Information Technology Reference
In-Depth Information
implies another value (returns TRUE) or if there is contradiction (returns FALSE).
The function
Chk_Cons
checks whether all the
t
-tuples have been covered in the
columns
if all the cells in column
c
have been assigned values. The function
CELL_Selection
chooses an unassigned cell and function
Val_Set_Gen
generates
the candidate value set
S
x
of a cell.
{
1
,...,
c
}
Algorithm 4
Backtracking Search BSrh(
pSol
,
Fmla
)
1:
if
!BPropagate(
pSol
,
Fmla
)
then
2: return
FA L S E
;
3:
end if
4:
if
!Chk_Cons(
pSol
,
Fmla
)
then
5: return
FA L S E
;
6:
end if
7:
if
every cell is assigned
then
8: return
TRUE
;
9:
end if
10:
x
= CELL_Selection(
pSol
);
11:
S
x
= Val_Set_Gen(
x
,
pSol
,
Fmla
);
12:
for
each value
u
in set
S
x
do
13:
if
BSrh(
pSol
∪{
x
=
u
}
,
Fmla
)
then
14: return
TRUE
;
15:
end if
16:
end for
17: return
FA L S E
;
6.3.3 Exploiting Symmetries in CA
Obviously two CAs with the same parameters are isomorphic if one can be obtained
from the other by a finite sequence of row permutations, column permutations and
permutations of symbols in each column.
2
5
Example 6.2
Figure
6.3
illustrates three instances of CA
.MatrixBis
obtained fromMatrix A by swapping the last two columns, and Matrix C is obtained
from Matrix A by swapping the first row with the fifth row. They are isomorphic to
each other.
(
6
,
,
2
)
Fig. 6.3
Three isomorphic
instances of CA
(a)
(b)
(c)
00000
01000
10011
11
101
00111
11110
00000
01000
10011
11
110
00111
11101
00111
01000
10011
11
101
00000
11110
2
5
(
6
,
,
2
)
Search WWH ::
Custom Search