Beta

Slashdot: News for Nerds

×

Welcome to the Slashdot Beta site -- learn more here. Use the link in the footer or click here to return to the Classic version of Slashdot.

Thank you!

Before you choose to head back to the Classic look of the site, we'd appreciate it if you share your thoughts on the Beta; your feedback is what drives our ongoing development.

Beta is different and we value you taking the time to try it out. Please take a look at the changes we've made in Beta and  learn more about it. Thanks for reading, and for making the site better!

Problem-Solving Bacteria Crack Sudoku

samzenpus posted more than 3 years ago | from the and-your-bacteria-just-stink dept.

Biotech 86

techbeat writes "A strain of Escherichia coli bacteria can now solve logic puzzles – with some help from a group of students at the University of Tokyo, Japan, reports New Scientist. The team began with 16 types of E. coli, each colony assigned a distinct genetic identity depending on which square it occupied within a four-by-four sudoku grid.The bacteria can also express one of four colors to represent the numerical value of their square. As with any sudoku puzzle, a small number of the grid squares are given a value from the beginning by encouraging the bacteria in these squares to differentiate and take on one of the four colors. The Tokyo team's sudoku-solving bacteria competed in the International Genetically Engineered Machine competition at the Massachusetts Institute of Technology last week."

cancel ×

86 comments

They May Crack Sudoku ... (1, Redundant)

