I'm given a matrix containing a blueprint of a crossword puzzle - unfilled, of course. The goal is to fill the whole puzzle - it's a task from Checkio, and I've been struggling with this for quite some time now.
From what I understand of complexity, there's no perfect algorithm for this problem. Still, there has to be the best way to do this, right? I've tried some different things, and results were not that good with increasing number of words in the crossword and/or dictionary.
So, some of the things I've tried:
And this is where I'm currently at. I decided to ask about this here as it's already at that point where I think it took more time than it should have, and even then my latest idea may not even be the proper way to do it.
So, what is the proper way to do it?
Edit: Input is a list of strings representing the crossword and a list of strings representing the dictionary. Output is a list of strings representing the filled crossword.
And example of a crossword:
['...XXXXXX',
'.XXX.X...',
'.....X.XX',
'XXXX.X...',
'XX...X.XX',
'XX.XXX.X.',
'X......X.',
'XX.X.XXX.',
'XXXX.....']
The output would be a similar list with filled letters instead of dots.
Note that the 'dictionary' is just that, a small English dictionary and not a list of words fitted as answers for this puzzle.
So, what is the proper way to do it?
I don't know if it is optimal, but I would be using the principles of Floodfill.
Data structures:
Crossword words and their intersections. Sort them by the number of words in the dictionary for the corresponding word length. This will most likely mean that you will start with one of the longest words.
Dictionary accessible by word length.
If the dictionary is large it would be beneficial to be able to quickly find words of a certain length with a specific n
:th letter, where n
corresponds to an intersection position.
Note that for each crossword word, any two words that fit and have the same letters in all intersections are equivalent. Thus, it is possible to select a subset from the dictionary for each crossword word. The subset is the set of equivalence classes. So for each crossword word you can create a subset of the dictionary that contains at most [the number of letters in the alphabet] to the power of [the number of intersections]. This subset would constitute the equivalence classes that might fit a particular crossword word.
Algorithm:
Take the first/next unsolved crossword word. Assign it the first/next word that fits.
Take the first/next intersection. Assign the other crossword word the first word that fits.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With