A program that generates crossword puzzles
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.
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:
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.
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.