Script for generating crosswords for a crossword directory. The goal was to use 300 000 words (answers) and questions to these words to generate square 16×16 cells, fully filled out with crosswords. Each cell had to store either a question or a letter of a word.
The challenging part was that direct generation of crosswords causes a lot of dead ends. For instance, algorithm should set up questions and answers so that not to leave empty corner cells and last in a row cells. It happens that one empty cell remains and the script should pick up a letter, which would match words both horizontally and vertically. The more crossword is filled with questions and answers, the more difficult generating is. Some combinations are impossible to fill out completely.
To resolve these issues we have developed an algorithm. The script for generating crosswords picks up a random word and a question to this word and places them on the grid. The result is written into the database. Each next words is pulled from the database and pseudo randomly placed on the grid in five different combinations. Thus, from 1 grid with 1 word we got 5 grids with 2 words etc. This was done so that we always had alternative variants in case of dead end, when it was not possible to add a new word. To speed up generation we run this algorithm in 50 threads, each of which was working on its own grid variant. To reduce the number of queries into the database and speed up performance, each thread stored the whole database of 300 000 words in its RAM. To make final crosswords as different from each other as possible, when the thread generated 5 full grids we added them into the main database and the thread started its work with an empty grid. In the end, we have generated 3 000 full crossword grids with the script for generating crosswords.