# A new kind of counting: Scientists develop computer algorithm to solve previously unsolvable counting problems

##### Feb 11, 2009

(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.

"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.

More information: Marc Timme, Frank van Bussel, Denny Fliegner, and Sebastian Stolzenberg, Counting Complex Disordered States by Effiecient Pattern Matching: Chromatic Polynomials and Potts Partition Functions, New Journal of Physics 11 (2009), 023001, February 4th, 2009, www.iop.org/EJ/abstract/1367-2630/11/2/023001/

Provided by Max-Planck-Institute

Explore further: Researchers help Boston Marathon organizers plan for 2014 race

## Related Stories

#### Canada police nab young man in Heartbleed data theft

9 minutes ago

Federal police said Wednesday they have arrested and charged a 19-year-old man in the theft of 900 Canadian taxpayers' data, which was made vulnerable by the "Heartbleed" bug.

#### Two new species of yellow-shouldered bats endemic to the Neotropics

13 minutes ago

Lying forgotten in museum collections two new species of yellow-shouldered bats have been unearthed by scientists at the American Museum of New York and The Field Museum of Natural History and described in ...

#### Red moon at night; stargazer's delight

15 minutes ago

Monday night's lunar eclipse proved just as delightful as expected to those able to view it. On the East Coast, cloudy skies may have gotten in the way, but at the National Science Foundation's National Optical ...

#### Information storage for the next generation of plastic computers

18 minutes ago

Inexpensive computers, cell phones and other systems that substitute flexible plastic for silicon chips may be one step closer to reality, thanks to research published on April 16 in the journal Nature Communications.

#### California delays decision on protecting gray wolf

25 minutes ago

A state board says it needs more time to hear from the public before deciding whether to list gray wolves as an endangered species in California.

#### Computers beat brainpower when it comes to counting stars

25 minutes ago

A team of University of Sydney astronomers has developed a new way to automatically classify huge numbers of astronomical objects, and to discover new, exotic ones almost as soon as they happen.

## Recommended for you

#### Study looks at stock market performance of polarizing brands

7 minutes ago

Are you a big fan of Apple or Nike, or a hater of McDonald's? A new study from the W. P. Carey School of Business at Arizona State University shows love-it or hate-it brands probably won't perform exceptionally ...

#### Which foods may cost you more due to Calif. drought

26 minutes ago

With California experiencing one of its worst droughts on record, grocery shoppers across the country can expect to see a short supply of certain fruits and vegetables in stores, and to pay higher prices ...

#### Creative activities outside work can improve job performance

10 hours ago

Employees who pursue creative activities outside of work may find that these activities boost their performance on the job, according to a new study by San Francisco State University organizational psychologist Kevin Eschleman ...

#### Researchers reveal relationships between rare languages in the Colombian Amazon

13 hours ago

The only linguistic data available for Carabayo, a language spoken by an indigenous group that lives in voluntary isolation, is a set of about 50 words. This list was compiled in 1969 during a brief encounter with one Carabayo ...

#### Earliest ancestor of land herbivores discovered

13 hours ago

New research from the University of Toronto Mississauga demonstrates how carnivores transitioned into herbivores for the first time on land.

#### Performance measures for CEOs vary greatly, study finds

17 hours ago

As companies file their annual proxy statements with the U.S. Securities and Exchange Commission (SEC) this spring, a new study by Rice University and Cornell University shows just how S&P 500 companies have ...

##### vivcollins
not rated yet Feb 11, 2009
How long before this hits CFD I wonder
##### magpies
2.3 / 5 (3) Feb 11, 2009
Why is this new?
##### Husky
not rated yet Feb 11, 2009
A new word for the dictionary: quantumchromomathematics ?
not rated yet Feb 11, 2009
Ah the world of dynamic programming. If we can't solve problem A, but can solve problem B, just find a way to map B to A.

Trading storage for speed is a viable option now that memory is cheap.
##### h0dges
3.3 / 5 (3) Feb 11, 2009
Exciting stuff.
##### Soylent
not rated yet Feb 12, 2009
Trading storage for speed is a viable option now that memory is cheap.

Doesn't always work well; memory grows ever more distant from the processor(with the exception of integrated memory controllers).

When you're doing something that defeats the usual tricks of caching, out of order execution, speculative reads etc. (like pointer chasing or something) it's going to take upwards of 100-200 clock cycles to get the requested piece of data and you could have executed a lot of instructions in that time.
##### KBK
not rated yet Feb 12, 2009
It also presents a new methodological attack scenario for security encryption breach programming, ie the breaking of previously 'secure code'.

256 bit? Not good enough........

That's the way the essence of 'reality' tends to be. You can't have one side of the coin-without the other. Both situations emerge, relatively speaking-at the same time.

Sorry. That's the way she goes...
##### mogmich
not rated yet Feb 12, 2009
Maybe uncertainty in nature (Quantum Mechanics) is there for the same reason: in order to make an otherwise impossible calculation possible?
##### Damon_Hastings
not rated yet Feb 12, 2009
I am a computer programmer, and I am befuddled by this. How is this algorithm new? The description of the algorithm is fairly vague here -- the phrase "notes down a formula" is especially frustrating. Computers don't generally note down entire "formulas", so it's anyone's guess what this actually means.

I don't see any explanation of how this new algorithm differs from the standard backtracking (node-by-node) algorithm which was given in my computer science textbook in college 20 years ago, and which does *not* copy the entire matrix at each step, and which was quite slow anyway. Could the author of this article please explain the difference? The article refers to "looking at separate sections of the problem" which sounds tantalizingly like parallelization (which would indeed be a real improvement) -- but then goes on to describe what sounds like a standard backtracking algorithm with no parallelization.

The standard backtracking algorithm is listed as the first result from a google search on "map coloring backtracking algorithm". (Okay, well, that implementation does copy the entire matrix each time, but it would be rather trivial to add in an "undo" stack to allow undoing modifications which were made directly to the original matrix rather than a copy. They only left that optimization out of this example for simplicity, since this is a teaching manual for an introductory programming class.)
##### BeastOfBodmin
not rated yet Feb 15, 2009
From magpie:
> Why is this new?

From Damon_Hastings:
> I don't see any explanation of how this new algorithm differs from the standard backtracking ...

Have you read the actual paper linked to at the bottom of the article?
##### Damon_Hastings
5 / 5 (1) Feb 16, 2009
From Damon_Hastings:
> I don't see any explanation of how this new algorithm differs from the standard backtracking ...

Have you read the actual paper linked to at the bottom of the article?

That article is not written for even a well-educated computer programmer. It dives quickly and deeply into quantum mechanics, of all things. The "zero-temperature partition function of the Potts antiferromagnet" (whatever that is) seems to be the key to the whole thing.

To understand the dense, narrow-niche jargon would require several years of training in QM and apparently a few exotic fields of math, as well. But I don't really need a deep understanding anyway, just a basic overview. For that, a more efficient way to get a basic overview would be to just call the author and interview him. And then maybe I could summarize my basic overview into an article which I could publish on, oh, I don't know, maybe some popular science news website where others could benefit from my work without having to call the author themselves.

Personally, I don't think I should have to take a course in quantum mechanics to understand a new computer algorithm on map-coloring. But I don't know, maybe the author decided that no one without a QM degree could even understand a basic overview of this new algorithm, and that's why he left it out and instead gave a basic overview of *all* backtracking map-coloring algorithms.
##### paulcurran
not rated yet May 10, 2009
The Potts antiferromagnet is equivalent to the chromatic polynomial. The chromatic polynomial is a polynomial of a graph which counts the number of distinct ways it can be colored. Colorings are counted as distinct even they differ only by permutation of colors.

I read the article and while hard at times I was able to follow it. Granted I had some courses in QM, but that was over 20 years ago.

If this type of material is to become critical one day for programmers, one really doesn't need to study quantum mechanics. However I can see where studying the methods of QM would be very advantageous. But at one time calculus was seen as a rather esoteric topic but it is now seen as a topic that many need to know. Perhaps one day the mathematics of QM would be seen in the same light.

## More news stories

#### Earliest ancestor of land herbivores discovered

New research from the University of Toronto Mississauga demonstrates how carnivores transitioned into herbivores for the first time on land.

#### Ancient shark fossil reveals new insights into jaw evolution

The skull of a newly discovered 325-million-year-old shark-like species suggests that early cartilaginous and bony fishes have more to tell us about the early evolution of jawed vertebrates—including humans—than ...

#### Study: The trials of the Cherokee were reflected in their skulls

Researchers from North Carolina State University and the University of Tennessee have found that environmental stressors – from the Trail of Tears to the Civil War – led to significant changes in the ...

#### Creative activities outside work can improve job performance

Employees who pursue creative activities outside of work may find that these activities boost their performance on the job, according to a new study by San Francisco State University organizational psychologist Kevin Eschleman ...

#### Last Week's Best—Quantum mechanics breakthrough, 3-D printed human heart, and paraplegia therapy

(Phys.org) —Hello readers—we'd like to try something new here at Phys.org and Medical Xpress: offer a weekly summary every Monday highlighting what we feel are the most important stories of the past ...

#### Smallest speed jump of pulsar caused by billions of superfluid vortices

A team of astronomers, including Danai Antonopoulou and Anna Watts from the University of Amsterdam, has discovered that sudden speed jumps in the rotational velocity of pulsars have a minimum size, and that ...

#### Inhibited children become anxious adults: Examining the causes and effects of early shyness

(Medical Xpress)—Three little girls sit together in a room, playing with the toys surrounding them. One of the girls—"Emma"—has clearly taken charge of the group, and the others happily go along with ...

#### SRI microrobots show fast-building factory approach (w/ video)

(Phys.org) —SRI International, a research center that conducts client-sponsored research and development for government and other organizations, is attracting attention for work on what micro-factories ...

#### Micro-macro entangled 'cat states' could one day test quantum gravity

(Phys.org) —In Schrödinger's famous thought experiment, a cat's quantum state becomes entangled with the quantum state of a decaying nucleus, resulting in the odd situation that the cat is both alive and ...

#### Japan firm offers glowing finger for those phoning home

If you thought a finger that glows when you phone home was strictly the preserve of extra-terrestrials, think again: a Japanese firm has unveiled nails that light up when you make a call.