Generating Crossword Grids Using Constraint Programming
A crossword is a puzzle where a grid of white and black squares must be filled with letters in order to form valid words across in the rows and down in the columns. We will build a constraint programming model to generate crossword grids. The goal of this blog post is to show the thought process that goes into modeling a non-trivial problem. We start small and tackle the modeling difficulties one at a time, adding more components to the model along the way.
To model this problem we will use CP-SAT, from the OR-Tools optimization suite. The input for this model consists of a word list and a grid size, and our plan is for the model to describe a valid grid of the given size containing words from the word list. First, we initialize the model and the parameters.
We start with a small 2×5 grid to test the model as we're building it. The word list is a file with one word per line. Since the solver only works with integers, we want to convert the letters of the words to integers, i.e., A=1, B=2, etc.
