Search Lessons Learned from Crossword Puzzles
Abstract
The construction of a program that generates crossword puzzles is discussed. The aim of this research is to draw conclusions that apply to conjunctive search generally, and the experimental results obtained in the crossword-puzzle domain lead us to the following: (1) Lookahead is extremely important when solving conjunctive queries, (2) Compile-time control of search is far less effective than its run-time counterpart, and (3) Connectivity is best used as a backtracking heuristic and not as a heuristic that determines which of a particular set of conjuncts should be expanded next. 1 Introduction Appearances notwithstanding, this is not a paper about crossword puzzles. It is a paper about search. More specifically, it is a paper about conjunctive search in large databases. What we have done is to write a program that generates crossword puzzles by filling words into an empty frame. For frame sizes greater than 4 \\Theta 4, the associated search space is large enough to make brute force ...
Cite
Text
Ginsberg et al. "Search Lessons Learned from Crossword Puzzles." AAAI Conference on Artificial Intelligence, 1990. doi:10.1530/jrf.0.0420575Markdown
[Ginsberg et al. "Search Lessons Learned from Crossword Puzzles." AAAI Conference on Artificial Intelligence, 1990.](https://mlanthology.org/aaai/1990/ginsberg1990aaai-search/) doi:10.1530/jrf.0.0420575BibTeX
@inproceedings{ginsberg1990aaai-search,
title = {{Search Lessons Learned from Crossword Puzzles}},
author = {Ginsberg, Matthew L. and Frank, Michael and Halpin, Michael P. and Torrance, Mark C.},
booktitle = {AAAI Conference on Artificial Intelligence},
year = {1990},
pages = {210-215},
doi = {10.1530/jrf.0.0420575},
url = {https://mlanthology.org/aaai/1990/ginsberg1990aaai-search/}
}