# Tries-Based Parallel Solutions for Generating Perfect Crosswords Grids
## 4 Tries-Based Solutions
### The Trie Solution  
The problem specification stipulates that the size of the grid should be equal to \(n\times m\), where \(n\) is the size of the given word that should be placed in the first column, and \(m\) is the number of columns of the optimal solution. If the optimisation function \(\Phi\) is defined to maximize the characters' weight sums, then it is very probable that an optimal solution will be obtained for big values of \(m\), and so an approach could start for the maximal value of \(m\), which decreases successively. The proposed solution follows a letter-by-letter approach, and the design analysis considers a specified size \(n\times m\) of the grid. **Data representation:** The words of the dictionary are represented using a complex data structure that contains \(max\_size\) tries; the number \(max\_size\) is equal to the maximum size of the words from the dictionary (e.g., \(max\_size=16\) for our dictionary). We have words that contains 1, 2,..., \(max\_size\) letters. This way, we have words represented only as full paths--from root to leaves--in the tries. The roots of the corresponding tries are stored in an array of lengths, \(max\_size\)--\(Tries[1..max\_size]\); so, \(Tries[n]\) is the root of the trie that stores the words with lengths equal to \(n\). The decision of using \(max\_size\) tries increases the space complexity, but facilitates a very good time complexity, since in order to fill a crossword grid, as specified in the problem specification, we need words of specific lengths. These tries could be created one time and stored, potentially as the first step of the algorithm. The time complexity of creating these tries is not very high since a single dictionary traversal is required; for each new word, the path corresponding to its letters is followed and new nodes (corresponding to the contained letters) are added when necessary. So, the time complexity is \(O(N)\) for this operation. For each trie, the first level contains an array of 26 roots for the words starting with each alphabet letter. We propose a special trie representation, in which each node of a trie contains:  
* A letter--_letter_;
* An array with a length equal to 26--\(array\_link\)--for the children nodes (one for each letter);
* A number--_code_--which is obtained from a binary representation with 26 digits that reflects the possible continuations:
* 0 on the position \(i\) means that there is not a subtrie corresponding the \(i\)th letter;
* 1 on the position \(i\) means that there is a subtrie corresponding the \(i\)th letter. Example: if for one particular node there are subtries that continue only with the letters \(A\) and \(D\), the _code_ will be 37748736, which has the following binary representation: 10010000000000000000000000. This binary code is very important in the fast verification of the possible letters that could be placed in a new position. For the node that represents the root of such a tree, the attribute \(letter\) is empty. The words are obtained from the leaf nodes and correspond to the letters on the path from root to them. In order to fill the crossword grid, three matrices (\(M1,M2\) and \(M3\)), which all have the same size as the grid (\(n\times m\)), are used:  
* \(M1\) memorizes pointers to the nodes from \(Tries[m]\) that correspond to each letter of the words written horizontally (on rows)s;
* \(M2\) memorizes pointers to the nodes from \(Tries[n]\) that correspond to each letter of the words written vertically (in columns);
* \(M3\) memorizes each position the index of the last letter put into the grid--\(M3[i,j]\)._index_, and the binary code of the possible letters that could be placed on that position--\(M3[i,j]\)._code_--this code is obtained through the intersection (and operation) of the binary codes stored in the corresponding pointed nodes of the firsttwo matrices. The type of the \(M3\) elements is defined by a data structure with two fields--\((index,code)\).