Crossword Puzzles

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.


Table 2: Comparison (in cpu time) between algorithms for the HVE and algorithms for the non-binary representation of crossword puzzles. $n$ is the number of words and $e$ is the number of blanks. All times are in seconds except those followed by ``m'' (minutes). A dash (--) is placed wherever the algorithm did not manage to find a solution within 2 hours of cpu time. Problems marked by (*) are insoluble. We only include problems that were reasonably hard for at least one algorithm and at the same time were solvable within 2 hours by at least one algorithm.
 puzzle   $n$   $e$   MGAC-2001   MHAC-2001   MHAC-2001-$full$  
 

15.02

  80   191   3.70   3.58   --  
 15.04*   76   193   40.84   38.88   29.75  
 15.07   74   193   94.65   46.36   44m  
 19.02   118   296   34.62   35.08   --  
 19.08   134   291   --   --   5.45  
 6$\times$6   12   36   9.39   5.07   5.49  
 7$\times$7*   14   49   14m   8m   12m  
 8$\times$8*   16   64   6m   2m   5m  
 10$\times$10*   20   100   11.81   11.85   15.39

 


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-$full$ managed to find a (different) solution than MHAC-2001 and MGAC-2001 earlier. On the other hand, MAC-2001-$full$ was subject to thrashing in some instances where other methods terminate. The fact that in all insoluble puzzles MAC-2001-$full$ did not do better than MHAC-2001 shows that its performance is largely dependent on the variable ordering scheme. In many cases MAC-2001-$full$ 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-$full$ does more work than when an original one is instantiated. It has to instantiate automatically each original variable $x_i$ constrained with the dual variable and propagate these changes to other dual variables containing $x_i$.

Nikolaos Samaras 2005-11-09