snippetMinor
Algorithm to create dense style crossword puzzles
Viewed 0 times
createpuzzlesalgorithmstyledensecrossword
Problem
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:
-
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
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".
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:
-
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 ge
Solution
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.
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.
Context
StackExchange Computer Science Q#123618, answer score: 3
Revisions (0)
No revisions yet.