Building a Crossword Puzzle Generator with JavaScript

Building a Crossword Puzzle Generator with JavaScript(mitchum.blog)

42 points by maynman 6 years ago | 8 comments

garaetjjte 6 years ago |

From quick glance it picks random matching word and goes with that, never reverting that decision. This allows only for generating rather low-density crosswords, where much of the board is empty.

Keeping a "stack" of crosswords, each one with one word added, iterating through possible words, and when nothing matches dropping "stack frame" and retrying with another word on previous level, would allow to generate much denser crosswords.

tobr 6 years ago | |

I wrote a crossword generator one or two years ago - it used this approach but for individual letters, not whole words. You’d feed it a pattern of blank squares. If I recall correctly, it used a dictionary to find all the words that would fit in each current row or column, and counted how many different possible letters each square could take. If it found a row or column with no matches, it would backtrack - otherwise it would take one of the squares with the fewest possible letters, fill one of them in, and recurse. If that would fail it would try the next possible letter in the list, until it ran out of letters, in which case it would also backtrack.

It made it possible to produce incredible dense crosswords, but it wasn’t very efficient, as it would retry certain impossible local solutions again and again and again. I wonder if it would be more or less efficient to do one whole word at a time, as you suggest.

maynman 6 years ago | | |

That sounds pretty cool. I also found it difficult to optimize for both performance and word density with the approach I took. Maxing out on one seemed to negatively affect the other. I'm sure there have to be some better algorithms out there to do this sort of thing.

impostervt 6 years ago |

Working on an activity book for kids and was contemplating writing something like this, and then realized it was definitely non-trivial. Thanks for the work!

maynman 6 years ago | |

I had fun making it. I'm glad you've found it valuable :)

apocalyptic0n3 6 years ago |

This looks like a fun project. I might try building one myself this weekend (or doing a word search, maybe). Thanks for the idea

tothrowaway 6 years ago | |

I have a great story about generating word searches. I once got an angry email from a superintendent at a school district in Washington state using my algorithm. He said 'the generator inserted the phrase "killanigger" in the middle of the word search. This is obviously intentional on the part of the programmer since the odds of a phrase of this length being generated randomly is exceedingly small.'

I was very confused because I had implemented a bad word filter which I knew worked (it was the most interesting part of building a word search). And obviously, I didn't hard code that string in my program!

I asked to see the offending puzzle. Upon inspection, I found that the word search contained the word "ORIGINAL". When reversed for the word search it is "LANIGIRO" (which contains the substring "NIGIRO"). The start of another word - "LAW" - was placed next to "LANIGIRO" (by random chance) creating the string "LLANIGIRO". The two preceding randomly chosen letters were "K" and "I", forming the string "KILLANIGIRO".

I explained it to the superintendent, and all was well again.

apocalyptic0n3 6 years ago | | |

That's actually pretty amusing and just bad luck. I wonder if your bad word filter would have caught it if you used some sort of fuzzy word lookup. Probably would have increased the time to remove those quite a bit, though.

And now that you mention it, the bad word filter does sound like fun to build. I've got a bunch of ideas for how to do it best floating around in my head.