The Romanian Crosswords Competition Problem is a challenging, NP-hard constraint optimization problem. The task is to fill a 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.
AudemardG.LecoutreC.MaamarM. (2020). Segmented tables: An efficient modeling tool for constraint reasoning. In Proceedings of the 24th European conference on artificial intelligence (ECAI) (pp. 315–322).
2.
BarlacchiG.NicosiaM.MoschittiA. (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.
3.
BeachamA.ChenX.SillitoJ.BeekP.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.
4.
BoteaA. (2007). Crossword grid composition with a hierarchical CSP encoding. In Proceeding of the 6th CP workshop on constraint modelling and reformulation, ModRef-07.
5.
Anbulagan, & BoteaA. (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.
6.
BoteaA., & Anbulagan. (2009). Analysing the behaviour of crossword puzzles. In Proceedings of the international symposium on combinatorial search (SoCS).
7.
BoteaA.BulitkoV. (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.
8.
BoteaA.BulitkoV. (2022). Tiered state expansion in optimization crosswords. In Proceedings of the AAAI conference on artificial intelligence and interactive digital entertainment (AIIDE) (pp. 79–86).
9.
BoteaA.BulitkoV. (2023a). Core expansion in optimization crosswords. In Proceedings of the international symposium on combinatorial search (SoCS) (pp. 2–10). AAAI Press.
10.
BoteaA.BulitkoV. (2023b). Generating and solving champion-level Romanian crosswords puzzles. In Proceedings of the IEEE conference on games (CoG) (pp. 1–4). IEEE.
11.
BoteaA.BulitkoV. (2024). Extended seeds in optimization crosswords. In Proceedings of the IEEE conference on games (CoG) (pp. 1–8). IEEE.
12.
BulitkoV.BoteaA. (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.
ChenL.LiuJ.JiangS.WangC.LiangJ.XiaoY.ZhangS.SongR. (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.
EfratA.ShahamU.KilmanD.LevyO. (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.
ErnandesM.AngeliniG.GoriM. (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.
GinsbergM. 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.
KimbroughS. O.KoehlerG. J.LuM.WoodD. 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.
LecoutreC.RousselO. (2019). Proceedings of the 2018 XCSP3 competition. CoRR, abs/1901.01830.
19.
LittmanM. L.KeimG. A.ShazeerN. 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.
LiuJ.ChenL.JiangS.WangC.ZhangS.LiangJ.XiaoY.SongR. (2024). A crossword solving system based on Monte Carlo tree search. Artificial Intelligence, 335. https://doi.org/10.1016/j.artint.2024.104192
MoschittiA.NicosiaM.BarlacchiG. (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.
NicosiaM.BarlacchiG.MoschittiA. (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.
RoznerJ.PottsC.MahowaldK. (2021). Decrypting cryptic crosswords: Semantically complex wordplay puzzles as a target for NLP. CoRR, abs/2104.08620.
27.
SeverynA.NicosiaM.BarlacchiG.MoschittiA. (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.
