There was a lot of discussion at the 1999 tournament of computer solutions to the contest puzzles. Two weeks before the event I had sent advance copies of them to Michael Littman at Duke University. Michael heads a team of computer scientists that has developed a program called Proverb--the world's first computer program designed to solve standard crosswords. He immediately put Proverb through its paces. The results were so interesting (in fact, so amazing) that I printed them out on large sheets of paper and posted them, along with Michael's analysis, after each round at the event. These results are now combined and reprinted with a general introduction below. Note: If you still intend to solve the 1999 puzzles yourself, do not read further until you're done, as many answers are revealed. --Will Shortz

About "Proverb" — And its 1999 Tournament Results

Proverb (The Probabilistic Cruciverbalist) is a computerized crossword puzzle solver developed at Duke University. It builds on recent advances in computer science on efficient probabilistic reasoning, information retrieval, data mining, and constraint satisfaction to use a variety of online databases to solve puzzles. An extensive series of tests indicates that Proverb fills in approximately 90% of the words correctly on an average New York Times crossword puzzle (about 95% correct for Monday-Wednesday and 85% for Thursday- Sunday).

The design of the system consists of two phases: candidate generation and grid filling. Candidate generation is performed by a set of 30 different "modules" that use different algorithms and data sources to suggest candidate solutions to the clues. Given the generated candidates and their certainty scores, the grid-filling algorithm finds a way of fitting the candidates into the grid, maximizing a total certainty score. The highest scoring solution is returned as Proverb's answer.

The Duke team was sent advance copies of the tournament puzzles on which to test the program. Proverb runs on a collection of 15 computers and takes about 7 to 10 minutes to solve a puzzle, but this varies significantly depending on how many other users are sharing the computers. To give Proverb the benefit of ever-increasing computer speed, all scores were calculated assuming the puzzles could be completed in under a minute.

In the grids below, capital letters indicate Proverb's correct answers; small letters indicate errors.

PUZZLE 1

M A U V E . S T R A P . s W F
A C R I D . N E A T O . H O R
W H A T I S I T N O W . O N E
. E L A T E D . I N D U L G E
. . . M O V E R . . E S O . .
R E H I R E . E N G R A V E D
I C O N S . S C A R Y . E L O
P O W . . W H Y M E . . S I N
E L D . P I E C E . B A s E D
N E O N A T A L . D E N A L I
. . Y E T . . E G R E T . . .
E P O C H A L . E N T I T Y .
L O U . W H E R E O R W H E N
A N D . A S H E N . E A R L E
L E O . Y O R B A . E R U P T

words correct: 73
words incorrect: 3
characters incorrect: 2

SCORE: 1030

As with most easy puzzles, Proverb gets more than 30% of its answers here from its database of 350,000 crossword clues from past puzzles. The "exact match" module is able to fill in enough of the puzzle with certainty that more tenuous statistical connections can be used to fill in the remainder of the words with high accuracy. Example clues solved by the "exact match" module are "The loneliest number" (ONE) and "River to the Caspian" (URAL).

PUZZLE 2

. . C L U M P . . . D O R M A N T
. B O O Z E R . . M A N A C L E S
E R U D I T E . T E L E P H O N E
M I R E S . W H E R E . . A T E .
O T T S . E R O D E . M E L . . .
T O T . S C A M S . G A M E T E S
E N V E L O P E . B I N S . R A H
. . . S U N . R O U G H . L I R E
. R E P R O N U N C I A T I O N .
K H A N . M O N T H . T O M . . .
E U R . A I M S . A N T I B I A S
A M P E R E S . O N E A L . R B I
. . . v t S . A D A M N . C O A X
. J A I . . S C E N E . D A N C E
F O L L I C L E S . S c A n E U S
L I M E A D E S . . I D L E R S .
U N A R M E D . . . S e Y s S . .

words correct: 87
words incorrect: 7
characters incorrect: 6

SCORE: 1320

The "exact match" module could solve only 16% of the clues on this puzzle. However, some of the slack was picked up by the "transformation" module. This module uses a database of crossword clues to create a set of rules for transforming a clue it has never seen before into one in the database. One rule it knows is that the phrase "for one" can be deleted from a clue without changing the intended meaning. This allows the "transformation" module to convert "May, for one" to "May" (for MONTH), which is a clue in its database.

PUZZLE 3

