From biological imaging to Sudoku
Scientists are like you and me: they sometimes need to relax. This is why Veit Elser, professor at Cornell University, has applied an algorithm developed for X-ray diffraction microscopy to solve Sudoku puzzles. The difference-map algorithm, which he discovered with other chemists and physicists, will be primarily used for biological imaging. But it also might be used in other applications, ranging from productivity optimization to nanofabrication. And of course, it can solve Sudoku puzzles. If you're interested in this subject, please read this summary which provides additional details, pictures and references about this new bioimaging technique.
Here is the introduction of the Cornell Chronicle article.
In discovering an algorithm critical for X-ray diffraction microscopy, [Cornell physicist Veit Elser] and colleagues solved two problems. First, they gave researchers a new tool for imaging the tiniest and most delicate of biological specimens. And second, they discovered that the same algorithm also solves the internationally popular numbers puzzle Sudoku. Not just one puzzle. All of them.
Below is a picture showing a Sudoku puzzle designed by Elser's difference map algorithm (Credit: Veit Elser, Cornell University). If you solve this puzzle, you can send him your solution (e-mail address available in the Cornell Chronicle article).
But how is it possible that an algorithm developed to solve biological imaging problems can also be used to solve Sudoku puzzles? Simply because both problems have a solution which has to meet two independent constraints.
You all know the Sudoku constraints, which are pretty simple. But in X-ray diffraction microscopy, things are much more complex.
But the beauty of the algorithm, as Elser demonstrates, is that complexity doesn't matter. By applying the algorithm to the jumble of raw data from such an experiment, researchers can now reconstruct from it a clear, detailed image.
[And] some of these methods [used] can damage the specimen with harmful radiation, require that a specimen be stained or otherwise altered or lack the penetrating power necessary for three-dimensional reconstructions. X-ray diffraction microscopy, which uses "soft" X-rays and measures the resulting diffraction pattern, is often the method of choice because it gives a detail-rich image and leaves the specimen relatively unscathed.
In fact, the tricky part -- and the solution of the problem -- is to correctly take into account "the waves' phases, which are critical in reconstructing an image from the diffraction data."
Below are some images of "a freeze-dried yeast cell. A was obtained by phasing the diffraction data in Fig. 1, whereas C and D were obtained from reconstructions of two separate, slightly lower exposure data sets acquired with the cell tilted by 3° (C) and 4° (D) relative to A" (Credit: PNAS).
In fact, the researchers used two simple constraints. First, they assumed that "the object in view [had] a clearly defined boundary (i.e., that all pixel values outside that boundary be set to zero)."
For the second constraint, the researchers required that the wave amplitudes used in the Fourier synthesis matched those measured by the experiment.
For more information, this research work has been published in the Proceedings of the National Academy of Sciences under the title "Biological imaging by soft x-ray diffraction microscopy" (Vol. 102, No. 43, Pp. 15343-15346, October 25, 2005). Here is a link to the abstract -- which doesn't really speak of Sudoku.
We have used the method of x-ray diffraction microscopy to image the complex-valued exit wave of an intact and unstained yeast cell. The images of the freeze-dried cell, obtained by using 750-eV x-rays from different angular orientations, portray several of the cell's major internal components to 30-nm resolution. The good agreement among the independently recovered structures demonstrates the accuracy of the imaging technique. To obtain the best possible reconstructions, we have implemented procedures for handling noisy and incomplete diffraction data, and we propose a method for determining the reconstructed resolution. 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.
And the full paper is available for free from the PNAS web site (PDF format, 4 pages, 378 KB). The second image on this page has been extracted from this paper.
Sources: Lauren Gold, Cornell Chronicle Online, February 27, 2006; and various web sites
You'll find related stories by following the links below.