Crossword Puzzles

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.

	puzzle			$n$			$e$			MGAC-2001			MAC-2001			MAC-PW-AC
	15.02			80			191			3.98			164.04			13.70
	15.04*			76			193			40.84			895.29			140.65
	15.07			74			193			94.65			--			--
	15.09			82			187			0.43			--			--
	19.01			128			301			1.50			--			--
	19.02			118			296			34.62			--			1028.17
	19.08			134			291			--			33.01			7.76
	21.02			130			295			2.29			77.51			11.82
	21.03			130			295			345.96			273.87			40.57
	21.08			150			365			--			--			9.96
	21.09			144			366			--			--			8.87
	6$\times$6			12			36			9.39			98.49			6.04
	7$\times$7*			14			49			14m			--			12m
	8$\times$8*			16			64			6m			--			9m
	9$\times$9*			18			81			--			--			128.92
	10$\times$10*			20			100			11.81			474.54			22.78

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$\times$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.