Search Lessons Learned from Crossword Puzzles

Matthew L. Ginsberg, Michael Frank, Michael P. Halpin, Mark C. Torrance

The construction of a program that generates crossword puzzles is discussed. As in a recent paper by Dechter and Meiri, we make an experimental comparison of various search techniques. The conclusions to which we come differ from theirs in some areas - although we agree that directional arc consistency is better than path-consistency or other forms of lookahead, and that backjumping is to be preferred to backtracking, we disagree in that we believe dynamic ordering of the constraints to be necessary in the solution of more difficult problems.


This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.