Sudoku

Abstract Construct Lab note Result

Abstract

We're trying to make E.coli solve Sudoku puzzle. Human and Computers can solve Sudoku, of course. But E.coli, which is lower animal, solves sudoku in our project. It is very very interesting!

What is Sudoku?

What's Sudoku?

Sudoku is a famous puzzle game. It is now widely known all over the world. There are a lot of version of Sudoku puzzle, but the 9×9 cells version is the most famous. 81 cells are divided into nine smaller squares containing nine cells each; we call them subgrids. The puzzle setter provides a partially completed grid, which typically has a unique solution. The player must fill in the empty cells with the numbers 1 to 9 in such a way that no digit appears twice in the same row, column or subgrid. It looks like a Latin square. Sudoku requires no math, but logic. Sudoku became an international hit in 2005.

E.coli solves Sudoku?!

Each E.coli possesses two information

Every cells "consider" independently

How does E.coli solve a Sudoku puzzle? Now we explain it with simple version puzzle, 2 blocks of contiguous 4×4 cells.

E.colis are on each cells. Every E.coli has the number information and the locate information where it is on. When we solve 4×4 puzzle, we have to fill in the empty cells with the numbers 1 to 4, and use the same number only once in the same row, column or subgrid. So, when every E.colis can transmits information mutually, E.colis can solve puzzle in parallel. To realize this, we use "4C3 leak switch" and "signal virus."

Solution unique to the microbe: parallel computing

To solve Sudoku by human or the computer, we have to check the candidate of numbers which matches the rules for each 9x9 boxes. On the other hand, E. coli can fill in all boxes at a time by the system below.
-Judging all boxes simultaneously.
-Getting information about the location. (Which boxes they are in?)
-Outputting the correct number.
In other words, we propose the possibility of the new method of calculation, parallel computing, which has never been realized by traditional computers.

Differentiation model in prokaryote

E. coli in each box rearrange DNA and determine their numbers by receiving information about the number from other E. coli in the same row, column, and block. In other words, they change their states irreversibly from “the multi-output state” to “the uni-output state.” This process is similar to the process of multicellular organisms, which can differentiate depending on the situation around them. We consider that to build such differentiation model in prokaryote will lead to more profound understanding for life.

Information transmission by virus

E. coli in each box have to transmit their information of the number to the other appropriate boxes (Boxes which are in the same raw, column, and 3x3 boxes). To realize this “destination-restricted information diffusion,” we propose new information transmission system using RNA phage. With embedding information of the number and location in RNA loaded into the phage, we realize information transmission to the particular E. coli. This “destination-restricted information diffusion” can be a powerful tool for building bio-computer, which uses the creature as the unit of calculation.

Possibility of application for Artificial Intelligence

Originally, the process of solving Sudoku can be accomplished with high-level intelligence like human. Therefore, we suppose that implementation of this process in E. coli, or prokaryote, can play an important role in developing artificial intelligence.

Appeal point

Parallel computing

Our E.coli is superior to PC.

Differentiation model

This is a model of Eukarya differentiation model created by prokaryote.

Future vision

?????