Tea Leaves

It seems to be a reasonable childrearing principle that you should give kids a break in order to foster their creativity.  “Look, Mummy, I’ve made you a dinosaur out of cotton balls and toothpicks!”  “Oh Billy, that’s so precious.”  And it is.  But at some point, say after Billy has gotten his PhD in computer science, you need to finally expose him to the idea that the world is a competitive place and he needs to be a harsher critic of his own stupid ideas.

Every computer scientist in the world has, at some point, decided that he is going to write a computer program to generate crossword puzzles.  (That was my generation… today’s crop of top graduate students wants to write computer programs to generate Sudoku).  Just to be clear, the problem of crossword puzzle construction is different from that of crossword puzzle solving.  Solving, at least according to the TV ads, is what you do when you want to spend a lazy Sunday afternoon in bed with your hot boy/girlfriend, a pencil, your chrome/glass furniture, and a copy of the New York Times.  Construction refers to what the poor shlubs have to do to create those puzzles.  Specifically, it means starting with an empty grid (containing a smattering of black squares which define the boundaries between words), and then filling it with letters such that all the across and down slots contain different, valid words.  There are numerous technical conventions as well: the grids are typically square in shape, have a size of at least 11×11, and have rotational symmetry.  Experts try to keep the word count low (lower word count implies fewer black squares which implies a lot of interlock).  Before you publish such a puzzle you would also need to provide clever yet precise clues, but so far clueing is considered outside the scope of what a computer can do.

While reasonable people can differ about whether it makes sense to use taxpayer-funded defense money to pay a bunch of slackers to jerk around, the real problem is that every single person approaches the problem anew as if they were the first person to ever consider it.  You may be wondering what such people do when they graduate and get research jobs.  Give a computer scientist his first $500K grant, and I can guarantee you exactly what will happen:  “Look Mummy despite being ignorant of forty years of prior art I’ve built you a videoconferencing/telepresence system”.

But I’m talking about crossword puzzles.  If you want to be just like these computer scientists, here’s what you do.

• Think about the problem for 15 minutes.  Surely once you lay down a few words in the corner, the rest of the grid is so constrained that your search space is really small.  Right?
• Buy a copy of USA Today, and look at its crossword.  Stay in denial about whether expert constructors consider it a hard grid to fill.  After all, it must be good.  Lots of people read USA Today.
• Get some easily accessible online word list.  You’re so sophisticated that you know not to limit yourself to /usr/dict/words, so after some googling you find you can get OSPD (Official Scrabble Player’s Dictionary) or WEB2 (Webster’s New International Dictionary, 2nd Edition, which hails from the 1930s) online.
• Debug your program and be really impressed with yourself as it completes its search and fills your grid in like 5 seconds.  The fact that you’ve got QAT crossing QINTAR, as well as ESNE crossing ANOA… well, those are valid words, right?

This actually happened to me.  I found some guy who built such an automated crossword generator and showed it to me.  (By the way, he’s a friend.  Yes, I mock my friends.  And yes, after a few turns of the crank I have more mockery than friends.)   I took one of its output grids and gave it to another (not-yet-mocked) friend of mine, who happens to be a world-class crossword puzzle constructor.  Remember, I’m not talking about solving here.  I’m talking about construction: taking an empty grid and filling it with stuff.  It took him less than five minutes and I think he used his pencil eraser twice.  In other words, he filled the thing longhand almost as fast as he could write and did almost no backtracking.

Congratulations, you tragic little man, you have just built a computer program that quickly solves a problem that most practitioners would find trivial.

Because my gnomish anger is exceeded only by my thoroughness, I then asked my friend to provide me an example in the reverse direction: with a grid that he was able to fill successfully (so a solution is known to be possible) but that he found difficult (it had taken him several hours to do so).  I gave it to the other guy and asked him to feed it to his program.  It failed.  Horribly.  It was a total nightmare.

(One must take care to be precise when one is talking about with programs that run for a long time, especially those you suspect may never terminate.  To use a metaphor: strictly speaking, it is not correct to say that Matt Damon will never go on a man-date with me.  Perhaps Mattie and I will both go on severe calorie restricted diets and live to be 150; perhaps a thousand years from now, an insane alien computer will regenerate our personas from, in his case, footage from the film “Stuck On You”, and in mine, some DNA I may have left on a towel at the Holiday Inn).  My point is that the best you can say in these cases is that “Matt Damon has not gone on a man-date with me YET”.

Or, in the instant case, if a computer program correctly implements exhaustive search, sooner or later it will try all possibilities in the puzzle space.  Just realize that “later” can be, like, ”way” later, as in, dude! the sun just blew up and melted my ’puter!.”  In cases like this you basically have to pick a cutoff time and if the thing isn’t done by then, you pull the plug.  That’s what happened here.  He ran it for a few hours, maybe overnight, and then admitted failure.

I need to add a little postscript here.  Initially I wasn’t sure how this piece wanted to end.  Coming back to it after a couple of days, I realize that, I actually think doing research is a worthy endeavor.  And I think it’s quite common that some young punk comes along with an insight and shows a bunch of crusty old fools how things should be done.  So if you are a young punk, now that I’ve told you what NOT to do, I really ought to tell you what TO do.  One suggestion is this: because the search problem is, as they say, “embarrassingly parallelizable”, I’d like to take one of the open problems (an open 8×8 with no black squares) and see if you could find a fill for it using, like, some vast grid of 1000 CPUs.  Maybe you’d have to make a friend with access to a farm at MIT or Sandia or Google.  And remember, no words can repeat in the grid.  Allowing for repeated words makes degenerate grids that are very easy to fill.

Another suggestion is to study how humans create these puzzles.  They generally don’t use exhaustive search; they use insight, see patterns, know a bunch of tricks, and basically do a bunch of rejiggering when they find themselves painted into a corner.  It would be interesting to formalize this approach and see if you could get a computer to do the same.