(Press-News.org) For anyone who has ever struggled while attempting to solve a Sudoku puzzle, University of Notre Dame researcher Zoltan Toroczkai and Notre Dame postdoctoral researcher Maria Ercsey-Ravaz are riding to the rescue. They can not only explain why some Sudoku puzzles are harder than others, they have also developed a mathematical algorithm that solves Sudoku puzzles very quickly, without any guessing or backtracking.
Toroczkai and Ravaz of Romania's Babes-Boylai University began studying Sudoku as part of their research into the theory of optimization and computational complexity. They note that most Sudoku enthusiasts use what is known as a "brute force" system to solve problems, combined with a good deal of guessing. Brute force systems essentially deploy all possible combinations of numbers in a Sudoku puzzle until the correct answer is found. While the method is successful, it is also time consuming.
Instead, Toroczkai and Ercsey-Ravaz have proposed a universal analog algorithm which is completely deterministic (no guessing or exhaustive searching) but which always arrives at the correct solution to a problem and does so much quicker.
The researchers also discovered that the time it took to solve a problem with their analog algorithm correlated with the difficulty of the problem as rated by human solvers. This led them to develop a ranking scale for problem or puzzle difficulty. The scale runs from 1 through 4 and it matches up nicely with the "Easy" through "Hard" to "Ultra-Hard" classification currently applied to Sudoku puzzles. A puzzle with a rating of 2 takes, on average, 10 times as long to solve than one with rating of 1. According to this system, the hardest known puzzle so far has a rating of 3.6 and it is not known if there are even harder puzzles out there.
"I had not been interested in Sudoku until we started working on the much more general class of 'Boolean satisfiability problems," Toroczkai said. "Since Sudoku is a part of this class, it seemed like a good testbed for our solver, so I familiarized myself with it. To me, and to a number of researchers studying such problems, a fascinating question is how far can us humans go in solving Sudoku puzzles deterministically, without backtracking, that is without making a choice at random, then seeing where that leads to and if it fails, restarting. Our analog solver is deterministic — there are no random choices or backtracks made during the dynamics."
Toroczkai and Ercsey-Ravasz feel that their analog algorithm can potentially be applied to a wide variety of problems in industry, computer science and computational biology.
The research experience has also made Toroczkai a devotee of Sudoku puzzles.
"Both my wife and I have several Sudoku apps on our iPhones and we must have played thousands of times, racing to get the shortest completion times on all levels," he said. "She often sees combinations of patterns that I completely miss. I have to deduce them. Without paper and pencil to jot down possibilities, it becomes impossible for me to solve many of the puzzles that our solver categorizes as hard or ultra-hard."
Toroczkai's and Ercsey-Ravasv's methodology was first published in the journal Nature Physics and its application to Sudoku, appears in the Oct. 11 edition of the journal Nature Scientific Reports.
### END
Notre Dame researcher helps make Sudoku puzzles less puzzling
2012-10-12
ELSE PRESS RELEASES FROM THIS DATE:
Mug handles could help hot plasma give lower-cost, controllable fusion energy
2012-10-12
Researchers around the world are working on an efficient, reliable way to contain the plasma used in fusion reactors, potentially bringing down the cost of this promising but technically elusive energy source. A new finding from the University of Washington could help contain and stabilize the plasma using as little as 1 percent of the energy required by current methods.
"All of a sudden the current energy goes from being almost too much to almost negligible," said lead author Thomas Jarboe, a UW professor of aeronautics and astronautics. He presents the findings this ...
More than just 'zoning out' -- Exploring the cognitive processes behind mind wandering
2012-10-12
It happens innocently enough: One minute you're sitting at your desk, working on a report, and the next minute you're thinking about how you probably need to do laundry and that you want to try the new restaurant down the street. Mind wandering is a frequent and common occurrence. And while mind wandering in certain situations – in class, for example – can be counterproductive, some research suggests that mind wandering isn't necessarily a bad thing.
New research published in the journals of the Association for Psychological Science explores mind wandering in various ...
Duke Medicine news -- Anti-cancer drug fights immune reaction in some infants with Pompe disease
2012-10-12
DURHAM, N.C. – Adding a third anti-cancer agent to a current drug cocktail appears to have contributed to dramatic improvement in three infants with the most severe form of Pompe disease -- a rare, often-fatal genetic disorder characterized by low or no production of an enzyme crucial to survival.
Duke researchers previously pioneered the development of the first effective treatment for Pompe disease via enzyme replacement therapy (ERT). ERT relies on a manufactured enzyme/protein to act as a substitute for the enzyme known to be lacking in patients with a particular disease. ...
New studies reveal connections between animals' microbial communities and behavior
2012-10-12
Athens, Ga. – New research is revealing surprising connections between animal microbiomes—the communities of microbes that live inside animals' bodies—and animal behavior, according to a paper by University of Georgia ecologist Vanessa O. Ezenwa and her colleagues. The article, just published in the Perspectives section of the journal Science, reviews recent developments in this emerging research area and offers questions for future investigation.
The paper grew out of a National Science Foundation-sponsored workshop on new ways to approach the study of animal behavior. ...
Enzyme triggers cell death in heart attack
2012-10-12
University of Iowa researchers have previously shown that an enzyme called CaM kinase II plays a pivotal role in the death of heart cells following a heart attack or other conditions that damage or stress heart muscle. Loss of beating heart cells is generally permanent and leads to heart failure, a serious, debilitating condition that affects 5.8 million people in the United States.
Now the UI team, led by Mark Anderson, M.D., Ph.D., professor and head of internal medicine at the UI Carver College of Medicine, has honed in on how CaM kinase II triggers heart cell death ...
New treatments for epilepsy, behavioral disorders could result from Wayne State studies
2012-10-12
Three studies conducted as part of Wayne State University's Systems Biology of Epilepsy Project (SBEP) could result in new types of treatment for the disease and, as a bonus, for behavioral disorders as well.
The SBEP started out with funds from the President's Research Enhancement Fund and spanned neurology, neuroscience, genetics and computational biology. It since has been supported by multiple National Institutes of Health-funded grants aimed at identifying the underlying causes of epilepsy, and it is uniquely integrated within the Comprehensive Epilepsy Program at ...
Safety results of intra-arterial stem cell clinical trial for stroke presented
2012-10-12
HOUSTON – (Oct. 11, 2012) – Early results of a Phase II intra-arterial stem cell trial for ischemic stroke showed no adverse events associated with the first 10 patients, allowing investigators to expand the study to a targeted total of 100 patients.
The results were presented today by Sean Savitz, M.D., professor of neurology and director of the Stroke Program at The University of Texas Health Science Center at Houston (UTHealth), at the 8th World Stroke Congress in Brasilia, Brazil.
The trial is the only randomized, double-blind, placebo-controlled intra-arterial clinical ...
Satellite sees 16th Atlantic tropical depression born near Bahamas
2012-10-12
The 16th tropical depression of the Atlantic Ocean season has formed northeast of the Bahamas and NOAA's GOES-14 satellite captured a visible image of the storm as it tracks to the southwest.
NOAA's GOES-14 satellite captured a visible image of newborn Tropical Depression 16 (TD16) near the Bahamas on Oct. 11 at 7:45 a.m. EDT. TD16 appeared as a rounded area of clouds just northeast of the Bahamas and its western fringes were just off the Florida east coast. GOES-14 also showed another low pressure area with the potential for development a few hundred miles from the Windward ...
NASA sees Typhoon Prapiroon doing a 'Sit and Spin' in the Philippine Sea
2012-10-12
As Typhoon Prapiroon slowed down and became quasi-stationary in the Philippine Sea NASA's Terra satellite passed overhead and captured an image of the storm.
NASA's Terra satellite passed over Typhoon Prapiroon on Oct. 11 at 0210 UTC (1010 p.m. EDT, Oct. 10) and the Moderate Resolution Imaging Spectroradiometer (MODIS) instrument captured a visible image of the storm. The visible imagery clearly showed a small ragged eye, and microwave satellite imagery confirmed the eye. Satellite imagery also confirmed a well-defined low-level center of circulation.
By 11 a.m. EDT ...
Nurture trumps nature in study of oral bacteria in human twins, says CU study
2012-10-12
A new long-term study of human twins by University of Colorado Boulder researchers indicates the makeup of the population of bacteria bathing in their saliva is driven more by environmental factors than heritability.
The study compares saliva samples from identical and fraternal twins to see how much "bacterial communities" in saliva vary from mouth to mouth at different points in time, said study leader and CU-Boulder Professor Kenneth Krauter. The twin studies show that the environment, rather than a person's genetic background, is more important in determining the ...