Table 4 compares the cpu times of the two
MAC algorithms in the DE and MGAC in the nonbinary representation
using various benchmark crossword puzzles. We do not include
results for MAC in the double encoding since this particular
representation of crossword puzzle generation problems is
impractical. The reason for this is that for each pair of dual
variables involved in a constraint, the two variables have at most
one original variable in common (i.e. the letter on which the two
words intersect). As explained previously, this degrades the
filtering achieved by the constraints between dual variables. Such
constraints in the double encoding are redundant since the same
filtering can be achieved through the constraints between dual and
original variables.
Table 4:
Comparison (in
cpu time) between MAC algorithms for the DE and MGAC for the
nonbinary representation of crossword puzzles. All times are in
seconds except those followed by ``m'' (minutes). The cpu limit
was 2 hours. Problems marked by (*) are insoluble. We only include
problems that were reasonably hard for either MGAC2001 or
MACPWAC and at the same time were solvable within 2 hours by at
least one algorithm.

From the data in Table 4 we can clearly see
that MACPWAC is significantly faster than MAC2001 on all
instances. The speedup offered by the use of PWAC makes MAC in
the DE competitive with MGAC in many cases where using a generic
algorithm in the DE results in a clear advantage in favor of MGAC.
Also, in some instances (e.g. puzzles 21.03, 21.08, 21.09), the
use of PWAC makes MAC in the DE considerably faster than MGAC.
However, there are still some instances where MGAC (and
consequently MHAC) finds a solution (or proves insolubility) fast,
while MAC in the DE thrashes, and vice versa. Note, that only 4 of
the 10 very hard 2121 puzzles that we tried were solved by
any algorithm within the time limit of two hours. MACPWAC
managed to solve these 4 instances relatively fast, while the
other two algorithms solved only 2 of them within the cpu limit.
Nikolaos Samaras
20051109