Crossword Puzzles Under Evolutionary Stress
August 7, 2007
Philip J. Davis
"When in the chronicle of wasted time"
--Sonnet 106, William Shakespeare
In a review of the third edition of The Standard American Heritage Dictionary in the April 1995 issue of SIAM News, I considered the utility of the dictionary for crossword puzzle aficionados. That review appeared just before online search engines became generally available.
The time seems right for an update on crossword puzzles, and I begin with a few notes on my personal relation to them. I am very mildly addicted---I do at least one a day. Occasionally, when a friend gives me a collection from his newspapers, I may overdose. I am by no means an expert solver. I could never enter a puzzle-solving contest---I'm not in that class. Ability-wise, I would place myself in the lower half of solvers.
Because the manner in which puzzles are solved is not controlled or restricted by the laws of the United States or the state of Rhode Island or Providence Plantations, I have my own rules: I must solve the puzzle in ink. I allow myself the use of any data-bases that I have near my bed, which is where I usually work on puzzles. These databases include the Encyclopedia Britannica, two almanacs, dictionaries in English, French, German, and Spanish, a crossword puzzle dictionary, a dictionary of music and musicians, the Bible and a Bible concordance, a dictionary of fact and fable. I really should get myself a pop music and film reference book.
Now that search engines are firmly established, the first thing I do in solving a puzzle is to circle the definitions that mean nothing to me but are computer searchable. For the Sunday New York Times puzzle, this might amount to between 5% and 15% of the definitions. I find it impossible to make headway without this lift. Still, I am an impatient searcher and wish for a search engine that would give me the correct answer more rapidly, after a simple inquiry.
If I get stuck after this point, I freely allow myself the option of buttonholing anybody who happens to come my way. I use family members as databases, my wife for poetry and my son for sports. If the solution of a puzzle is printed in the same issue, I do not allow myself the option of seeing the answer. (Solving a puzzle completely leads to momentary ecstasy; leaving the slightest portion unsolved leads to agony that fortunately dissipates rapidly and rarely leads to my checking the answer the next day.)
You, dear reader, may think that these personal rules and practices are unethical, but I am not competing against any other person. Solving these puzzles is a relaxation that I allow myself to pursue according to my own rules. I tried very briefly to overcome my addiction, but resumed after I read that doing such things helps prevent degeneration of intellectual powers: If you don't use it you lose it. Yet, in a sense, I am competing against someone: the maker of the puzzle. More on him/her/it/them shortly.
The computerization of puzzles has moved forward rapidly. You can get puzzles online. You can get direct hints (and pay for them). Puzzles can be made by computer: As a birthday present, my daughter recently bought me a puzzle that, when solved, had my name built into it. Puzzles can be solved by computer. I was recently referred to a technical article on the computerized solution of puzzles.* The upshot of the project/write-up was the development of a puzzle solver called PROVERB, which "compared favorably to the 251 elite human contestants at the 1998 championship." Calling on at least 25 "expert modules" of information, it is reported to have high batting averages. Following in the footsteps of PROVERB, and improving on it, is WEBCROW, an Italian project.�
Have I learned anything from studying the architecture of these computer puzzle solvers? I doubt it; I think it goes the other way---that the programs simply automate what human solvers do (including making probability estimates). But there is an exception: I "backtrack," ending up with inky splotches in some squares, whereas the program of Littman et alii does not. In-stead, using a well-known algorithm called A* (A-star), the program keeps track of several alternative ways of partially filling in the puzzle. At each stage, the algorithm picks the alternative that looks most promising, generates one or more possible ways of filling in the response for the next clue, and re-estimates the quality of all these partial solutions. A* is not a technique that human solvers could use, but it's found in AI programs of various kinds.
Do the available solvers use any new programmatic techniques? Essentially, a puzzle-solving system has two aspects: first, very clever leveraging of online resources, combined with techniques specific to the way crossword puzzle clues are given, so as to generate lists of words marked with probabilities; second, combination of the probability measurements across different slots with the constraint that the answers be put together across and down. I've been told that the techniques here are probably somewhat new in detail, but do not represent a major programmatic innovation.
I now return to my adversary: the puzzle maker. I have not read any material put out by the makers of puzzles as regards their craft, so what I say here is by inference and may be a bit naive. If a puzzle is too easy, I junk it rapidly. If it's too hard---and it might take me a while to decide that it is---I junk it. The newspapers know this; puzzle makers have learned from experience how to gauge the difficulty and produce puzzles with a large range and for a varied clientele. A completed puzzle can be increased in difficulty simply by making the definitions more arcane, unusual, jargon-heavy, obsolete. Thus, "cat" might be defined as a feline, a pet, a device for raising an anchor, a tractor, a sailboat with twin hulls, the name of a ferry that plies between Maine and Nova Scotia, an island in the Bahamas, a hipster, etc. The greater the ambiguity the harder the puzzle, and the probabilities tend to move away from the "obvious" answer.
I assume that puzzle makers now take full advantage of the computerized databases and the specialized puzzle programs that are around. Why shouldn't they? Where formerly they were asking for the names of movie stars, now it is co-stars, directors, producers---and who knows but that the "best boys" will be next. What marriage of an important person took place in September 1908? We puzzle solvers may soon be asked for Pascal's mother's maiden name.
In the opposite direction, and paradoxically, there is a simultaneous thrust to work into the puzzles material that in some ways defies google-ization: current quips, puns, in-group slang or specialized terminologies, dialect, anagrams, inter-referential definitions (6A refers to 23D, and vice versa). Letters may be gratuitously added or omitted, yielding a common expression when subtracted or added. Obscure three-letter abbreviations abound. Google responds to practically any three-letter combination with the name of a program, an institution, etc. Example: PJD (my initials) yields almost a million suggestions, of which the first is the Justice and Development Program in Morocco. The imagination of puzzle makers is unlimited. A recent puzzle asked for "Advice from Georg Solti?" Solution: "Face the music." Evolutionary stress is working overtime here.
Some of the "themes" that have been inserted into puzzles are fun to work out; most are not. I admire the skill and the imagination of the puzzle makers who ply their craft in innovative ways, but for me, doing crossword puzzles has become a matter of my software versus my adversary's software. If this tendency strengthens, I shall look around for a different sort of recreation.�
* Littman, Keim, and Shazeer, A probabilistic approach to solving crossword puzzles, Artificial Intelligence, 134 (2002), 23�55. The authors were employed at AT&T Labs, Fairfield Language Technologies, and Google, respectively.
� http://webcrow.dii.unisi.it/webpage/implementation_details.html.
� Check out: Gene I. Rochlin, Trapped in the Net: The Unanticipated Consequences of Computerization, Princeton University Press, Princeton, New Jersey, 1997.
Philip J. Davis, professor emeritus of applied mathematics at Brown University, is an independent writer, scholar, and lecturer. He lives in Providence, Rhode Island, and can be reached at [email protected].
