A new kind of counting: Scientists develop computer algorithm to solve previously unsolvable counting problems
February 11th, 2009 in General Science / Mathematics
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
(PhysOrg.com) — 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.
Here is the full article.
Special thanks to Gene for sending us the link.
Nice article. Is there a mathematical explanation for the failure of Goichberg and his cronies?
Chess politics – I suppose the powers that be will let the above stand – I wonder why?
“Chess politics – I suppose the powers that be will let the above stand – I wonder why?”
Because you are a Jackass Brian?