I am working on creating a program to generate dense American style crossword puzzles of grid sizes between 15x15 - 30x30. The database of words I'm using ranges between 20,000 and 100,000 words of all varying lengths. The current algorithm I'm using takes some inspiration from this paper:
Search Lessons Learned from Crossword Puzzles by Matthew L. Ginsberg Michael Frank Michael P. Halpin Mark C. Torrance
as well as several others who have written about the topic:
The basic setup of the algorithm is this:
Find the most constrained word i.e. the current word (which is not currently a valid word from the dictionary) which has the fewest possibilites. EX: J--Z has significantly fewer possibilites for fill than T--S so I'd expand J--Z and not T--S.
Once selecting the word with the fewest potential candidates. Iterate through the word's potential candidates. Continuously check if playing the current candidate allows for all of this word's intersecting words to have candidates. EX: if the grid was
# H A S
- E - -
- A - -
- T - #
and I was currently examining A--- then "AZIZ" is a potential fill but there are no words -TZ (intersecting word) and thus "AZIZ" would not be considered. Depending on how long the word is the algorithm will generate several different potential candidates before moving on to the next most constrained word. In the example above, perhaps ATIS, ARTS, ARFS all allow the words intersecting words to have candidates. The geometric mean of the intersecting words potential candidates is taken and the next word played is the candidate which maximizes this mean. I consider this be one level of "look ahead".
- If at any point we arrive to a word where no potential candidates can be generated then we backtrack (actually back jump). And the algorithm will move back to the point where the most recently played intersecting word's content is different. EX: in the grid below if we are examining ST- and zero potential candidates are found, the most recently played word is "PEET" and thus it will be removed and more potential candidates will be explored
# H A S
P E E T
- A - -
- T - #
would maybe become:
# H A S
P E T S
- A- -
- T - #
and we'd then be able to play:
# H A S
P E T S
- A - O
- T - #
This algorithm works great for simple grids (grids with shorter words on average and fewer total word intersections). For example this algorithm can solve a grid like this in 10-20 seconds
but as soon as I introduce a grid with the same dimensions but longer words with a larger number of intersections:
this algorithm becomes totally useless. It will never move past filling the 5-6 initially most constrained words (typically the central longest words as you would expect). I've never let the algorithm run for more than 59 minutes but it's never been able to find a solution (or even come close) to an open style grid like the one above.
So I am looking for ideas/solutions/heuristics to attempt to solve these more open (harder) grids. Some ideas/things I have already tried:
I added a "second level" of look ahead. When examining a word, find the geometric mean of the number of potential candidates for intersecting words, and then go one level deeper and find the geometric mean of the intersecting word (with all of its own potential candidates) intersecting words. I implemented this and the computation time was enormous and this drastically slowed down the solve time for the easier style puzzles. It also appeared to have 0 benefit when solving the harder grids.
When playing the first few long and highly intersected words have a preference for words which have "easier letters" (think of scrabble tiles which have lower point values) so have a preference for words which contain many R/S/T/L/M and very few J/Q/Z/X etc. I realize this might aid in solving but I'm not convinced it will work because letter position within each word matters more than general word contents. I did a quick and dirty test of this by only allowing dictionary words of 22/26 letters (no words with J/Q/Z/X) and this had no effect.
Use some sort of letter by letter approach instead of a word by word approach which I am currently using. Compute the potential words for every word in the grid, map each of those words specific letters to each cell, and then try a greedy approach which maximizes the size of set intersection of cells.
Parallelize the solving algorithm. Not convinced this will work either. I believe I'll just compute more solutions with a dead end in less time and not make any actual headway.
In my reading I've learned that this problem is NP-HARD (perhaps NP-complete reduced from vertex cover? Just a proof I saw, not really concerned with this). Additionally, I've learned this problem is characterized as a CSP. Any sort of input you may have in terms of improving the current algorithm (perhaps more or better heuristics) or an entirely different approach relating to CSPs I would love to hear your thoughts.
ps I could post videos of the algorithm in action or other examples of grids the algorithm can solve easily/fails to solve. Willing to provide any info needed.
Update: by increasing the amount of pre-processing at each successive step I am able to solve the above grid. In step 1 when calculating the most constrained word I find all possible candidate words for each remaining unfilled word, and map the possible candidates word's letter to each cell and do an intersection at each cell. This is beneficial because it better indicates the most constrained word and additionally eliminates more possible solution paths. However, this pre-processing makes the backjumping essentially useless. Using my dictionary of ~290K words I am able to solve the above grid but have still not cracked the upper echelon of the most constrained grids.