WrongSizeGlass (838941) | more than 3 years ago | (#34263152)

They may be able to crack Sudoku but can they fix the cracks in concrete? [slashdot.org]

Re:They May Crack Sudoku ... (-1, Troll)

Anonymous Coward | more than 3 years ago | (#34263502)

Japan eh?

So how do you blindfold a Japanese? Dental floss.

Thank you folks. I'll be here all fucking night.

Wrong link in TFS? (1)

brainfsck (1078697) | more than 3 years ago | (#34263832)

When I clicked on the first link, I got a preview "article" titled "Sign in to read: brain asymmetry eases hypnotic trance". What relation does this have to the summary? On another site, I would ascribe this to a foolish error, but I'm sure the editors at Slashdot would never allow such a mistake to happen.

Re:Wrong link in TFS? (3, Funny)

WrongSizeGlass (838941) | more than 3 years ago | (#34264028)

When I clicked on the first link, I got a preview "article" titled "Sign in to read: brain asymmetry eases hypnotic trance". What relation does this have to the summary?

Once you're in an asymmetric hypnotic trance /. seems much easier to understand.

Re:They May Crack Sudoku ... (1)

K. S. Kyosuke (729550) | more than 3 years ago | (#34267130)

They may be able to crack Sudoku but can they fix the cracks in concrete? [slashdot.org]

Jeez, didn't you have biology in high school? Sudoku is what the bacteria are doing in their spare time, their day job being repairing concrete.

Next Step (1, Funny)

Anonymous Coward | more than 3 years ago | (#34263164)

Now if we can just get the bacteria to watch "Sarah Palin's Alaska", we'll have another 3.4x10^35 registered Republican voters.

Re:Next Step (1)

monkyyy (1901940) | more than 3 years ago | (#34281102)

along with 5.9x10^37 of them who hate people and stay inside all day

I for one... (1, Insightful)

drcheap (1897540) | more than 3 years ago | (#34263176)

I, for one, welcome our sudoku-solving underlords.

Link (4, Informative)

PatPending (953482) | more than 3 years ago | (#34263220)

Try this [igem.org] URL instead.

What's so special? (1, Insightful)

iviv66 (1146639) | more than 3 years ago | (#34263222)

I could probably solve a sudoku with some help from a group of students at the University of Tokyo as well.

There you go... (0)

Anonymous Coward | more than 3 years ago | (#34263692)

You have just proved your intelligence's upper limit matches that of the bacteria.

Re:There you go... (0)

Anonymous Coward | more than 3 years ago | (#34264618)

While it doesn't really establish an upper limit, it's still significantly better than those who can't solve a sudoku with some help from a group of students at the University of Tokyo.

Re:There you go... (1)

monkyyy (1901940) | more than 3 years ago | (#34286448)

i bet some paper could solve a sudoku from and young child

Re:What's so special? (5, Funny)

supertrinko (1396985) | more than 3 years ago | (#34263794)

The fact that you're comparing your abilities to that of bacteria worries me.

Real Link (1)

cpicon92 (1157705) | more than 3 years ago | (#34263260)

This [newscientist.com] is the article the summary is actually referring to.

Call me when... (1, Funny)

Dexter Herbivore (1322345) | more than 3 years ago | (#34263278)

They can solve the Times crossword, *then* I'll be impressed.

Re:Call me when... (1)

julesh (229690) | more than 3 years ago | (#34265768)

Or, you know, a *real* Sudoku. A Sudoku puzzle has 81 squares, not 16.

Re:Call me when... (3, Interesting)

delinear (991444) | more than 3 years ago | (#34266178)

Taniuchi does say in this article [newscientist.com] "By expanding these principles, 81 types of bacteria could solve a full nine-by-nine grid" - the number of squares that can be solved seems to be entirely dependent on the number of bacteria types, and they were working with 16 types. I don't know how easy it would be to expand that to 81 types (I don't know what differentiates a bacteria "type" or how many variants are commonly available, etc). I assume there was some reason they didn't go with 81 types right away, but maybe it was just time limitations and the maths is solid enough that you can reasonably extrapolate up from a small sample.

The Wonderful World of Synthetic Biology (2, Informative)

Anonymous Coward | more than 3 years ago | (#34263290)

Slashdot, I applaud your enthusiasm about synthetic biology and the iGEM competition. For all you interested folks out there, check out 2010.igem.org for information about the competition, and take a look at all the awesome wikis made by teams who competed. Also check out the results page at ung.igem.org/Results?year=2010.
-From your friendly 2010 iGEM competition participant

I smell a conspiracy! (2, Interesting)

kheldan (1460303) | more than 3 years ago | (#34263310)

It is my contention that this scientific breakthrough has been intentionally hushed-up by politicians from both sides of the aisle so that it wouldn't be released before elections just a few weeks ago. Why, even here in California, this remarkable bacteria, showing much more intelligence and logical-thought ability than anyone else on the ticket, would have been a write-in landslide victory for governor!

Re:I smell a conspiracy! (1)

fahrbot-bot (874524) | more than 3 years ago | (#34263382)

Why, even here in California, this remarkable bacteria, showing much more intelligence and logical-thought ability than anyone else on the ticket, would have been a write-in landslide victory for governor!

Unfortunately, most Americans probably cannot spell "Escherichia coli", "bacteria", or even "E. coli" (trouble w/the "E", I'm sure) so the write-in campaign would have failed. Some would deny that the bacteria could have even evolved to be so intelligent. A few would have questioned the bacteria's citizenship.

Re:I smell a conspiracy! (1)

OutSourcingIsTreason (734571) | more than 3 years ago | (#34269334)

showing much more intelligence and logical-thought ability than anyone else on the ticket

That's a low bar.

Why E.coli? (1, Informative)

John Saffran (1763678) | more than 3 years ago | (#34263314)

From wiki it seems that it's widely used for genetic experiments:

E. coli is frequently used as a model organism in microbiology studies. Cultivated strains (e.g. E. coli K12) are well-adapted to the laboratory environment, and, unlike wild type strains, have lost their ability to thrive in the intestine. Many lab strains lose their ability to form biofilms.[70][71] These features protect wild type strains from antibodies and other chemical attacks, but require a large expenditure of energy and material resources.

In 1946, Joshua Lederberg and Edward Tatum first described the phenomenon known as bacterial conjugation using E. coli as a model bacterium,[72] and it remains the primary model to study conjugation.[citation needed] E. coli was an integral part of the first experiments to understand phage genetics,[73] and early researchers, such as Seymour Benzer, used E. coli and phage T4 to understand the topography of gene structure.[74] Prior to Benzer's research, it was not known whether the gene was a linear structure, or if it had a branching pattern.

E. coli was one of the first organisms to have its genome sequenced; the complete genome of E. coli K12 was published by Science in 1997.[75]

The long-term evolution experiments using E. coli, begun by Richard Lenski in 1988, have allowed direct observation of major evolutionary shifts in the laboratory.[76] In this experiment, one population of E. coli unexpectedly evolved the ability to aerobically metabolize citrate. This capacity is extremely rare in E. coli. As the inability to grow aerobically is normally used as a diagnostic criterion with which to differentiate E. coli from other, closely related bacteria such as Salmonella, this innovation may mark a speciation event observed in the lab.

By combining nanotechnologies with landscape ecology complex habitat landscapes can be generated with details at the nanoscale.[77] On such synthetic ecosystems evolutionary experiments with E. coli have been performed in order to study the spatial biophysics of adaptation in an island biogeography on-chip.

http://en.wikipedia.org/wiki/Escherichia_coli [wikipedia.org]

but out of all bacteria that could use used why use one associated with human disease?

Re:Why E.coli? (2, Insightful)

damn_registrars (1103043) | more than 3 years ago | (#34263520)

but out of all bacteria that could use used why use one associated with human disease?

How many bacteria can you think of that are not associated with some human disease? Even the yeast that we use to make beer (and bread) can be a disease agent under the right (or wrong) circumstances.

That said, for each bacterium you can name that is associated with disease, the same has numerous strains that don't harm humans. The E Coli used in the lab is not the same strain that is found in cattle feces.

Re:Why E.coli? (1)

Shirakawasuna (1253648) | more than 3 years ago | (#34273094)

In fact, having a robust normal microbiota is associated with health and commensal E. coli (like those from which typical lab strains are derived) are part of that. They hang out, digest materials you wouldn't, make some vitamins, keep your immune system up to snuff (these interactions are essentially 'expected' by your system), and most importantly take up space and nutrients that potential pathogens could use.

In addition, the pathogenic E. coli have several virulence factors that lab strains don't (except when studying the disease-causing strains, of course). Finally, you, yes YOU or maybe YOU over there are chock full of bacteria that are directly associated with disease and full of nasty virulence factors. You are for all purposes a walking disease-passing machine which is simply capable of keeping these microbes in check. One errant cough could have you passing on an antibiotic-resistant S. pyogenes and causing someone who is immune compromised to come down with Scarlet Fever. In short, you are much more dangerous than these E. coli, yet a lot of you probably don't even wash your hands properly.

Re:Why E.coli? (2, Informative)

genomancer (588755) | more than 3 years ago | (#34263576)

Disease and biological study are sort of a circular dependency.

E.coli is one of the best biological test organisms because we've studied it so much. We understand most of its genetics, reproductive behavior, control signals, metabolism, etc... in part because it's fairly simple, but also precisely because it causes disease so it has been studied a lot in the past. It's also not very pathenogenic compared to most organisms... anything out of control is dangerous but it grows slowly and needs a lot from its environment so it's easy to keep in check.

The same holds true for a lot of "model organisms" (species that biologists can mess with without too many moral complications, like E.coli and fruit flies). S.aureus ("Staph") and Y.pestis (the plague) are horrific little bugs if they go unchecked in the wild... but they have a lot to teach us and if we can learn how to stop them we stand to gain a lot. Soo they're among the most studied species out there. Same goes for S.cerevisiea... baker's yeast :).

G

Re:Why E.coli? (5, Informative)

atmtarzy (1267802) | more than 3 years ago | (#34263610)

Cultivated strains (e.g. E. coli K12) are well-adapted to the laboratory environment, and, unlike wild type strains, have lost their ability to thrive in the intestine. Many lab strains lose their ability to form biofilms.[70][71] These features protect wild type strains from antibodies and other chemical attacks, but require a large expenditure of energy and material resources.

Basically the E. coli K12 gets totally owned by our immune system, as in before it has a chance to cause much damage, as in it doesn't make us sick, as in it is not "associated with human disease". In an abstract sense, saying, "K12 is 'associated with human disease' because O157:H7 is (and probably others are) associated with human disease," is very much like saying, "garden snakes/<insert relatively harmless snake> are associated with human death because black mambos/king cobras/<insert other deadly snake> is associated with human death." More colloquially put, "OMG it's a snake! It's going to kill me!" and "OMG it's E. coli! It's going to make me sick!" have the same logical flaws.

Re:Why E.coli? (1)

Thing 1 (178996) | more than 3 years ago | (#34267070)

"The K-12 dude. You make a gnarly run like that and girls will get sterile just looking at you."

Re:Why E.coli? (2, Funny)

AnonymousClown (1788472) | more than 3 years ago | (#34263662)

Not only that, but I wouldn't trust E. Coli bacteria for ANY solutions because they're usually full of shit ..er.. I mean they're usually on shit....no! I mean ....ah fuck it!

Re:Why E.coli? (0)

Anonymous Coward | more than 3 years ago | (#34264152)

Hey, we don't need to hear about your cophragia.

Re:Why E.coli? (1)

Mindcontrolled (1388007) | more than 3 years ago | (#34266580)

E. coli as such is not associated with human disease but rather a normal part of the intestinal flora. There are certain pathogenic strains, but those are in the minority. E. coli count is used for determining water quality, for example, because the presence of E. coli points to the presence of shit, not because of a pathogenic nature of the bacterium.

The main reason to chose E. coli is because it handles very well under lab conditions. Easy to culture, very robust.

Sudoku cracked! (1)

Junior J. Junior III (192702) | more than 3 years ago | (#34263334)

That's OK, can we just get some of the cementing bacteria to heal the cracks?

Bad news... (0)

Anonymous Coward | more than 3 years ago | (#34263392)

Hate to break it to you all, but I talked with this team at the conference and their system doesn't work yet. Neat design though!

They might crack Sudoku (0)

Anonymous Coward | more than 3 years ago | (#34263404)

But you'll never get bacteria to crack The Game of Life.

Re:They might crack Sudoku (1)

delinear (991444) | more than 3 years ago | (#34266230)

Actually bacteria are generally considered to be the first things ever to crack the game of life [wikipedia.org] .

Four by four? (2, Insightful)

TurtleBay (1942166) | more than 3 years ago | (#34263414)

Since when is a Sudoku puzzle 4 by 4 with 16 cells? I always played the nine by nine version with 81 cells.

Re:Four by four? (0)

Anonymous Coward | more than 3 years ago | (#34263478)

Aren't you special.

Re:Four by four? (3, Insightful)

The Clockwork Troll (655321) | more than 3 years ago | (#34263590)

More like Pseudoku.

Re:Four by four? (2, Informative)

Garth Smith (1720052) | more than 3 years ago | (#34263682)

While Sodoku is usually played with a 9x9 board, any square number would work. 4x4, 16x16, I've even seen a 25x25 in a Sodoku book before. (Started it, but didn't want to spend that much free time finishing it.) Technically you could have a 1x1 board but there's not much fun in that!

Re:Four by four? (1)

Dthief (1700318) | more than 3 years ago | (#34264610)

what about 1x1

Re:Four by four? (0)

Anonymous Coward | more than 3 years ago | (#34265664)

there's not much fun in that

Re:Four by four? (1)

somejeff (825047) | more than 3 years ago | (#34264692)

50% of trials were a success with binary sudoku! http://www.xkcd.com/74/ [xkcd.com]

Re:Four by four? (1)

tehcyder (746570) | more than 3 years ago | (#34266736)

Technically you could have a 1x1 board but there's not much fun in that!

Because there wouldn't be a unique solution.

Re:Four by four? (1)

camperdave (969942) | more than 3 years ago | (#34267748)

Technically you could have a 1x1 board but there's not much fun in that!

Because there wouldn't be a unique solution.

Yes there would.
3x3 sudoku uses the digits from 1-9
2x2 sudoku uses the digits from 1-4

So 1x1 sudoku would use the digits from 1-1. So here is the unique solution to all 1x1 sudoku:

1

There. Now, wasn't that fun?

Re:Four by four? (1)

etwills (471396) | more than 3 years ago | (#34267092)

While Sodoku is usually played with a 9x9 board, any square number would work. 4x4, 16x16, I've even seen a 25x25 in a Sodoku book before. (Started it, but didn't want to spend that much free time finishing it.) Technically you could have a 1x1 board but there's not much fun in that!

It isn't necessary to have a square number size, it just means that you are forced out of having a puzzle comprising row-, column- and square-based "house"s when you do. Various polyomino forms have been done, from plain rectangular to the the "Squiggly" variety at dailysudoku.co.uk

Being reasonably competent at the various 9x9 forms (I seek puzzles online because the only puzzle I've found in the national press that I can't solve is the supposed-world's hardest [guardian.co.uk] [solution [guardian.co.uk] ]), I can't see that there's any great complication possible in one of 4x4 size, although I'd imagine it was precisely the point to have *some* complexity but not *lots*.

sudoku is trivial (1)

Dr. Tom (23206) | more than 3 years ago | (#34263470)

I wrote a Python script to solve Sudoku puzzles. It takes 10 milliseconds. For a hard game where a guess is required, it takes 20 milliseconds. Interpreted Python. 10 milliseconds. Humans are terrible at this game because they can't remember 89 things at once. But it is really trivial.

Re:sudoku is trivial (1)

by (1706743) (1706744) | more than 3 years ago | (#34263714)

No one is claiming sudoku isn't computationally easy; it's the fact that bacteria are being used to solve problems mathematical in nature.

As an aside, 10 ms is about twenty million CPU cycles on a run-of-the-mill PC. So the fact that a handful of bacteria might be designed to solve a problem which takes you 20 million computations is pretty snazzy in my opinion. (The overhead of Python, the OS, your browser, the fact that the bacteria use a smaller sudoku grid etc. don't take away from any of this -- it's just a matter of degrees.)

Re:sudoku is trivial (0, Troll)

tehcyder (746570) | more than 3 years ago | (#34266742)

I wrote a Python script to solve Sudoku puzzles. It takes 10 milliseconds. For a hard game where a guess is required, it takes 20 milliseconds. Interpreted Python. 10 milliseconds. Humans are terrible at this game because they can't remember 89 things at once. But it is really trivial.

I bet you're a real hit at parties.

Re:sudoku is trivial (0)

Anonymous Coward | more than 3 years ago | (#34266898)

Yeah, it's a fierce competition between people who solve sudoku by hand and people who solve sudoku by computer - who is the wilder party animal?

Is it not in the Debian repositories yet? (0)

by (1706743) (1706744) | more than 3 years ago | (#34263738)

me@mybox:~$ sudo ku
sudo: ku: command not found
me@mybox:~$ sudo apt-get install ku
Reading package lists... Done
Building dependency tree
Reading state information... Done
E: Couldn't find package ku

Re:Is it not in the Debian repositories yet? (0)

Anonymous Coward | more than 3 years ago | (#34264788)

Lame.

Re:Is it not in the Debian repositories yet? (1)

TaoPhoenix (980487) | more than 3 years ago | (#34266922)

That codec is not FOSS.

On everyone's mind: (1)

Tablizer (95088) | more than 3 years ago | (#34263892)

But can they be bred to run Linux?

Generalized Sudoku is NP-complete (3, Interesting)

dido (9125) | more than 3 years ago | (#34263894)

The Sudoku problem is in general NP-complete [u-tokyo.ac.jp]

. If they can get the bacteria to solve a puzzle in the most general form efficiently, they might be on to something big. I have the feeling though it may turn out to be just as effective as Leonard Adleman's (the A in RSA) attempts at solving Hamiltonian Cycles and other NP-complete problems with DNA-based computing: incredibly promising, but running into practical issues as the problems grow from the trivial to the interesting.

Re:Generalized Sudoku is NP-complete (0)

Anonymous Coward | more than 3 years ago | (#34264216)

Would standard big O notation even matter here? In this situation you have a massive number of small processors limited in the data of the problem they have access to, compared to the traditional model of computation with one actor.

Re:Generalized Sudoku is NP-complete (0)

Anonymous Coward | more than 3 years ago | (#34264646)

Although the meaning does change a bit, you can still apply big-O to a computation on more than one processor. Obviously with exponentially many processors, an NP problem can be solved in polynomial time. On other hand, using O(n^2) (or some other polynomial) bacteria to solve an NP-complete problem in polynomial time would be an interesting result.

Re:Generalized Sudoku is NP-complete (1)

Sulphur (1548251) | more than 3 years ago | (#34265504)

Although the meaning does change a bit, you can still apply big-O to a computation on more than one processor. Obviously with exponentially many processors, an NP problem can be solved in polynomial time. On other hand, using O(n^2) (or some other polynomial) bacteria to solve an NP-complete problem in polynomial time would be an interesting result.

But will they publish their results?

Re:Generalized Sudoku is NP-complete (1)

FrootLoops (1817694) | more than 3 years ago | (#34265756)

Big-O notation can be used to refer to running time instead of the number of steps in an algorithm's solution. It's purely a notational convenience, saying that up to a multiplicative constant a function is eventually bounded above by another function. (Formally, there's a c so that for some X, x larger than X means f(x) is less than c*g(x).) In this generality it can be applied wherever you see fit.

Yes, Big-Oh is relevant: it's turing-simulatable (1)

jonaskoelker (922170) | more than 3 years ago | (#34266588)

Would standard big O notation even matter here?

Yes, although we're not saying "This takes O(f(n)) turing machine transitions" nor "This takes O(g(n)) instructions on an abstract pointer machine" nor "This takes O(h(n)) x86 cpu cycles".

In this situation you have a massive number of small processors limited in the data of the problem they have access to, compared to the traditional model of computation with one actor.

I conjecture this to be turing-simulatable with polynomial overhead. If they can do it in polynomial time, so can my turing machine. Which would prove P = NP. Which would be big news.

Re:Yes, Big-Oh is relevant: it's turing-simulatabl (1)

dido (9125) | more than 3 years ago | (#34279134)

The way I've always understood nondeterministic Turing machines is that they are an idealized model of computation where you in essence have unbounded parallelism. If you had very large numbers of processing elements, large enough to grow to the scale required for the problem which you're attempting to solve, then arguably you have what almost amounts to a nondeterministic Turing machine, albeit with a very large, but still finite, bound on parallelism. This is, after all, the reason why research is being done into getting very small objects such as bacteria and DNA molecules to perform computation: they offer the promise of far higher levels of parallelism than are possible with conventional computing devices. Quantum computers as I understand them seem to offer something very close, but not quite the kind of unbounded parallelism that should be offered by a hypothetical NTM, but this is a murky area of research (it involves showing that BQP [wikipedia.org] != NP, which seems about as hard as trying to prove P != NP).

Does that formalize? (1)

jonaskoelker (922170) | more than 3 years ago | (#34304776)

The way I've always understood nondeterministic Turing machines is that they are an idealized model of computation where you in essence have unbounded parallelism.

Can you formalise this?

I know you can define NP in two equivalent ways: as the languages of either (1) non-deterministic machines making polynomially many transitions along every computation path; or (2) deterministic polynomial-time machines which verify polynomially sized solution candidates to a given instance.

I'm not sure how parallelism enters the picture. I know of parallelism relating to NC, Nick's Class (see http://en.wikipedia.org/wiki/NC_(complexity) [wikipedia.org] ) which can equivalently be defined in terms of polylog-depth poly-size (acyclic) boolean circuits.

Your comments?

Re:Generalized Sudoku is NP-complete (1)

Mask (87752) | more than 3 years ago | (#34265510)

The Sudoku problem is in general NP-complete [u-tokyo.ac.jp]

.

From their website they are solving a simpler problem:

here we solve a 4x4 grid version. However, expanding on the same principles, our E. coli can theoretically solve larger grids, for example 9x9 grids.

9x9 Sudoku problems that you find in magazines or online are trivial Constraint Satisfaction Problems (CSP) [wikipedia.org] . Trivial CSP solvers can solve thousands of these in one second. By solving such a trivial problem I am not sure that their work can be scaled to more complex variants. Their 4x4 variant is so simple that it can even be solved efficiently by a trivial program which can be written from scratch in a couple of hours. This is in contrast to the general problem which is in a completely different class.

Re:Generalized Sudoku is NP-complete (1)

FrootLoops (1817694) | more than 3 years ago | (#34265574)

There are 288 [wikipedia.org] distinct 4x4 Sudoku puzzles (each grid is 2x2; the usual 9x9 case has 3x3 grids). There are ~4 billion 16-square grids of numbers 1-4, so these can be found easily with completely naive methods. A few hours is probably too generous :).

Big deal (1)

russotto (537200) | more than 3 years ago | (#34263958)

Compared to the tricks bacteria pull off to get past your immune system, a little Sudoku is child's play.

crazy (1)

juan2074 (312848) | more than 3 years ago | (#34264232)

Seems a lot easier to just use a pencil.

Re:crazy (0)

Anonymous Coward | more than 3 years ago | (#34266324)

Reminds me of Leslie Winkle [wikipedia.org] using a lab laser to heat her noodles (or coffee or whatever) when the microwave was broken. Typical scientists.

The interesting part of this article (3, Interesting)

shadow_slicer (607649) | more than 3 years ago | (#34264320)

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.

Re:The interesting part of this article (1)

Shirakawasuna (1253648) | more than 3 years ago | (#34273004)

Why is that frightening? Every in vivo molecular bio lab has hundreds (thousands?) of 'unique' bacterial strains, particularly E. coli. They are less viable in your system than the billions of bacteria hanging out on your skin (some of which are probably Staph. aureus) right now. In addition, they're usually derivatives of E. coli K12. Similar E. coli are in your colon right now, being nice, normal microbiota.

I may have misinterpreted your comment, though. It's mostly the last sentence that makes me think you're saying that the bacteria are dangerous or something. A sufficient quantity of bacteria for this experiment would involve 16 small tubes of broth and one day, so I don't see how it's... frightening. Your refrigerator is more diverse and vastly more likely to spread disease.

Bacteria, I dub thee.... (1, Funny)

Anonymous Coward | more than 3 years ago | (#34264516)

"Sudokoli"

Oblig (0)

Anonymous Coward | more than 3 years ago | (#34264636)

But can they play Crysis?

Carbon ? (1)

ProgramErgoSum (1342017) | more than 3 years ago | (#34264674)

But, what about the carbon footprint ? How much of life supporting medium is required for a given 'computational' bacteria ?

That's all??!! (0)

Anonymous Coward | more than 3 years ago | (#34264748)

This is all well and good... but what will really impress me is when they figure out how many bacteria are needed to change a light bulb!!

Next up: hantavirus solves Rubik's Cube (1)

andrew_d_allen (971588) | more than 3 years ago | (#34265050)

Next up: modified hantavirus that can solve the Rubik's Cube in less than 21 moves.

Re:Next up: hantavirus solves Rubik's Cube (1)

FrootLoops (1817694) | more than 3 years ago | (#34265774)

(This is a reference to God's number [bbc.co.uk] , which is 20.)

E. coli & soduko? (0)

Anonymous Coward | more than 3 years ago | (#34265402)

I should do more puzzles while on the crapper....

Biological computing again? (0)

Anonymous Coward | more than 3 years ago | (#34265556)

Biological computing rears its bacteria laden head every few years. I remember a few years ago a guy with four large vats of a bacterium managed to get them to solve the travelling salesman problem faster than any computer known. Problem was, he couldn't ask them how they did it. Its nice to see its not dead (oh just ignore the pun sparky), just hibernating for a while (ok, pay serious attention to that pun, serious).

web designing (1)

saiyom123 (1941960) | more than 3 years ago | (#34265730)

The address of sudoku has advance to the prokaryotic world. A ache of Escherichia coli bacilli can now break the argumentation puzzles “ with some advice from a accumulation of acceptance at the University of Tokyo, Japan. "Because sudoku has simple rules, we acquainted that maybe bacilli could break it for us, as continued as we advised a ambit for them to follow," says aggregation baton Ryo Taniuchi. The aggregation activate with 16 types of E. coli, anniversary antecedents assigned a audible abiogenetic character depending on which aboveboard it active aural a four-by-four sudoku grid. The bacilli can aswell accurate one of four colours to represent the after amount of their square. As with any sudoku puzzle, a baby amount of the filigree squares are accustomed a amount from the alpha by auspicious the bacilli in these squares to differentiate and yield on one of the four colours web designing company in chandigarh [saiyom.com] .

Oblig. (0)

Anonymous Coward | more than 3 years ago | (#34265990)

No. shit!

Politics (1)

haydensdaddy (1719524) | more than 3 years ago | (#34266966)

Now... Sudoku, next... Congress!

Re:Politics (1)

drkim (1559875) | more than 3 years ago | (#34279334)

I don't think Congress will ever be able to solve Sudoku.

When they try it with a virus (1)

zhub (1877842) | more than 3 years ago | (#34272184)

The virus that ends up wiping out humanity will have been engineered to solve the NYTimes crossword puzzle.

Bad Article (1)

Shirakawasuna (1253648) | more than 3 years ago | (#34272936)

Outside of this article, there's no indication that these E. coli actually exist. Check the U Tokyo iGem page: http://2010.igem.org/Team:UT-Tokyo/Sudoku_construct [igem.org]

I guess it's difficult since their page keeps talking about 'our E. coli', but we also never see any results from 'their E. coli'. I think they're more hypothetical at this point.

They have an interesting model and system, but nothing on their actual E. coli or their results. Everything is idealized and simulated. I think there must have just been some kind of miscommunication. If they had actually created bacteria that solved sudoku, they would have done better in the contest.

Groundbreaking research (0)

Anonymous Coward | more than 3 years ago | (#34277530)

Thanks for the link [newscientist.com] . It had never occurred to me that when I'm being hypnotized, bacteria play sudoku in my brain!

Bad Headline, replace with... (1)

hallux.sinister (1633067) | more than 3 years ago | (#34279394)

Japanese university students succeed in creating worlds smallest cyborg thinking-machine robots. Fleshy, squishy micro-borg can now outdo me in Sudoku?!? RUN! FLEE FOR YOUR LIVES!

Check for New Comments
Slashdot Account

Need an Account?

Forgot your password?

Don't worry, we never post anything without your permission.

Submission Text Formatting Tips

We support a small subset of HTML, namely these tags:

  • b
  • i
  • p
  • br
  • a
  • ol
  • ul
  • li
  • dl
  • dt
  • dd
  • em
  • strong
  • tt
  • blockquote
  • div
  • quote
  • ecode

"ecode" can be used for code snippets, for example:

<ecode>    while(1) { do_something(); } </ecode>
Create a Slashdot Account

Loading...