The interesting part of this article (to me) is not that they made bacteria solve sudoku. What I find interesting is how they solved it:
1) Unlike most sudoku solvers, which use a centralized algorithm. The bacteria use a distributed algorithm: Each individual bacteria cell only knows the contents of cells in their row or column. It's actually a lot more complicated than this though, since there are many bacteria cells for each sudoku square and cells only respond to the first signal they hear from a given position. Given enough bacteria (or time to grow them), the bacteria could brute force a solution (though there appear to be some inherent heuristics that would make a solution probable without the bacteria differentiating into all possible types).
2) The way logic is implemented. They use, what they call a 4C3 leak-switch. This basically is a piece of RNA that codes for 4 different proteins. This piece of RNA can only be transcribed to proteins when there is only one protein left. When the signal is received from another cell, it removes the part of the RNA corresponding to that protein.
3) The communication infrastructure. The bacteria communicate by releasing simple viruses (coded for using the 4C3 leak-switch). These viruses are specialized to only infect bacteria in a certain row or column. When the viruses infect a bacteria they remove the part of the RNA in the 4C3 leak-switch. The viruses are specialized to only infect cells in the corresponding row or column.
The amount of biological power employed in this case is actually rather frightening. This requires the creation of (at least) 16 unique viruses and 16 unique bacteria. Specific receptors for the viruses to bind to the bacteria must have been designed and the protein for both the virus coat and payload transcription need to be tweaked and introduced to the bacteria. A sufficient quantity of each bacteria must have been created.