La generación de cuadrículas de crucigramas en general se considera un problema NP-completo y teóricamente podría ser un buen candidato para ser utilizado por algoritmos de criptografía. En este artículo, proponemos un nuevo algoritmo para generar cuadrículas de crucigramas perfectos (sin casillas negras) que se basa en el uso de estructuras de datos de tries, las cuales son muy importantes para reducir el tiempo de encontrar las soluciones, y también ofrecen una buena oportunidad para la paralelización. El algoritmo utiliza una representación especial de tries y es muy eficiente, pero a través de la paralelización, el rendimiento se mejora a un nivel que permite obtener la solución extremadamente rápido. Los experimentos se realizaron utilizando un diccionario de casi 700,000 palabras, y las soluciones se obtuvieron utilizando la versión paralelizada con un tiempo de ejecución del orden de minutos. Demostramos aquí que encontrar una cuadrícula de crucigramas perfecta podría resolverse más rápido de lo que se había estimado anteriormente, si utilizamos tries como estructuras de datos de soporte junto con la paralelización. Aún así, si el tamaño del diccionario se incrementa considerablemente (por ejemplo, considerando un conjunto de diccionarios para diferentes idiomas, no solo uno), o a través de una generalización a un espacio 3D o espacios multidimensionales, entonces el problema aún podría ser investigado para un posible uso en criptografía.