# Tries-Based Parallel Solutions for Generating Perfect Crosswords Grids
## 1 Introduction  
Crosswords are known as a form of intellectual game, and they are widespread throughout the world. The most common crosswords are generally presented on grids that do not necessarily have equal sides. Many of them have black cells because it is very difficult to create such grids otherwise.  
In addition to the typical crosswords grids, there are some very special ones that we intend to refer to, such as:  
_Perfect Grids_: crosswords grids with no black boxes, where the words are considered in two directions, from left to right and from up to down.  
The computation used in the crossword domain follows different directions: generating new grids (without any clues), automatic clue generation, solving grids starting from clues, etc. Our focus is on the first one applied to perfect grids.  
A general crossword grid generation is considered an NP-complete problem [1]. This is why we investigate if it could be a good candidate to be used by cryptography algorithms. As for prime number factorisation, the difficulty does not necessarily rely on the theoretical difficulty of problem solving, but on the time needed to practically solve the problem. The possible usage of the crosswords in cryptography was considered a long time ago [2].  
There are different solutions--brute-force, backtracking based, heuristics, different constraint-satisfaction algorithms--but when we arrive at the time-complexity evaluation, we discover that it is very difficult to obtain concrete solutions for large dictionaries cases.  
In order to reduce the execution time, we can try to reduce the searching space by using different approaches and heuristics, but we can also apply different parallelisation techniques.  
Because of the problem's intrinsic nature, the solutions generally allow a high degree of parallelism. Still, it is possible that the reduced time complexity obtained only through parallelisation would not be enough, or at least if the degree of parallelism is highly bounded because of the concrete implementation architecture constraints, other optimisations should be investigated, too.  
We intend to investigate the problem of generating all the perfect crosswords grids, for a given keyword, which is to be placed in the first column. This could be considered simpler than the finding a solution for a given grid with white and black cells, but it depends much more on the grid size and the given keyword. Additionally, without the black cells, the number of possible choices that should be investigated increases very much. On the other hand, it is possible to not obtain any solution, or to have many solutions for different grid sizes (the number of columns could be allowed to vary).  
This special case was chosen in order to analyse it in the larger context of their possible usage in a public-key cryptography system [3]:  
The public and private keys could be based on the words of a perfect grid:  
* The word placed in the first column of the solution grid.
* The word in the \(i\)th (\(0\leq i\)) row of the solution;
* A preset combination of the solution rows.  
If there are more solutions for the word to be placed in the first column, then the solution with the largest weight sum in terms of characters is considered.  
In this paper, we propose a solution based on _tries_ (digital trees or prefix trees), which are a special kind of tree used especially for storing strings, and where there is one node for every common prefix; the final strings are represented through the path from the root to the leaf nodes [4]. The usage of tries led to a very efficient way of choosing possible words that could be placed in the grid.  
The solution offers good potential for parallelisation, too. The proposed parallel solution is a hybrid one based on multiprocessing (using MPI) and multithreading. The performance improvement through parallelisation is important and is proven by the speed-up seen in the concrete experiments.