Extended Seeds in Optimization Crosswords

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 from two lists, the thematic list and the regular list, can be utilized. 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 AI approach to the problem constructs seeds, partial solutions with a high density of points in a subarea of the grid. Seeds are then completed to full solutions via a stochastic search. We present an approach to significantly extend the size of a seed which makes completion via stochastic search more successful. Experiments demonstrate an improvement of the completed solutions over published state-of-the-art algorithms.