Application of a Limit Theorem to the Construction of Japanese Crossword Puzzles

Volodymyr Novykov, Geoff Harris, Isaac Tonkin

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


The generation of crossword puzzles is known to be NP-Complete. Optimization over structural characteristics is known to extend this into the NP-Hard regime. This paper discusses the application of a limit theorem to assist in optimizing the NP-Hard aspects of crossword puzzle generation of Japanese lexicons in particular. It is shown that the similarity of artificially enumerated lexicons to Japanese kana-based lexicons is greater than to English language lexicons. This greater similarity is exploited in the derivation of expressions for both the expected value of the crossword and the use of the central limit theorem to determine an empirical estimate on the upper limit of the associated optimization problem. Initial empirical outcomes attest to the expected efficacy of the central limit theorem application to the final expressions.
Original languageEnglish
Title of host publicationAdvances and Trends in Artificial Intelligence. Theory and Practices in Artificial Intelligence
Subtitle of host publicationProceedings of the 35th International Conference on Industrial, Engineering and Other Applications of Applied Intelligent Systems, IEA/AIE 2022
EditorsHamido Fujita, Philippe Fournier-Viger, Moonis Ali, Yinglin Wang
Place of PublicationCham
Number of pages7
ISBN (Electronic)978-3-031-08530-7
ISBN (Print)978-3-031-08529-1
Publication statusPublished - 30 Aug 2022

Publication series

NameLecture Notes in Computer Science
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Dive into the research topics of 'Application of a Limit Theorem to the Construction of Japanese Crossword Puzzles'. Together they form a unique fingerprint.

Cite this