Crossword Generator
A program that generates crossword puzzles
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 crossword grids must be 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. To improve the speed, a few of the optimizations were:
- Keep track of all words that can fit in each slot, and stop searching a branch of the tree if any of the numbers of possible words drop to zero. This is a lot of extra work for the algorithm, but it saves much more time than it spends.
- Choose the next word to fill based on which slot has the lowest number of possible words that can fill it. This will likely make it faster to find areas where no words fit a certain slot.
- Pick a word for a certain slot based on what leads to the highest number of possibilities for crossing slots. This means that it's likelier for the algorithm to take profitable branches of the tree.
With these optimizations, the filling process now usually takes around 1 second, with code written in C++. This is about a 100x improvement over previous iterations of the code, which were written in Python.
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 generated puzzles aren't completely original, but computationally generating high-quality clues would be extremely hard and 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.