If you’re a regular on this blog, you may remember that I floated the idea of making a crossword-filling algorithm just to see how hard it would be. I wasn’t sure I’d ever get around to making it but today I was sick and bedridden and bored (yay?) so I spent a few hours coding something up. If you’d like to see more or less what I’ve done and how it performs on a sample themeless puzzle, follow me to the rest of this post.

Here’s the basics of it: MySQL has a terrific full-text match based on the tf*idf algorithm which I’m using to find good fits for clue/entry pairs. For instance, if I have a four-letter word for “Fried Cajun side” you can run the MySQL query

SELECT Entry,
MATCH (
Clue
)
AGAINST (
'Fried Cajun Side'
) AS Score
FROM `Clues`
WHERE MATCH (
Clue
)
AGAINST (
'Fried Cajun Side'
)
AND Entry LIKE '____'
LIMIT 0 , 10

and get the following results:

Entry 	Score
SLAW 	15.20439338684082
OKRA 	14.877264976501465
OKRA 	9.801589965820312
OKRA 	9.801589965820312
OKRA 	9.801589965820312
OKRA 	9.801589965820312
OKRA 	9.801589965820312
OKRA 	9.801589965820312
ROUX 	9.69262981414795
OKRA 	9.69262981414795

(OKRA appears several times because it has matched with several different clues.) Of course, if you knew even one of the letters, this process would immediately give you the correct answer (OKRA).

At each step of the algorithm, I’m taking these results and adding the “Score” to the difference between the top entry and the second-ranked entry. The entry with the highest sum gets added to the grid and the process is restarted. For now I’m not doing any backtracking; I just want to see how this algorithm will do simply marching ahead and filling in entries.

Ready? Let’s step through with it on Brendan’s grid and see how it does.

Step 1: 49 ACROSS: Electrical resistance symbol — OMEGA
We’re off to a good start. This clue was an exact match for one I had in my database, and was a much better match than the second-best possibility (which turned out to be SAILS, for whatever reason).

Step 2: 10 DOWN: 1961 Charlton Heston epic — ELCID
Step 3: 39 DOWN: Renault vehicle marketed to the U.S. — LECAR
Step 4: 33 DOWN: North Carolina town or college — ELON
These are all stone-cold gimmes for anyone who does a lot of crosswords, so it’s nice to see the algorithm doing well on them too. Nice to see it reject DUKE for 33-Down; the database’s clue of “North Carolina college town” was a great match.

Step 5: 57 ACROSS: ___ Center (home of the Nets and Devils) — IZOD
Step 6: 1 ACROSS: Model airplane material — BALSA
I was shocked that the algorithm got the IZOD Center so quickly, I guess because I didn’t know this little bit of trivia. And now that I’ve learned it, it’s already out of date, since those teams have moved to the Prudential Center. Oh well.

Step 7: 6 DOWN: Immune system stuff — SHREDBLOODCELLS
Well, we had to mess up eventually. A human would never ever have entered this into the grid, but the bot sees the clue in its database that reads [Attack the immune system?] and thinks it’s got a good match. Maybe I need some logic for when the clue in the database has a question mark? This seems especially important for long entries. (And incidentally, I don’t have WHITEBLOODCELLS in my database, which is shocking, considering it’s a totally legit 15-letter answer. I’ll have to data-mine Brendan’s puzzle after I’m done here to add it.)

Step 8: 59 ACROSS: Pummels — ROUTS
Ah, shoot, we’ve messed up again even though this one doesn’t look quite so bad. The intended answer was PELTS. There’s only one five-letter entry in my database with the word “pummels” in it, so it gets the green light here.

Step 9: 35 DOWN: Clothing joint? — SEAM
Step 10: 8 DOWN: Miso soup enhancer — MSG
Step 11: 60 ACROSS: Choosing word — EENY
Yeah, it’s doing fine on these, but let me show the grid at this point:

B A L S A . . S _ M . _ E _ _
_ _ _ _ _ . _ H _ S . _ L _ _
_ _ _ _ _ . _ R _ G _ _ C _ _
_ _ _ _ _ _ _ E _ . _ _ I _ _
. . . _ _ _ _ D _ _ _ _ D _ _
_ _ _ _ _ _ _ B . _ _ _ . . .
_ _ _ _ . . _ L _ _ _ _ _ _ E
_ _ _ . . S _ O _ _ . . _ _ L
_ _ _ _ L E _ O _ . . _ _ _ O
. . . _ E A . D _ _ _ _ _ _ N
_ _ _ _ C M _ C _ _ _ _ . . .
O M E G A . _ E _ _ _ _ _ _ _
_ _ _ _ R _ _ L _ . _ _ _ _ _
I Z O D . _ _ L _ . R O U T S
E E N Y . _ _ S . . _ _ _ _ _

Anything jump out at you? Something sure jumps out at me: we’re hardly crossing any words at all. We absolutely HAVE to use the information we’ve got in terms of the crossing words or we’ll never get anywhere. The algorithm isn’t doing that, and definitely needs a push in that direction.

Okay, look at the above grid one more time. What answer can you put in next, even without looking at the clues? I see an obvious one: _M_ZE has to be AMAZE, right? Let’s see what the bot fills in next.

Step 12: 27 ACROSS: Chicago-based insurance company that sponsors Manchester United’s uniforms — RIO
Okay … that’s wrong, first of all, and why didn’t you fill in AMAZE?

So … this needs work. Any thoughts on how to make this better?