Table 2 demonstrates the performance of search algorithms on various crossword puzzles. We used benchmark puzzles from the papers by Ginsberg et al. Ginsberg90 and Beacham et al. bcsvB01. Four puzzles (15.06, 15.10, 19.03, 19.04) could not be solved by any of the algorithms within 2 hours of cpu time. Also, two puzzles (19.05 and 19.10) were arc inconsistent. In both cases GAC discovered the inconsistency slower than AC in HVE (around 3:1 time difference in 19.05 and 10:1 in 19.10) because the latter method discovered early the domain wipe-out of a dual variable.
In the rest of the puzzles we can observe that MHAC-2001 performs better than MGAC-2001 on the hard instances. For the hard insoluble puzzles MHAC-2001 is up to 3 times faster than MGAC-2001. This is mainly due to the large arity of the constraints in these classes6. Another interesting observation is that there can be significant differences between the performance of methods that may instantiate dual variables and those which instantiate only original ones. In many cases MAC-2001- managed to find a (different) solution than MHAC-2001 and MGAC-2001 earlier. On the other hand, MAC-2001- was subject to thrashing in some instances where other methods terminate. The fact that in all insoluble puzzles MAC-2001- did not do better than MHAC-2001 shows that its performance is largely dependent on the variable ordering scheme. In many cases MAC-2001- visited less nodes than MHAC-2001. However, this was not reflected to similar time performance difference because when a dual variable is instantiated MAC-2001- does more work than when an original one is instantiated. It has to instantiate automatically each original variable constrained with the dual variable and propagate these changes to other dual variables containing .
Nikolaos Samaras 2005-11-09