# Tries-Based Parallel Solutions for Generating Perfect Crosswords Grids
## 4 Tries-Based Solutions
### Parallel Implementation
Seven experiments have been conducted for seven different given words, and the resulting grids obtained through these experiments are given in Appendix A. The execution times were as follows:

* **Experiment 1** The given word \"ABACA\". The sequential execution time \(T_{1}^{s}=6.1\) s. The sequential execution time \(T_{1}^{p}=0.9\) s.
* **Experiment 2** The given word \"XEROFAG\". The execution time \(T_{2}^{s}=9.1\) s. The execution time \(T_{2}^{p}=3.5\) s.
* **Experiment 3** The given word \"ABERANT\". The execution time \(T_{3}^{s}=1199\) s. The execution time \(T_{3}^{s}=95.1\) s.
* **Experiment 4** The given word \"INSECABIL\". The execution time \(T_{4}^{s}=648.4\) s. The execution time \(T_{4}^{p}=350.4\) s.
* **Experiment 5** The given word \"ABATORIZA\". The execution time \(T_{5}^{s}=4191s=69.85\) min. The execution time \(T_{5}^{p}=308.5\)s.
* **Experiment 6** The given word \"ABATORIZAT\". The execution time \(T_{6}^{s}=4834s=80.56\) min. The execution time \(T_{6}^{s}=427.6\) s.
* **Experiment 7** The given word \"ZACAMANT\". The execution time \(T_{7}^{s}=2131s=35.51\) min. The execution time \(T_{7}^{p}=383.9\) s.

The execution times of the parallel and sequential executions for each experiment are depicted in Figure 3, and the resulting speed-up obtained through parallelisation is shown in Figure 4.

**Remark 1**. : _It can be seen that for the Experiment 2--word \"XEROFAo\"--the solution was found very fast because the first letter \(X\) restrains the searching space; there are only a few words that start with \(X\)._

_Experiments 5 and 6 had long sequential execution times since in these cases the searching space is quite large--there are many words starting with the letter \(A\). They also emphasize the need for parallelisation. The parallel implementation manages to obtain the solution in much less time._

_There is a correspondence between the amount of sequential computation and the level of speed-up through parallelisation: when the sequential computation was high the speed-up obtained through parallelisation was also high._

Figure 4: The speed-up obtained through parallelisation for each experiment. Figure 3: The execution time of parallel and sequential executions for each experiment (time expressed in seconds). ## 6 Conclusions and Further Work

The presented computation solution based on tries dramatically reduces the time complexity of the solution for determining perfect crossword grids that start with a given keyword placed in the first column. With this solution, the usefulness of _tries_ is enforced, proving once more to be an exceptional conceptual and practical tool. This method has unique advantages due to the new proposed representation of the tries that use binary codes attached to each node (which reflect the possible continuation); these codes facilitate a very fast verification of the possible paths to follow. The solution offers a good parallelisation opportunity, and our experiments proved that very good speed-ups could be achieved through this parallelisation. The parallel solution could be easily adapted such that the maximum degree of parallelism can be increased; this depends on the size of the tuple of letters that each one of the processes considers to be fixed on the first cells that should be filled. This is also a very good premise for achieving a good scalability. The initial analysis of the proposed problem emphasized a very high level of complexity that qualifies the problem for use in cryptography systems. Without a \"smart\" solution, such as the proposed one that uses tries, the complexity of the direct approaches for computing a perfect crossword grid would have been enough in order to qualify the problem for such systems.