Crossword Generator
A program that generates crossword puzzles very fast
Try today's puzzle!
Overview
This program generates crossword puzzles using a three step process: first, generate the grid; second, fill the grid with words; and third, clue the filled grid. To make a different puzzle available on my website each day, I began using the web framework Flask.
Generating the Puzzles
Step one is generating the grid. At the moment my code takes an empty grid, adds 1-2 rows and columns extending inwards from the sides, and fills the middle randomly. Since crosswords are usually rotationally symmetric, it only generates half of it and fills in the rest using the first half.
Step two, filling the grid with words, is the most complicated step. My algorithm is a tree search where each branch represents filling a slot in the grid with a word. A brute-force search will generate a valid filling of the grid; however, it's very slow without optimizations. I implement two main types of optimizations: search heuristics and faster code.
Search heuristics:
- Keep track of all words that can fit in each slot, and stop searching a branch of the tree if a slot has no valid words.
- Choose the next word to fill based on which slot has the lowest number of possible words that can fill it.
- Pick a word for a certain slot based on what leads to the highest number of possibilities for crossing slots.
Code efficiency:
- Use multithreading when choosing the next word to put in a slot. This is implemented via a thread pool to avoid the overhead of spawning threads mid-search.
- Store the words as SIMD vectors to increase the speed of matching comparisons between words and slots.
- Aggressive moving of data to avoid copying at all costs.
With these optimizations, the filling process now usually takes around 0.1 seconds. This is about a 1000x improvement over previous iterations of the code.
Step three is clueing the filled grid. For each word in the filled grid, my code looks at past crosswords and randomly chooses a clue corresponding to that word. These clues aren't original, but generating them from scratch would be costly.
Playing on my Website
To make a different crossword available on my website each day, I had to use a web framework to make my site dynamic. I chose to use Flask as it seemed good for small projects like this site. To display puzzles in the browser, I use a Javascript player from Crossword Nexus.