When Cornell physicist Veit Elser attempted to demystify an esoteric imaging problem for biologists, he had no idea his solution would also help subway riders and break room loiterers around the world figure out those challenging, Sudoku puzzles.
While creating an algorithm that could render images of small and delicate biological specimens, Elser inadvertently found a universal solution for the popular Japanese brainteasers.
“This algorithm, which was extremely effective in image reconstruction microscopy, was extremely general,” he said. “If you just express it in the right mathematical language it could be used in all kinds of things.”
Since 2001, Elser has been working on the “difference-map algorithm” to help scientists get rich, detailed images of small objects. When specimens, like a single yeast cell, are too small and fragile to easily examine, x-rays are bounced off of them in a process called diffraction microscopy. The scattered light waves are then collected and analyzed in order to get a clear picture of the objects.
One day, while wrapping his brain around a Sudoku grid, Elser realized that the tension set up in the puzzle was the same as what he had been trying to solve with his algorithm to render images from diffraction microscopy.
In order to analyze the light waves created during diffraction microscopy, scientists must know the amplitude of the waves and the phase angles at which the light was collected. If these two separate conditions are not met, the image will come back as “noise,” according to Elser.
“What will happen in all cases—except when you have a correct phase—is that these waves will combine and they will give you something that you know right away can’t be this object,” said Elser.
But diffraction microscopy is not the only function that has two sets of independent constraints. Sudoku puzzles are arranged so that the digits 1 through 9 must appear nine times throughout a nine-by-nine grid. The second constraint is that all nine digits must be used within each of the nine three-by-three blocks.
Attempts at mastering Sudoku have been the cause of much hair pulling, frustrated screams and many countless nerd caucuses. But Elser may have finally found a way to put the puzzled minds of Sudoku fanatics to rest.
Also, Elser said, “I can finally explain to the man on the street what I do.”
In the process of writing algorithms to solve Sudoku puzzles, Elser learned how to play the old fashioned way: using a pen and paper.
“It’s more fun doing it that way than with a computer,” he said.
But the real motivation behind the “difference-map” wasn’t to solve the popular mind-bender, but to construct a quick and easy manipulation of wave and phase data to reconstruct 3D images of objects only a few microns in size. The Sudoku revelation is just “an extremely amusing illustration of that principle,” said Elser.
The process has already produced results. Images published in a recent article in the Proceedings of the National Academy of Sciences, authored by David Shapiro of the SUNY-Stony Brook, included pictures of a specimen as small as a single yeast cell that were taken without staining, sectioning or damaging the specimen.
“This work represents a previously uncharacterized application of x-ray diffraction microscopy to a specimen of this complexity and provides confidence in the feasibility of the ultimate goal of imaging biological specimens at 10-nm resolution in three dimensions,” said Shapiro in his paper’s abstract.
Originally published March 8, 2006
