Algorithm to create dense style crossword puzzles

Question

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:

https://www.aaai.org/Papers/AAAI/1990/AAAI90-032.pdf

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:

https://www.cs.rpi.edu/~dhulena/CS44FinalProjectReport.pdf

http://www.cs.columbia.edu/~evs/ais/finalprojs/steinthal/

http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.501.1743&rep=rep1&type=pdf

The basic setup of the algorithm is this:

1. 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.

2. 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".

3. 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:

1. 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.

2. 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.

3. 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.

4. 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.

Thank you.

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.

Answer 1

There may simply be no solution to some of these problem instances. And the fact that the problem is NP-hard means that you cannot expect to find any efficient algorithm to find solutions for large instances, even if they do exist.

That said, I suggest the following relaxation:

Idea: Map down to a smaller alphabet

Choose some $k < 26$, and map each of the 26 letters to one of the integers $1, \dots, k$. This mapping can work however you want -- you could try to keep roughly the same number of letters in each group, or not. These $k$ integers are a new, smaller "alphabet", in which each "letter" corresponds to the set of possible original letters A-Z that are mapped to it.

Map the dictionary words into this new alphabet. Try to solve the problem instance with your existing algorithm: You can do this without modifying your program, since it suffices to use some subset of the 26 letters to represent the integers in the new alphabet. If there is no solution to this "relaxed" problem, there is certainly no solution to your original problem.

OTOH, if there is a solution to this problem (and there will be if $k$ is small enough -- e.g., there definitely will be for $k=1$), then there is no guarantee that it can be converted back into solutions to your original problem, but it may be possible. Provided that $k$ is not too small, you now have a much more strongly constrained space for a recursive search to explore exhaustively, since in each position on the grid you are restricted to one of the letters mapped to that integer -- this should result in earlier cutoffs and a much faster search.

Note that it may be that the relaxed problem has multiple solutions, and the solution you initially find cannot be extended to a solution for the original problem -- but some other solution to the same relaxed problem can. So it may be worth exploring multiple solutions to the relaxed problem, if your program can do so.

One nice property of this approach is that it is very flexible: Since any mapping works, you can simply try again with a different one if extending a solution of the relaxed problem to the original problem fails. (If the relaxed problem itself has no solution, then you can stop: The original definitely has no solution.) Many different mappings can be tried independently in parallel.

I would initially try $k=2$ just to get a lower bound on how quickly a relaxed problem can be solved -- this may even be enough to get a useful speedup in the subsequent extension (assuming a solution is found!) Then I would try to choose $k$ as large as possible such that solving the relaxed problem completes in reasonable time. It's not obvious to me what kinds of mappings are best -- it might turn out to be helpful to group certain letters together, or to "preserve" some letters by making them the unique preimage of some integers.