Helps to solve a "Fill Word" puzzle.
"Fill words", also known as the "Hungarian crossword" puzzles - is a puzzle in which you want to find all the words inscribed in a square grid. At first glance, the letters are written randomly, but in fact, they are part of a word.
Words can be bent in any direction at a right angle but do not intersect with each other. To find the words you need to identify each of them with the mouse from the first letter to the last. After all the words in "Fill Word" unraveled, empty cells should not remain. When a word is selected correctly, it will appear in the lower list and obscured in the grid "Fill words".
You can find much of them here: Grand Fill Words Collection
You may see usage example in src/solver.py
# cd src
# python3 solver.py
2019-07-11 02:24:06,828 - root - INFO - Loaded 175025 words
2019-07-11 02:24:06,828 - root - INFO - Building word index...
2019-07-11 02:24:09,406 - root - INFO - Searching...
2019-07-11 02:24:09,409 - root - INFO - Found 21 words
2019-07-11 02:24:09,410 - root - INFO - Found words: 21
==== ландшафт (1) ====
# # # # # #
# # # # # #
# # # # # #
# # т # # #
# # ф а ш д
# # # л а н
==== агроном (1) ====
# # # # а #
# # # # г м
# # # # р о
# # # # о н
# # # # # #
# # # # # #
==== огород (1) ====
# # # # # #
о г о # # #
# о р # # #
# д # # # #
# # # # # #
# # # # # #
==== шалфей (2) ====
# # # # # #
# # # # # #
# # # # # #
# # # # # #
# й # # ш #
# е ф л а #
# # # # # #
# # # # # #
# # # # # #
# # # # # #
# й # а ш #
# е ф л # #
==== город (1) ====
# # # # # #
# г о # # #
# о р # # #
# д # # # #
# # # # # #
# # # # # #
<...>
This library implements special "Recursive Dict" data structure (which is something like a Trie data structure or "prefix search index"), effectively searching all dictionary words and their possible places, using Depth-First Search algorithm from each position.
Given a dictionary of known English words:
find
finding
fix
run
Yes, it's pretty small, but it's only for the purposes of the example.
Let's try to find all the words from the dictionary in the matrix!
Step -1. Build word index with all the words we know at all. It would look something like:
d = {
'f': {
'i': {
'n': {
'd': {
'i': {
'n': {
'g': {
None: {}, # mark meaning that `finding` ends here
},
},
None: {}, # mark meaning that `find` ends here
}
}
},
'x': {
None: {}, # mark meaning that `fix` ends here
}
}
},
'r': {
'u': {
'n': {
None: {}, # mark meaning that `run` ends here
}
}
}
} OK! We now have the effective word index (RecursiveDict in terminology of my code)
Step 0 Given matrix
f i x
d n r
k n u
Let's try to find all the words in it!
Step 1
- Starting from letter "f" in the top-left corner.
f * *
* * *
* * *
- Let's take a look inside the recursive dictionary. Hm... From letter "f" we can consume letters "i" and "x". OK.
list(d['f'].keys()) == ['i', 'x']d['f'] is
{
'i': {
'n': {
...
},
'x': {
...
}
}
}- Now we try to move to all possible directions, right and down, as for now. We have a letter "d" down, and letter "i" to the left
f i *
d * *
* * *
- So, we can't go down, because we can't consume letter "d" after "f" (it's because no words start with "fd").
'x' not in d['f']- But we can try, just try to consume letter "i" next, because some of the dictionary words start with "fi".
'i' not in d['f']- So we go left from "f", now we have "f" and "i" in out path. Now we have prefix "fi"
f i *
_ * *
* * *
d = f['i']Now d is
{
'n': {
'd': {
'i': {
'n': {
'g': {
None: {}, # mark meaning that `finding` ends here
},
},
None: {}, # mark meaning that `find` ends here, but we could possibly explore next to `finding`
}
}
},
'x': {
None: {}, # mark meaning that `fix` ends here
}
}Meaning having prefix "fi" we can explore only letters "n" or "x" next.
- OK. Let's move next. We can move right and down (but we can't go back in Depth-First Search)
f i x
_ n *
* * *
-
Okay, we have both "x" and "n" now in "d", so as DFS is recursive we have to split our search in two: one we'll try to explore the way down and another would go to the right. Let's only take a look for the move to the right.
-
Well, now we in cell with "x" having a path to it like "f" -> "i" -> "x".
f i x
_ * *
* * *
Our dictionary has a special mark (None keyword) meaning that this is the end of some word.
So we can add the word fix to the resulting found words list.
- But we can not stop yet! We have to move next because we could possibly have some words starting with "fix", but longer, like "fixing". Unfortunately, in this example, we can not find more words, because the only explorable way, "fixr" is not an English word, nor a prefix for some English word.
So, our search is ended here. We found a word "fix", although this algorithm would find a word "run" as well, but we would skip it in this example.
All dictionaries are loaded automatically.
You may place any word dictionaries (in UTF-8) in data/dictionaries folder.
Included zdf.txt is the Andrey Zaliznyak's words dictionary
got from here (but encoded to UTF-8).
Included engmix.txt is English words dictionary got from here (but without some strange words in the end).