Enlarge

SUDOKU SCIENCEA powerful but mysterious computational algorithm may reveal its secrets when it’s applied to Sudoku puzzles. One is shown here unsolved (left) and then solved. So far, the algorithm has been able to solve every Sudoku it's tried.

You’re under a deadline, but your daughter will never forgive you if you miss her soccer game. Either obligation alone would be no problem, but trying to find the solution that satisfies everyone — or least minimizes their dissatisfaction — makes your stomach churn.

The same problem, it turns out, plagues science. And optics researchers may have found a solution. An algorithm they developed to balance competing constraints (like your daughter’s soccer game and your deadline) has been used to predict how proteins fold, improve radiation treatment for cancer, and even solve Sudoku puzzles.

Until a mathematician and a physicist caught wind of it, though, no one realized it might apply to anything much beyond manufacturing telescopes and microscopes.

At an optics conference, mathematician Heinz Bauschke of the University of British Columbia and theoretical physicist Veit Elser of Cornell University kept hearing about some mysterious, wonderful algorithm. No one had any idea how it worked, but it seemed to do its job marvelously well.

The algorithm was designed to create a sort of microscope that would reveal the atomic structures of crystals and other materials. Optics researchers would bombard the crystals with X-rays and keep track of how the X-rays would scatter. Each scattering direction provided a constraint on the structure of the crystal, just like the demands of your boss and your daughter constrain your time. James Fienup of the University of Rochester developed an algorithm in 1982  to find the structure that satisfied all those constraints. When the data had a bit of noise in it so that no one structure would work perfectly, it found the one that was closest.

After the conference, Bauschke and Elser reverse-engineered this algorithm to figure out how it worked. The technique, they realized, might be useful for computational problems throughout science. “The remarkable thing is that almost any problem, even the hardest, can be expressed by saying that the thing you’re looking for satisfies two properties, where satisfying each independently isn’t so hard,” Elser says. “The real challenge is figuring out how to satisfy both.”

The algorithm has one little gotcha: its calculations might never stop. In fact, the two researchers realized that the technique was a variation on one mathematicians had known for a long time, called a projection algorithm. But mathematicians knew that the algorithm, even though it hardly ever stops, can stop in very particular conditions — conditions the optical folks weren’t meeting.

Mathematicians imagine a constraint as being like a blob in the plane. Asking for a solution that satisfies two constraints is like looking for a point that lies in two different blobs. The mathematicians’ technique was to start by picking any old starting point in the plane. Since it probably won’t lie in both blobs, they next take the point closest to it that lies within the first blob (which isn’t hard to find). But then chances are that this new point won’t lie in the second blob, so they continue by taking the point closest to the new one in the second blob (even though it probably won’t be in the first blob). They continue back and forth like this, picking the closest point within one blob and then the other.

This projection algorithm can carry on for a long time. Yet, surprisingly, this see-saw process will eventually yield a point that lies within both blobs — if the blobs are convex, with no holes or indentations. When the optics folks developed their variation on this technique, though, their “blobs” weren’t convex at all. So there were no guarantees that the see-saw would halt.

But what the optics researchers had discovered was that with a slight variation of the procedure, most of the time, it did stop. Not only that, it did so very quickly and efficiently, without keeping the computers running for hours or days.

“As mathematicians, this drives us crazy,” Bauschke says, “because we don’t know why it works so well.”

So Bauschke is determined to find out. He knows that in some circumstances, the algorithm does fail to complete, so he’s looking for a simple example to understand. A good place to look, he figured, would be Sudoku.

Sudoku puzzles are nine-by-nine grids, divided into three-by-three sections, partially filled in with numbers. The challenge is to fill the remaining squares in so that every row, column and subgrid has exactly one of the numbers 1 through 9. That rule provides the constraints.

Elser, Bauschke and his graduate student Jason Schaad created a computer program that solves Sudoku puzzles using the projection algorithm method. So far, the program has solved every puzzle that’s been thrown at it. Bauschke is hoping it will come up with one it can’t solve soon so that he can understand what makes that Sudoku special. Furthermore, he says, finding one it fails on “would relieve me, because then I’d know there isn’t a theorem out there we need to prove that the method always works on Sudoku!”

In the meantime, Elser, Bauschke and other colleagues started getting the word out about the technique to other fields, and it has had some remarkable successes. For example, killing a tumor requires delivering lots of radiation to the tumor without hitting too much of the surrounding tissue: competing constraints! The projection method has been used to develop Intensity-Modulated Radiation Therapy, one of the most precise methods of radiation treatment.

They haven’t gotten to the soccer game problem yet, though.

• Email
• |
• Print
• |
• Comment