‘Dr. Fill’ vies for crossword solving supremacy, but still comes up short

A computer program called ‘Dr. Fill’ can solve even the most difficult crossword puzzles in just a few seconds. But humans still have the advantage: computers just can’t compete with human invention, imagination and sense of humor.

Dr. Fill was created by computer scientist and crossword constructor Matthew Ginsberg. Ginsberg, who says he is “arguably the world's worst puzzle solver,” became so frustrated at his lack of ability that he decided to write a computer program that would help him.

Dr. Fill has a database of every crossword clue used since the 1980s. Ginsberg has also entered the contents of several dictionaries and other reference works — and the entirety of Wikipedia.

“Dr. Fill solves puzzles by finding similarities between the clues in the puzzle and the clues it knows about,” Ginsberg explains. “Then it just tries to cram in the words in a way that satisfies the fundamental crossword requirement that if two words cross they cross at the same letter. It doesn't know what it's doing; it just sort of stumbles around. But it gets pretty good results.”

It’s also improving quickly. For the past three years, Dr. Fill has competed “informally” at the American Crossword Puzzle Tournament, organized by Will Shortz, the crossword editor at the New York Times. The first year, Dr. Fill came in 141st out of about 600 competitors. It did a little better the second-year; last year it was 65th. “I get a little smarter so it gets a little smarter each year — and I’m inching my way up there,” Ginsberg says.

So why is it that computers, which have had such success beating humans at games like chess, have trouble matching up with us at crossword puzzles? “I think it's the fundamental imagination that the constructors bring to the puzzle,” Ginsberg says.

As an example, he cites one of his favorite New York Times puzzles. “One of the clues was ‘Apollo 11 or 12 — 180 degrees,’ and the answer was gibberish,” Ginsberg says. “But if you turned it over, the answer was ‘moon missions‘ — because all of those letters are still letters when you rotate them 180 degrees. Doctor Fill can't figure that out. It doesn't know about rotating things, it doesn't know about the physical shape of letters. … That’s what makes it hard, when there is something tremendously novel.”

Shortz says sometimes he will write a clue for a New York Times puzzle and think, "This clue will kill Dr. Fill." This happens, he says, when “it's something that maybe everyone knows, but [the clue] is worded in a vague way that a computer would have a hard time figuring out if it's not in its database already."

Shortz says there is invariably one puzzle with a tricky theme at the Crossword Puzzle Tournament which Dr. Fill simply has no way to figure out. “A couple of years ago,” he says, “we had a puzzle [that used] boustrophedon, an ancient form of writing in which words start from left to right, and in the next row go from right to left and then left to right and right to left and so on. As you might guess, that killed Doctor Fill.”

Dr. Fill can detect the theme in some puzzles, Ginsberg says. It understands certain kinds of themes that often get repeated, like replacing one letter with another in an answer. But “flexible thinking,” the kind of thinking that makes humans good puzzle solvers, isn’t its strong suit. What it lacks in conceptual ability it makes up for in sheer speed, however. Once Dr. Fill catches on to a theme, it just “throws the whole puzzle out and starts from scratch, knowing the theme, and fills it in again” — many times faster than a human ever could.

Though computers have yet to match the creativity of human puzzle solvers, they have become indispensable to puzzle constructors. When Shortz started at the Times in 1993, most of the puzzles were made the old-fashioned way, by hand on graph paper. Over the years, the balance has shifted overwhelmingly, he says. Now most crosswords are made with computer assistance, and just a few people do them by hand.

Shortz doesn’t worry, however, that someday a computer will take his job at the Times; there are just too many ways that the human mind is fundamental to good crosswords. “Only a human can come up with an original crossword theme,” he says. “Only a human knows what an interesting crossword answer is, and only a human can write an original clue. The computer can suggest clues that have been used in past crosswords, but it can't suggest an original one.”

This story is based on an interview that aired on PRI's Science Friday with Ira Flatow