On the bayesian estimation and computation of the number of solutions to crossword puzzles

Geoffrey Harris, John Forster

Research output: Chapter in Book/Report/Conference proceedingConference contributionResearchpeer-review

3 Citations (Scopus)

Abstract

There exist implemented algorithms which can provide all possible solutions to any crossword puzzle grid for any given set of words. A formula is derived, within a Bayesian framework, and it provides an estimate of the number of solutions which can be constructed from a given dictionary for any given crossword puzzle without direct recourse to computation of all solutions. The formula is constructed to account for any puzzle geometry and any given dictionary, natural language or otherwise. The number of solutions estimated by the formula, for a variety of puzzles and dictionaries, is compared with the actual number in each solution set. The formula is shown to be only partially effective but to be capable of further development. The formula is useful as an indicator of the time required for computing all solutions, if any exist.
Original languageEnglish
Title of host publicationProceedings of the 1990 Symposium on Applied Computing
PublisherIEEE Computer Society
Pages220-222
DOIs
Publication statusPublished - 1990
Externally publishedYes

    Fingerprint

Cite this

Harris, G., & Forster, J. (1990). On the bayesian estimation and computation of the number of solutions to crossword puzzles. In Proceedings of the 1990 Symposium on Applied Computing (pp. 220-222). IEEE Computer Society. https://doi.org/10.1109/SOAC.1990.82172