Generating and Solving Champion-Level Romanian Crosswords Puzzles
Adi Botea, Vadim Bulitko · 2023
The Romanian Crosswords Competition Problem is a challenging, NP-hard constraint optimization problem where state-of-the-art Artificial Intelligence has been lagging behind top human performance. The task is to construct a high-score grid with words from a thematic list, that changes every year, and from a regular list. Each thematic word in the solution gives a number of score points equal to its length. A recent approach to the problem generated grids with scores in the range of top human performance for the first time. However, such scores were obtained for only three years. We present new results with experiments on a larger scale, including an increase from three to eleven years. We produce grids with scores in the top-12 human range in six out of eleven years and discuss steps towards outperforming top humans.