Table 4 compares the cpu times of the two
MAC algorithms in the DE and MGAC in the non-binary 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
non-binary 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 MGAC-2001 or
MAC-PW-AC 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 MAC-PW-AC is significantly faster than MAC-2001 on all
instances. The speedup offered by the use of PW-AC 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 PW-AC 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 21
21 puzzles that we tried were solved by
any algorithm within the time limit of two hours. MAC-PW-AC
managed to solve these 4 instances relatively fast, while the
other two algorithms solved only 2 of them within the cpu limit.
Nikolaos Samaras
2005-11-09