The most difficult crossword made by computer

Solving crosswords is not such an easy task for a computer, because tasks are formulated indistinctly. On the other hand, the thesaurus simplifies the task. The Deep Blue example shows that AI programs can participate in quizzes and beat people. Why not do the same with crosswords?

American developer Matthew Ginsberg (Matthew Ginsberg) has created a program called Dr Fill, which copes with crossword puzzles much better than the absolute majority of people, writes New Scientist.

The program puts forward several answers, indicating the probability for each of them. If the software works in tandem with a person, then the solution to the crossword puzzle becomes a trite thing. It is much more difficult to ensure the autonomous operation of software.
')
Mathew Ginsberg has been working on this problem for about 40 years. In 1976, he probably wrote the world's first crossword puzzle program. Then he abandoned the case for 10 years or more, until his friend said that a couple of crosswords compiled by him were accepted into the newspaper The New York Times.

Many years passed before Ginsberg finished creating his champion program Dr Fill, which debuted at the United States Crossword Championship . She immediately showed herself well, and since then has only improved performance.

The secret weapon of Dr Fill is a base of 6 million questions and answers for crosswords. For each question, she searches for a match in the database, and then tries to combine words on the grid. If it fails, the program tries another combination. For more information about algorithms, see scientific work .

The author compares Dr Fill with the work of the recommendations engine on sites like Netflix: this is one of the big data analysis applications.

If solving a crossword puzzle can be compared with brute force passwords, then creating a new crossword puzzle and generating descriptions for each word is a more difficult task. Like the rest of the programs, Dr Fill is not too good at this. However, at the request of New Scientist, the author agreed to generate one crossword puzzle on the grid in the style of The New York Times. This crossword is in front of you. Try your hand in the battle against the "artificial intelligence".

Crossword compiled by the program


When generating a crossword puzzle, I had to help the program a bit to get rid of too similar words. Nevertheless, according to Ginsberg, today it is the most difficult crossword puzzle, generated almost entirely by a computer program (the answers will be published on January 17 in the journal New Scientist).