The writer of puzzles often invents puzzles to illustrate a principle. The puzzles, however, sometimes have other ideas. Sometimes, they speak up and say that they would be so much prettier as slight variants of their original selves. The dilemma is that the puzzle-writer sometimes can't solve those variants. Sometimes he finds out that his colleagues can't solve them either, because there is no existing theory for solving them. We discuss a few such upstarts inspired originally from the layout of planar graphs, zero-knowledge proofs, industrial design, computational geometry, and code invention. They have given a good deal of trouble to a certain mathematical detective whom I know well.


Dennis Shasha is a professor of computer science at the Courant Institute of NYU where he works with biologists on pattern discovery for microarrays, combinatorial design, and network inference; and with physicists and financial people on algorithms for time series. Other areas of interest include database tuning, tree and graph matching, and cryptographic file systems. In his spare time, he has written three books of puzzles, a biography of great computer scientists, and technical books about database tuning, biological pattern recognition and an upcoming book time series.
He also writes the puzzle column for Scientific American and Dr. Dobb's Journal.