Core Expansion in Optimization Crosswords


  • Adi Botea Eaton
  • Vadim Bulitko University of Alberta



Combinatorial Puzzles, Combinatorial Optimization, Constraint Search


In constraint optimization many problem instances remain challenging to current technology. We focus on the Romanian Crosswords Competition Problem. It is a challenging, NP-hard constraint optimization problem where state-of-the-art AI has been lagging significantly behind top human performance. We present an approach that first builds a core, a portion of the problem that will have a high contribution to the objective function. A core is grown into a seed, a partial solution with a subset of variables defined and instantiated. Seeds are further extended into full solutions. Our approach takes as input the size of a rectangular core to consider, and the locations of zero or more black cells inside the core. The results advance state-of-the-art substantially. We report a boost in the scores obtained, bringing our top solutions in the vicinity of top human entries.