The most difficult crossword, compiled computer

Crossword puzzles - not an easy task for the computer, because the problems are formulated vaguely. On the other hand, simplifies the thesaurus. Example Deep Blue shows that AI programs can participate in quizzes and beat people. Why not do the same with crossword puzzles?

American designer Matthew Ginsberg (Matthew Ginsberg) created a program called Dr Fill, which copes with the crossword is much better than the vast majority of people, пишет New Scientist.

The program puts forward several answers, indicating the probability for each of them. If the software works in conjunction with a person, then the solution of a crossword puzzle becomes trivial matter. Much more difficult to ensure battery life.

Matthew Ginsberg mathematician deals with this problem for 40 years. In 1976, he wrote, probably the world's first program for compiling crosswords. Then he gave up this business for 10 years or more, until his friend said that he had compiled a couple of crossword accepted in the newspaper The New York Times.

Many years passed until Ginsberg has not finished making your program champion Dr Fill, which debuted on Championship US crosswords . She immediately proved to be good, and since then only improves performance.

Secret Weapon Dr Fill - base of 6 million questions and answers for the crossword. For each question, she looks for matches in the database, and then tries to combine the words on the grid. If not, the program tries another combination. More details about the algorithms cm. Research .

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

If solving a crossword puzzle can be compared to brute force passwords, the drafting of a new generation of crossword and descriptions for each word - the task is more complicated. Like the rest of the program, Dr Fill in this until it's too good. However, at the request of New Scientist author agreed to generate a crossword grid in the style of The New York Times. This crossword puzzle in front of you. Try your hand in the battle against "artificial intelligence».

Crossword compiled program




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

Source: geektimes.ru/post/243643/