Home > Press > A new kind of counting: Göttingen-based scientists are developing a computer algorithm to solve previously unsolvable counting problems

Fig. 1: Left and center: A map of Germany with corresponding representation as a network. Top right: A simplified sudoku with three rows of three boxes. Bottom right: The representation as a network. "1" is represented in "red", "2" in "blue" and "3" in "yellow".
Image: Max Planck Institute for Dynamics and Self-Organization |

**Abstract:**

How many different sudokus are there? How many different ways are there to color in the countries on a map? And how do atoms behave in a solid? Researchers at the Max Planck Institute for Dynamics and Self-Organization in Göttingen and at Cornell University (Ithaca, USA) have now developed a new method that quickly provides an answer to these questions. In principle, there has always been a way to solve them. However, computers were unable to find the solution as the calculations took too long. With the new method, the scientists look at separate sections of the problem and work through them one at a time. Up to now, each stage of the calculation has involved the whole map or the whole sudoku. The answers to many problems in physics, mathematics and computer science can be provided in this way for the first time. (New Journal of Physics, February 4, 2009)

Whether sudoku, a map of Germany or solid bodies - in all of these cases, it's all about counting possibilities. In the sudoku, it is the permitted solutions; in the solid body, it is the possible arrangements of atoms. In the map, the question is how many ways the map can be colored so that adjacent countries are always shown in a different color. Scientists depict these counting problems as a network of lines and nodes. Consequently, they need to answer just one question: How many different ways are there to color in the nodes with a certain number of colors? The only condition: nodes joined by a line may not have the same color. Depending on the application, the color of a node is given a completely new significance. In the case of the map, "color" actually means color; with sudoku the "colors" represent different figures.

"The existing algorithm copies the whole network for each stage of the calculation and only changes one aspect of it each time," explains Frank van Bussel of the Max Planck Institute for Dynamics and Self-Organization (MPIDS). Increasing the number of nodes dramatically increases the calculation time. For a square lattice the size of a chess board, this is estimated to be many billions of years. The new algorithm developed by the Göttingen-based scientists is significantly faster. "Our calculation for the chess board lattice only takes seven seconds," explains Denny Fliegner from MPIDS.

This is how it's done: With the new method, the researchers move through the network node by node. As if the computer program were short-sighted, it only ever looks at the next node point and not at the whole network. At the first node point, it cannot finalize the color selection as it would have to know how all the other nodes are connected to each other. However, instead of answering this question, the program notes down a formula for the first lattice point which contains this uncertainty as an unknown quantity. As it progresses through the network, all the connections become visible and the unknown quantities are eliminated. Having arrived at the final node point, the program's knowledge of the network is complete.

This new method can be used on much more complicated cases than the existing standard algorithm. "We can now answer many questions in physics, graph theory and computer science that have hitherto been practically unsolvable," says Marc Timme from MPIDS. "For example, our method can be applied to antiferromagnetic solids," he adds. In these solid bodies, every atom has an internal rotational pulse, called spin, which can have different values. Usually, adjacent atoms exhibit different spins. It is now possible to calculate the number of possible spin arrangements, which will allow physicists to draw conclusions about the fundamental characteristics of the thermodynamics of solid bodies.

####

**About Max Planck Society**

The research institutes of the Max Planck Society perform basic research in the interest of the general public in the natural sciences, life sciences, social sciences, and the humanities. In particular, the Max Planck Society takes up new and innovative research areas that German universities are not in a position to accommodate or deal with adequately. These interdisciplinary research areas often do not fit into the university organization, or they require more funds for personnel and equipment than those available at universities. The variety of topics in the natural sciences and the humanities at Max Planck Institutes complement the work done at universities and other research facilities in important research fields. In certain areas, the institutes occupy key positions, while other institutes complement ongoing research. Moreover, some institutes perform service functions for research performed at universities by providing equipment and facilities to a wide range of scientists, such as telescopes, large-scale equipment, specialized libraries, and documentary resources.

**For more information, please click here**

**Contacts:**

Max Planck Society

for the Advancement of Science

Press and Public Relations Department

Hofgartenstrasse 8

D-80539 Munich

Germany

PO Box 10 10 62

D-80084 Munich

Phone: +49-89-2108-1276

Fax: +49-89-2108-1207

Dr. Birgit Krummheuer, Press and Publicity Office

Max-Planck-Institute for Dynamics and Self-Organization, Göttingen

Tel.: +49 551 5176-668

Dr. Marc Timme

Max-Planck-Institute for Dynamics and Self-Organization, Göttingen

Tel.: +49 551 5176-440

Copyright © Max Planck Society

If you have a comment, please Contact us.Issuers of news releases, not 7th Wave, Inc. or Nanotechnology Now, are solely responsible for the accuracy of the content.

Related News Press |

**News and information**

Oxford Instruments’ Triton Cryofree dilution refrigerator selected by Oxford University for developing scalable quantum nanodevices September 2nd, 2015

JEOL Introduces New Best-in-Class Field Emission SEM September 2nd, 2015

Atomic Force Microscopes from Asylum Research Guide the Development of Thin Film Deposition and Etch Processes September 2nd, 2015

**Discoveries**

For 2-D boron, it's all about that base: Rice University theorists show flat boron form would depend on metal substrates September 2nd, 2015

Silk bio-ink could help advance tissue engineering with 3-D printers September 2nd, 2015

Phagraphene, a 'relative' of graphene, discovered September 2nd, 2015

A marine creature's magic trick explained: Crystal structures on the sea sapphire's back appear differently depending on the angle of reflection September 2nd, 2015

**Announcements**

For 2-D boron, it's all about that base: Rice University theorists show flat boron form would depend on metal substrates September 2nd, 2015

Silk bio-ink could help advance tissue engineering with 3-D printers September 2nd, 2015

Phagraphene, a 'relative' of graphene, discovered September 2nd, 2015

A marine creature's magic trick explained: Crystal structures on the sea sapphire's back appear differently depending on the angle of reflection September 2nd, 2015

The latest news from around the world, FREE | ||

Premium Products |
||

Only the news you want to read!
Learn More |
||

University Technology Transfer & Patents
Learn More |
||

Full-service, expert consulting
Learn More |
||