# Tries-Based Parallel Solutions for Generating Perfect Crosswords Grids
## 4 Tries-Based Solutions
### The Trie Solution
In addition, a position that indicates the current position in the grid completion is used:  
* _position_--a variable of type \(pair=[0..n]\times[0..m]\)\(([i,j]\) ). **The algorithm:** The algorithm is in essence a backtracking algorithm that fills the cells step by step in columns, starting with the first which is known. So, it is a letter-by-letter algorithm that relies on prefix verification. The \(M1\) and \(M2\) matrices are first initialized with the pointers to the nodes that correspond to the letters of the given word that should appear on the first column. In \(M2\), the nodes (from \(Tries[n]\)) follow a path that represents the given word, and in \(M1\) we will have pointers to the nodes from \(Tries[m]\) that correspond to the specified first letters in the rows. The letter in a new position \([i,j]\) is chosen from the letters obtained by the intersection of the set of the possible letters that allow horizontal words (it creates possible prefixes in rows)--given from the code stored in the node \(M1[i,j-1]\)--and the set of possible letters that allow vertical words (creates possible prefixes in columns)--given from the code stored in the node \(M2[i-1,j]\). The intersection is obtained by applying the _bit_and_ operation (denoted by &&) to the codes \(M1[i,j-1]\)_code and \(M2[i-1,j]\).code_, and it is stored in the \(M3[i,j]\).code_. The letters from this intersection are considered in order and the index of the current chosen letter is stored into \(M3[i,j]\)._index_. For the first letter in a column \(j\) the set of possible letters is given by \(M1[0,j-1]\)._code_; no intersection operation is needed. If the result of the && operation between the codes of the nodes stored into \(M1[i-1,j]\) and \(M2[i,j-1]\) is zero (the intersection is empty), then a step back is executed and the letter in the position \([i-1,j-1],if\ i\geq 1\) is changed by taking the next possible letter in the corresponding intersection set. Additionally, when all the possible letters from the intersection were verified, and moving forward is not possible, a step back is executed again. So, the back_step function is defined as:  
```
procedureback_step( ) \(position=\left\{ \begin{array}{ll}(position.i-1,position.j),&\text{if }position.i>0\\ (n-1,position.j-1),&\text{if }position.i=0\end{array} \right.\)
```  
The function SET_LETTER has the responsibility of setting a new letter in the current position. ```
functionset_letter( ) \(M3[position]\).index\(=\)first_index(\(M3[position]\).code) if(\(M3[position]\).index\(\
eq 0\)) then \(M1[position]=M1[\)left\((position)].array\_link[M3[position]\).index\(]\) if\(position.i>0\)then \(M2[position]=M2[\)UP(position).array\_link[M3[position]\).index\(]\) else \(\triangleright\) the root node corresponding to \(M3[position]\).index\(]\) letter in \(\mathbf{Tries[m]}\) \(M2[position]=\mathbf{Tries[m]}.array\_link[M3[position]\).index\(]\) return\(true\) else return\(false\)
```  
The function FIRST_INDEX returns the position of the first bit equal to 1 in the binary representation of \(M3[position]\).code and set it to 0; setting this bit to 0 is needed in order to emphasize that it has been verified. Additionally, in this way the next call of the function FIRST_INDEX will return the position of the next bit equal to 1. There is always a left position since we have a word in the first column, and the UP function will be called only when \(position.i>0\). ```
functionUP(position) \(up\_position=\left\{ \begin{array}{ll}(position.i-1,position.j),&\text{if $position.i>0$}\\ (n-1,position.j)-1,&\text{if $position.i=0$}\end{array} \right.\)return\(up\_position\) functionleft(position) \(left\_position=\left\{ \begin{array}{ll}(position.i,position.j-1),&\text{if $position.i>0\wedge position.j>0$} \end{array} \right.\)return\(left\_position\)
```  
The procedure \(move\_next\) moves the current position to the next cell in the grid, and sets the corresponding value of the _code_ attribute in \(M3\):  
```
proceduremove_next() \(position=\left\{