Generating High-Score Crosswords Puzzles With Bi-Objective,Stochastic and Systematic Search

Abstract

The Romanian Crosswords Competition Problem is a challenging, NP-hard constraint optimization problem. The task is to fill a $13 \times 13$ grid with criss-crossing words and up to 26 black cells. Words come from two lists, thematic and regular. Each thematic word adds a number of points equal to its length to the score and the objective is to maximize the score. A recent artificial intelligence approach to the problem constructed seeds—partial solutions with a high density of points in a subarea of the grid. Seeds were then completed to full solutions via a stochastic portfolio search. In this paper, we significantly extend the size of a seed by repeatedly filling grid corners with letters and black cells. Thus a seed is extended with two corners filled out by two bi-objective searches. We further present a technique to systematically fill the remaining empty area of a seed that has already been extended into two corners in order to find the maximum possible solution score of the seed. The combination of algorithmic enhancements allows us to improve solution scores, which promises to reliably match or exceed top human scores in the future.

Keywords

optimization crosswords Romanian crosswords competition search

Get full access to this article

View all access options for this article.

References

Audemard

Lecoutre

Maamar

(2020). Segmented tables: An efficient modeling tool for constraint reasoning. In Proceedings of the 24th European conference on artificial intelligence (ECAI) (pp. 315–322).

Barlacchi

Nicosia

Moschitti

(2014). Learning to rank answer candidates for automatic resolution of crossword puzzles. In Proceedings of the 18th conference on computational natural language learning (pp. 39–48). Association for Computational Linguistics.

Beacham

Chen

Sillito

Beek

P.v.

(2001). Constraint programming lessons learned from crossword puzzles. In Proceedings of the 14th biennial conference of the Canadian Society on Computational Studies of Intelligence: Advances in artificial intelligence (pp. 78–87). Springer Verlag.

Botea

(2007). Crossword grid composition with a hierarchical CSP encoding. In Proceeding of the 6th CP workshop on constraint modelling and reformulation, ModRef-07.

Anbulagan, & Botea

(2008). Crossword puzzles as a constraint problem. In Proceedings of the 14th international conference on principles and practice of constraint programming (pp. 550–554). Springer.

Botea

, & Anbulagan. (2009). Analysing the behaviour of crossword puzzles. In Proceedings of the international symposium on combinatorial search (SoCS).

Botea

Bulitko

(2021). Scaling up search with partial initial states in optimization crosswords. In Proceedings of the international symposium on combinatorial search (SoCS) (pp. 20–27). AAAI Press.

Botea

Bulitko

(2022). Tiered state expansion in optimization crosswords. In Proceedings of the AAAI conference on artificial intelligence and interactive digital entertainment (AIIDE) (pp. 79–86).

Botea

Bulitko

(2023a). Core expansion in optimization crosswords. In Proceedings of the international symposium on combinatorial search (SoCS) (pp. 2–10). AAAI Press.

10.

Botea

Bulitko

(2023b). Generating and solving champion-level Romanian crosswords puzzles. In Proceedings of the IEEE conference on games (CoG) (pp. 1–4). IEEE.

11.

Botea

Bulitko

(2024). Extended seeds in optimization crosswords. In Proceedings of the IEEE conference on games (CoG) (pp. 1–8). IEEE.

12.

Bulitko

Botea

(2021). Evolving Romanian crossword puzzles with deep learning and heuristic search. In Proceedings of the IEEE conference on games (CoG) (pp. 1–5). IEEE.

13.

Chen

Liu

Jiang

Wang

Liang

Xiao

Zhang

Song

(2022). Crossword puzzle resolution via Monte Carlo tree search. In Proceedings of the international conference on automated planning and scheduling (ICAPS) (pp. 35–43). AAAI Press.

14.

Efrat

Shaham

Kilman

Levy

(2021). Cryptonite: A cryptic crossword benchmark for extreme ambiguity in language. In Proceedings of the conference on empirical methods in natural language processing (pp. 4186–4192). Association for Computational Linguistics.

15.

Ernandes

Angelini

Gori

(2005). WebCrow: A web-based system for crossword solving. In Proceedings of the national conference on artificial intelligence and the innovative applications of artificial intelligence conference (pp. 1412–1417). AAAI Press.

16.

Ginsberg

M. L.

(2011). Dr.Fill: Crosswords and an implemented solver for singly weighted CSPs. Journal of Artificial Intelligence Research, 42, 851–886. https://doi.org/10.48550/arXiv.1401.4597

17.

Kimbrough

S. O.

Koehler

G. J.

Wood

D. H.

(2008). On a feasible–infeasible two-population (FI-2Pop) genetic algorithm for constrained optimization: Distance tracing and no free lunch. European Journal of Operational Research, 190(2), 310–327. https://doi.org/10.1016/j.ejor.2007.06.028

18.

Lecoutre

Roussel

(2019). Proceedings of the 2018 XCSP3 competition. CoRR, abs/1901.01830.

19.

Littman

M. L.

Keim

G. A.

Shazeer

N. M.

(2002). A probabilistic approach to solving crossword puzzles. Artificial Intelligence, 134(1–2), 23–55. https://doi.org/10.1016/S0004-3702(01)00114-X

20.

Liu

Chen

Jiang

Wang

Zhang

Liang

Xiao

Song

(2024). A crossword solving system based on Monte Carlo tree search. Artificial Intelligence, 335. https://doi.org/10.1016/j.artint.2024.104192

21.

Mathworks. (2024). Box chart (Box Plot). https://www.mathworks.com/help/matlab/ref/boxchart.html

22.

Moschitti

Nicosia

Barlacchi

(2015). SACRY: Syntax-based automatic crossword puzzle resolution system. In Annual meeting of the association for computational linguistics (pp. 79–84). Association for Computational Linguistics and The Asian Federation of Natural Language Processing.

23.

Mouret

Clune

(2015). Illuminating search spaces by mapping elites. CoRR, abs/1504.04909 http://arxiv.org/abs/1504.04909

24.

Nicosia

Barlacchi

Moschitti

(2015). Learning to rank aggregated answers for crossword puzzles. In A. Hanbury, G. Kazai, A. Rauber, & N. Fuhr (Eds.), Advances in information retrieval (pp. 556–561). Springer Cham.

25.

Pohl

(1970). Heuristic search viewed as path finding in a graph. Artificial Intelligence, 1(3), 193–204. https://doi.org/10.1016/0004-3702(70)90007-x

26.

Rozner

Potts

Mahowald

(2021). Decrypting cryptic crosswords: Semantically complex wordplay puzzles as a target for NLP. CoRR, abs/2104.08620.

27.

Severyn

Nicosia

Barlacchi

Moschitti

(2015). Distributional neural networks for automatic resolution of crossword puzzles. In Proceedings of the 53rd annual meeting of the association for computational linguistics and the 7th international joint conference on natural language processing (volume 2: Short papers) (pp. 199–204). Association for Computational Linguistics.