S P C A . . T R A S H . . E S P A N A
I R O N . S H E R P A S . R E U S E S
Z O O T . P E P P E R M I N T T I C K
E N T O . R A E . W E A N . S T A K E
S A I N T . S A D . . L A N A . N S W
U T E . M A P L E A W L N U T . . . .
P E S T E R . . A R I S E N . E W O K
. . t O N O . A T E N . . C H E R R Y
A R C O . M O C H A G Y P . O N E A L
D O R . E A R L . . . O L A Y . N N E
O L E I C . B U B B A G U M . A C T S
P L A Q U E . . R U D I . A M A H . .
T O M S . D E S I R E . . N E R V E S
. . . . b U T T E R P E C A N . A N Y
M B A . A C H Y . . T A R . D E N T S
A R G O T . E L I O . R U E . D I R T
H E A T H B R u C s U N C H . G L E E
R A T I O S . s E t T E E S . E L A M
E D E S S A . . S E A R S . . R A T S

words correct: 112
words incorrect: 8
characters incorrect: 6

SCORE: 1695

The solution here depends heavily upon the "segmenter" module. This subsystem suggests candidates for long slots consisting of likely sequences of words that fit well with crossing letters. This allows Proverb to get clues like "Sucker flavor?" (PEPPERMINTTICK), whose answer would not appear in any word list, simply because it is made up of reasonable words and fits well with the crossing words. Running Proverb without the segmenter on this puzzle resulted in a score of only 930 (93 words correct).

PUZZLE 4

c A r f . r A d i r . s e a m
a r e i . A t O n E . e l l e
p o n n . d o e s t . a s e s
s w e i t i e S . a s k e r s
. . . s o o t . l i k E . . .
i n t h E . a l i n i . a w i
t o l e d o . o n E S . f o r
A L A S . l A v e r . a t m e
a t a . T a l e . s a m e e n
d e s p e r a t e . v e r n E
. . . i r i s . u s e r . . .
A L A S K A . a g a l i n i s
o u S e . l A p e l . c o n e
o n E s . i n a n e . a a r e
s E A t . n o t e S . s h e d

words correct: 3
words incorrect: 75
characters incorrect: 160

SCORE: 30

This spooneristic puzzle is brilliantly designed to undermine Proverb's retrieval abilities. Since Proverb "understands" only very few clues, it doesn't notice the consistent way in which the clues are corrupted. Remarkably, Proverb does manage to fill most of the grid with answers it finds plausible, including three correct words. Two of these appear to depend primarily on the structural similarity of their clues to clues from past puzzles (e.g., both "'Woe is me!''' and "'Moe is wee!''' [ALAS] have "is" sandwiched between two other words). Proverb's third correct answer, ALASKA ("Home is near"), apparently is gotten by accident from the "path" module. Proverb knows that the Near Islands include Attu, and Attu is part of Alaska. Proverb finds an unexpected answer for "Barry or Hess" (the correct answer is TRUMAN, but it fills in EUGENE). "Eugene Barry" and "Eugene Hess" are both in its actors database. Note that when the clues are unspoonerized by hand, Proverb achieves a perfect score on this puzzle (1530). This result reinforces the fact that the puzzle is actually quite easy, even though Proverb is unable to solve it.

PUZZLE 5

G R I T T a . a r T a . S H A G S
R E L O A d . s e e r . H A S O N
A S I M O V . s t e m . A L I B I
M A K E S . P i e n y P R O F I T
S T E S . . O s l . . L E E . . .
. . . . L I T T L E M U R D E R S
. F R A U D . . . a D S . . L E O
. Y E N T L . s I t S . . D U A L
M O N K E Y I N T H E d o o D L E
I D E A . . N o S e . I N T E L .
F O G . . T R U . . . S A S S Y .
F R E N C H I t a l i a n . . . .
. . . O L E . . b a r n . t a t t
F R O Z E N O R A N k a r a c h i
L A N Z A . P E t e . m o n T e m
A T I L T . A D E N . e l t o r e
G E N E S . L O D E . s e i r e S

words correct: 53
words incorrect: 37
characters incorrect: 68

SCORE: 530

This puzzle is difficult for Proverb, in part because of the relatively low percentage of "exact match" clues. Two problem areas, the top middle and the bottom right, have no exact matches at all. Compounding the difficulty, the "transformation" module misanalyzed "Military front?" (PARA)--it had learned a rule that "military" can be replaced by "ships"--giving the solution of "STEM" with high confidence. In the lower right, the "path" module found a tenuous connection between "ROLE" and "Anima theorist" (JUNG), helping to destabilize that part of the grid.

PUZZLE 6

