https://abstractnonsense.com/crosswords.html

Crosswords -- Bill Moorier

I've been interested in computer-generated crosswords for a long
time, and have written several computer programs of my own over the
years to generate crosswords. Recently, with the addition of modern
AI techniques, I've started to feel like the output is getting quite
good -- perhaps even beginning to rival something that a human would
create. I don't know of any other attempt at fully-automated
crossword generation whose output is this good (if you know of one, I
would love to hear about it!).

You can find my most-recent attempts here.

If you simply ask a modern AI (like ChatGPT, for example) to generate
a crossword for you, at the time of writing (2024-12-21) the results
are not good. I've tried with all the models I can get my hands on,
and have never managed to get anything usable out of them.

But a combination of old-school computer science and modern AI can be
very successful!

I start with a huge wordlist, which I compiled from a number of
sources on the internet. This is just a giant list of English words
and phrases. Recently I've been asking AI models to tell me which
entries in the list are the most obscure, so that I can consider
deleting them (but this is still a work-in-progress).

Next comes my grid-generator. If you want to generate a nice
crossword you have to start with a good-looking grid. American
audiences tend to expect 180-degree rotational symmetry, for example.
My grid-generator starts with a blank array of white squares, 7x7,
11x11, 13x13, or 15x15. Then it randomly colors squares black, in
pairs, to maintain 180-degree symmetry. The process isn't completely
random though. There's a small bias toward the horizontal and
vertical axes in the middle of the grid, and another small bias
toward even-numbered coordinates (if you start numbering at 1). I've
found these two biases to both make the next step more likely to
succeed.

Exaggerating the first bias will get you a grid like this, where most
of the black squares are very close to either the horizontal or the
vertical axes:

[axis-bias]

On the other hand, exaggerating the second bias will get you a grid
like this, with clues "criss-crossing" each other. I think of this as
more of a "British-style" grid:

[even-bias]

With both of these biases present (but turned-down a bit from the
above grids), we keep coloring squares black until some target
"density" is reached (again I've set that number empirically to make
the next step more likely to succeed).

Once we have a grid, we try to fill it with words! I use simple
backtracking search for that, with a timeout to stop the search on
grids that are likely impossible to fill. In practice it's easy to
generate a new filled grid from scratch about once every two minutes.

After the grid is full of words, we use an LLM to generate some
clues. I've iterated over many models and prompts for this. I think
the current performance is quite good, but far from perfect. One
noticeable defect is that the models I've tried tend to not pay close
enough attention to the instruction never to use the solution word
anywhere in the clue. In particular they struggle when the solution
is an acronym (e.g. sometimes a clue for "LOL" will be something like
"Laughing out loud online"!). I've written some code to do some
post-processing to avoid and correct things like this, but that's a
work-in-progress and there's still plenty of low-hanging fruit for me
to tackle.

That's it for now (please do try a crossword or two and let me know
what you think!). I have plenty of other ideas I want to work on in
this space. Excitingly some of them involve "themed" crosswords,
which are quite a big step-up in difficulty for crossword generation.