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

Glossaries
Geometry

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
Harris, Geoffrey ; Forster, John. / On the bayesian estimation and computation of the number of solutions to crossword puzzles. Proceedings of the 1990 Symposium on Applied Computing. IEEE Computer Society, 1990. pp. 220-222
@inproceedings{c11784e0db5144999058abbb11f04865,
title = "On the bayesian estimation and computation of the number of solutions to crossword puzzles",
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.",
author = "Geoffrey Harris and John Forster",
year = "1990",
doi = "10.1109/SOAC.1990.82172",
language = "English",
pages = "220--222",
booktitle = "Proceedings of the 1990 Symposium on Applied Computing",
publisher = "IEEE Computer Society",
address = "United States",

}

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. IEEE Computer Society, pp. 220-222. https://doi.org/10.1109/SOAC.1990.82172

On the bayesian estimation and computation of the number of solutions to crossword puzzles. / Harris, Geoffrey; Forster, John.

Proceedings of the 1990 Symposium on Applied Computing. IEEE Computer Society, 1990. p. 220-222.

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

TY - GEN

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

AU - Harris, Geoffrey

AU - Forster, John

PY - 1990

Y1 - 1990

N2 - 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.

AB - 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.

U2 - 10.1109/SOAC.1990.82172

DO - 10.1109/SOAC.1990.82172

M3 - Conference contribution

SP - 220

EP - 222

BT - Proceedings of the 1990 Symposium on Applied Computing

PB - IEEE Computer Society

ER -

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