O N C E . O S L O . B L A B . I C E D
V A L E . S I A M . E I R E . C O I R
E T O N . E R M I N E M E L V I L L E
R A C Y . . R A T E . B A L I . L E A
A S H . S T A R . R Y E . E E R I E R
C H E E T A H R I V E R A . T E E N Y
T A S S E L . . B E N . R A N T S . .
. . . S W E A T S . . S A G A . I W O
P A C A S . T H E N . I M A M . M A P
A C H Y . R H I N O N E A L . D O N T
I R A . S A L E . H O P I . B E N D S
D E M . C H E F . . T I C T A C . . .
. . O D I S T . T S E . . B R A N D O
S P I C E . E L A N D S T A N F O R D
C A S I N O . I N A . E R R S . M A D
A R S . C R A M . F O R E . . S I G N
L I O N E S S P A U L I N r . A N N E
E A S E . O T I C . L A D E . L E E S
S H o W . N O D E . A L S O . T E T S

words correct: 118
words incorrect: 4
characters incorrect: 2
SCORE: 1855

Once again, the "segmenter" played a crucial role in this solution. Because of the crossing theme entries, some letters (for example, the L in the intersection between "Songstress of the dog family" [COLLIESIMON] and "Author of the weasel family" [ERMINEMELVILLE]) could not be disambiguated by consulting a word list. The "segmenter" was able to recognize that these answers consisted of multiple words, found their boundaries, and chose candidates that fit.

PUZZLE 7

W A N T A D . P A N G R A M . F R E S C O
A R O U S E . A M E R I C A . L U T H O R
R U N N I N G S C A R V E D . A B S O R B
M B A S . E A T S . . U S A R M Y . V I I
T A M . C U R E . D H L . M O B . T E N T
h N E W A V Y S T R E E T . C E L E S T A
. . . O P E . . A U N T I E . . A M A H L
G I J O E . P O X . . . E T O N I A N . .
E M U . A R C H I r a B U N K E R . D R J
R A S H N E S S . a L L P A S S . I S E E
A C T I N G . . A T L A S . . T R O O P S
L O V E . R E g R e e N . S I L E N C E S
D P I . f a R e C r y C U R V E S . K A Y
. . b A r b A R I . . . S O Y . C A S T E
T H E R o . . E N T R E E . . O U T . . .
H O F F M A N . G R A N D V O L E O P R Y
U S O S . S O S . A D D . A N D S . R O E
N P R . S H R I L L . . A R E S . C O D A
D I A B L O . L E A D I N G L A l I V E S
E C L A I R . A T L A N T A . L A T E N T
R E L A T E . S T A N C E S . T W E N T Y

words correct: 126
words incorrect: 16
characters incorrect: 17

SCORE: 1935

A number of modules contributed to Proverb's performance on this puzzle. The "movie" module supplied "'Rain Man' Oscar winner" (HOFFMAN). A "fuzzy match" on the crossword database got "Outdoor climber" from "Wall climber" (IVY). The "path" module solved "Urgent message" (SOS). A "thesaurus" module contributed "Parrot" (REPEAT). And an "encyclopedia" module got "Weather report?" (THUNDER).

PUZZLE 8

S A M E N E S S . S H O R T S
P L O W I N T O . H O M E E C
I S T A N B U L . O U S T E R
C O H N . E D I T O R . A H A
E R E . . R I C O . G R I E G
D A R K . G O I T A L i N E .
U N L I T . . T E X A S . . .
P S Y C H I C . D E S E R V E
. . . K E B A B . . S T E I N
. S T E A M R O L L . O C T A
S T A R T . O N E A . . R A M
A R R . R O M A N O . H E M O
B A Z A A R . I N T H E A I R
I T A L I C . R O S E A N N E
N A N A N A . E X E M P T E D

words correct: 66
words incorrect: 2
characters incorrect: 1

SCORE: 985

Like humans, Proverb is sensitive to the difficulty of the clues. Unlike humans, Proverb can be presented with three different sets of clues for the same solution and not notice. On this puzzle, Proverb's score improves quite a bit from 430 (43 words correct) for puzzle A, to 915 (64 words correct) for puzzle B, to 985 (66 words correct) for puzzle C (shown above). Note that the single letter error here came from an inability to produce the past tense for "Met, as the occasion" (ROSETO).

Final result: Proverb's total score for Puzzles #1-#7 in the 1999 tournament is 8395 points. Had it competed, it would have finished in 147th place out of 255 contestants.

Read more about PROVERB