{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,7]],"date-time":"2026-04-07T16:31:18Z","timestamp":1775579478069,"version":"3.50.1"},"reference-count":16,"publisher":"MDPI AG","issue":"1","license":[{"start":{"date-parts":[[2022,1,13]],"date-time":"2022-01-13T00:00:00Z","timestamp":1642032000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>A general crossword grid generation is considered an NP-complete problem and theoretically it could be a good candidate to be used by cryptography algorithms. In this article, we propose a new algorithm for generating perfect crosswords grids (with no black boxes) that relies on using tries data structures, which are very important for reducing the time for finding the solutions, and offers good opportunity for parallelisation, too. The algorithm uses a special tries representation and it is very efficient, but through parallelisation the performance is improved to a level that allows the solution to be obtained extremely fast. The experiments were conducted using a dictionary of almost 700,000 words, and the solutions were obtained using the parallelised version with an execution time in the order of minutes. We demonstrate here that finding a perfect crossword grid could be solved faster than has been estimated before, if we use tries as supporting data structures together with parallelisation. Still, if the size of the dictionary is increased by a lot (e.g., considering a set of dictionaries for different languages\u2014not only for one), or through a generalisation to a 3D space or multidimensional spaces, then the problem still could be investigated for a possible usage in cryptography.<\/jats:p>","DOI":"10.3390\/a15010022","type":"journal-article","created":{"date-parts":[[2022,1,13]],"date-time":"2022-01-13T10:57:37Z","timestamp":1642071457000},"page":"22","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Tries-Based Parallel Solutions for Generating Perfect Crosswords Grids"],"prefix":"10.3390","volume":"15","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-9981-0139","authenticated-orcid":false,"given":"Virginia","family":"Niculescu","sequence":"first","affiliation":[{"name":"Department of Computer Science, Faculty of Mathematics and Computer Science, \u201cBabe\u015f-Bolyai\u201d University, 400084 Cluj-Napoca, Romania"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Robert Manuel","family":"\u015etef\u0103nic\u0103","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Faculty of Mathematics and Computer Science, \u201cBabe\u015f-Bolyai\u201d University, 400084 Cluj-Napoca, Romania"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2022,1,13]]},"reference":[{"key":"ref_1","unstructured":"Garey, M.R., and Johnson, D.S. (1990). Computers and Intractability; A Guide to the Theory of NP-Completeness, W. H. Freeman Co."},{"key":"ref_2","unstructured":"Fleming, V. (Daily Record (Little Rock), 2008). Mystery of the D-day crosswords, Part 1, Daily Record (Little Rock), Retrieved: 7 June 2010."},{"key":"ref_3","unstructured":"Stallings, W. (2017). Cryptography and Network Security: Principles and Practice, Pearson Education. [7th ed.]."},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"Brass, P. (2008). Advanced Data Structures, Cambridge University Press.","DOI":"10.1017\/CBO9780511800191"},{"key":"ref_5","unstructured":"Cioban, V., Niculescu, V., and Prejmerean, V. (Crosswords Generator, 2019). Crosswords Generator, Zilele Acdemice Clujene."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0004-3702(76)90019-9","article-title":"Computer Construction of Crossword Puzzles Using Precedence Relationships","volume":"7","author":"Mazlack","year":"1976","journal-title":"Artif. Intell."},{"key":"ref_7","unstructured":"Ginsberg, M.L., Frank, M., Halpin, M.P., and Torrance, M.C. (August, January 29). Search Lessons Learned from Crossword Puzzles. Proceedings of the Eighth National Conference on Artificial Intelligence, Boston, MA, USA."},{"key":"ref_8","unstructured":"Meehan, G., and Gray, P. (1997, January 12). Constructing Crossword Grids: Use of Heuristics vs. Constraints. Proceedings of the Expert Systems 97: Research and Development in Expert Systems XIV, SGES, Cambridge, UK."},{"key":"ref_9","unstructured":"and Botea, A. (2008, January 4\u201318). Crossword Puzzles as a Constraint Problem. Proceedings of the Principles and Practice of Constraint Programming, Sydney, Australia."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1515\/jagi-2015-0006","article-title":"A Play on Words: Using Cognitive Computing as a Basis for AI Solvers in Word Puzzles","volume":"6","author":"Manzini","year":"2015","journal-title":"J. Artif. Gen. Intell."},{"key":"ref_11","unstructured":"Fenner, S.A. (2014). The complexity of some regex crossword problems. arXiv."},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"De La Briandais, R. (1959, January 3\u20135). File Searching Using Variable Length Keys. Proceedings of the Western Joint Computer Conference, Association for Computing Machinery, IRE-AIEE-ACM \u201959 (Western), New York, NY, USA.","DOI":"10.1145\/1457838.1457895"},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"490","DOI":"10.1145\/367390.367400","article-title":"Trie Memory","volume":"3","author":"Fredkin","year":"1960","journal-title":"Commun. ACM"},{"key":"ref_14","unstructured":"Black, P.E. (2021, June 30). Dictionary of Algorithms and Data Structures. Available online: https:\/\/xlinux.nist.gov\/dads\/."},{"key":"ref_15","unstructured":"Knuth, D.E. (1973). The Art of Computer Programming, Addison-Wesley."},{"key":"ref_16","unstructured":"Connor, J., Duchi, J., and Bruce, I. (2005). Crossword Puzzles and Constraint Satisfaction, Stanford University. Technical Report."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/15\/1\/22\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,13]],"date-time":"2025-10-13T14:14:57Z","timestamp":1760364897000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/15\/1\/22"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,1,13]]},"references-count":16,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2022,1]]}},"alternative-id":["a15010022"],"URL":"https:\/\/doi.org\/10.3390\/a15010022","relation":{},"ISSN":["1999-4893"],"issn-type":[{"value":"1999-4893","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,1,13]]}}}