Sudoku, folding proteins and coherent diffraction

…all of these problems have a lot in common – they involve exhaustive search with a huge number of parameters, accompanied by a similarly large number of constraints, or rules.

The picture on the left is from the cover illustration to PNAS issue back in January of this year, accompanied by the paper by Elser et al., “Searching with iterated maps” PNAS 104, 418 (2007).

One of the key applications is in coherent x-ray imaging – coherent diffraction patterns are fourier transforms of real-space density of an object, but due to phase problem (loss of phases during the measurements of x-ray intensities) one can’t simply perform inverse fourier transform to get back to real-space image. But oversampling – measuring intensities at at least twice the spatial frequency of the object – can solve the phase problem by bringing the number of equations equal to the number of unknown variables again. One can solve for phases by considering restraints, or rules, imposed by such experiments – for example, intensities are known (while phases are not), real space densities are real positive numbers, typically contained within a finite volume (support). There may be more elaborate restraints.

By using an approach based on differential map algorithm one can alternate performing simple projections in real and reciprocal space, using the restraints mentioned above, alternated with Fourier transforms to go from real space to reciprocal space and back.

This approach can be applied to other problems – from finding the local minimum in energy landscape for protein folding, packing and tiling probelms to finding a unique solution for sudoku problems, jumble and other puzzles.

For more info see this wikipedia page or slides of talk by Veit Elser from his Cornell webpage.