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 classes⁶. 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$.