Tiered State Expansion in Optimization Crosswords


  • Adi Botea Eaton
  • Vadim Bulitko University of Alberta




Crosswords, Constraint Optimization, Search


Crosswords puzzles continue to be a popular form of entertainment. In Artificial Intelligence (AI), crosswords can be represented as a constraint problem, and attacked with a combinatorial search algorithm. In combinatorial search, the branching factor can play a crucial role on the search space size and thus on the search effort. We introduce tiered state expansion, a completeness-preserving technique to reduce the branching factor. In problems where the successors of a state correspond to the values in the domain of a state variable selected for instantiation, the domain is partitioned into two subsets called tiers. The instantiation of the two tiers is performed at different times, with tier 1 first and tier 2 in a subsequent state. Before a tier-2 instantiation occurs, its set of applicable values can shrink substantially due to constraint propagation, with a corresponding reduction of the branching factor. We apply tiered state expansion to a constraint optimization problem modeled on the Romanian Crosswords Competition, empirically demonstrating a substantial improvement. Tiered state expansion allows finding a full solution, with an average CPU time of up to 1.2 minutes, to many puzzles that would otherwise time out after 4 hours.




How to Cite

Botea, A., & Bulitko, V. (2022). Tiered State Expansion in Optimization Crosswords. Proceedings of the AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment, 18(1), 79-86. https://doi.org/10.1609/aiide.v18i1.21950