# Discovery could lead to more difficult Sudoku puzzles

##### Feb 13, 2010 by Lisa Zyga

(PhysOrg.com) -- A new analysis of number randomness in Sudoku matrices could lead to the development of more difficult and multi-dimensional Sudoku puzzles. In a recent study, mathematicians have found that the way that numbers are arranged in Sudoku puzzles is even more random than the number arrangements in randomly-generated matrices. The counter-intuitive discovery may enable researchers to develop algorithms that generate Sudoku matrices with fewer clues, making them more difficult to solve.

Mathematicians Paul Newton and Stephen DeSalvo of the University of Southern California in Los Angeles have published the results of their study in a recent issue of the .

"I think it will help develop multi-dimensional Sudoku puzzles, and answer questions about how to give the initial [clues] in order to create a hard, but still solvable Sudoku puzzle," Newton said in an article at ABC Science.

Sudoku is a number puzzle consisting of a 9x9 grid, whose 81 boxes are filled in with the numbers 1 through 9 in a way that meets certain criteria. Each number can only appear once per row and once per column, as well as only once in each of the nine 3x3 sub-grids that make up the .

In 2006, researchers (Felgenhauer and Jarvis) found that there are about 6.67 x 1021 different Sudoku matrices that satisfy these three criteria. In contrast, the total number of different 9x9 randomly generated matrices is much greater: 981. The ratio of these two numbers, or the of randomly generating a Sudoku matrix by randomly selecting each number in each box independently, is very small: about 3 x 10-56. This small probability results from the constraints put on Sudoku matrices.

In their study, Newton and DeSalvo wanted to find out how exactly random a Sudoku matrix is, given these constraints. To answer this question, they generated a representative sample of about 10,000 matrices and compared them to randomly generated matrices. They were surprised to find that Sudoku matrices are actually more random than randomly-generated matrices. This result is counterintuitive since you would expect that, the more constraints on a matrix, the less random it will be.

Instead, the rules of Sudoku seem to “weed out” matrices with patterns. For example, as Newton explained, a randomly generated matrix could potentially consist of all one number, alternating numbers, or some other pattern not allowed in Sudoku. The imposed high level of number distribution in Sudoku gives it a higher level of entropy, making it more random than random matrices.

Newton and DeSalvo predict that this greater understanding of Sudoku could lead to better Sudoku-generating algorithms that create more difficult puzzles. Currently, Sudoku puzzles require at least 17 numbers to be given in their correct boxes in order for the puzzle solver to find a unique solution. The new study could decrease that , making it more difficult to solve the puzzles. Future algorithms might also develop more complex 3D Sudoku cubes.

"I think it will give people a lot of insight into how to produce better algorithms for constructing Sudoku matrices and it will enable ultimately the very fast learning algorithms that solve Sudoku matrices," Newton said.

Australian mathematician Marcel Jackson of Latrobe University in Melbourne, who was not affiliated with the study, added that understanding Sudoku matrices better might also be useful in coding information to minimize the effect of errors in transmission.

Explore further: Strong teams attract crowds for international cricket

-- Paul K. Newton and Stephen A. DeSalvo. “The Shannon entropy of Sudoku matrices.” Proceedings of the Royal Society A. doi: 10.1098/rspa.2009.0522.
-- Via: ABC Science

## Related Stories

#### Toy Robot to Solve Sudoku (w/ Video)

Sep 03, 2009

(PhysOrg.com) -- A Swedish programmer, Hans Andersson, has used a Lego Mindstorms NXT kit to develop a robot to solve Sudoku puzzles.

#### Physicist's algorithm simplifies biological imaging -- and also solves Sudoku puzzles

Mar 02, 2006

Cornell physicist Veit Elser has been engrossed recently in resolving a pivotal question in biological imaging. So he hasn't had much time for brainteasers and number games.

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

#### Scientists harness logic of 'Sudoku' math puzzle to vastly enhance genome-sequencing capability

Jun 24, 2009

A math-based game that has taken the world by storm with its ability to delight and puzzle may now be poised to revolutionize the fast-changing world of genome sequencing and the field of medical genetics, suggests a new ...

#### An easy way to find a needle in a haystack by removing the haystack

Jun 18, 2009

Researchers at the Max Planck Institute for Chemical Ecology in Jena and their colleagues from the Czech Academy of Sciences in Prague have developed a new method to quickly and reliably detect metabolites, ...

#### 5 ways to strengthen your brain

Aug 20, 2009

You're lifting those barbells for strong muscles. You're walking around the block or running marathons or doing 1,000 jumping jacks every day for a stronger heart.

## Recommended for you

#### Strong teams attract crowds for international cricket

Mar 06, 2014

The strength of the team—not the promise of a close contest—is the biggest draw to crowds in international cricket, new research has found.

#### Improving radiation therapies for cancer mathematically

Mar 05, 2014

In a paper published in December in the SIAM Journal on Scientific Computing, authors Li-Tien Cheng, Bin Dong, Chunhua Men, Xun Jia, and Steve Jiang propose a method to optimize radiation therapy treatments in cancer patien ...

#### Computational study finds maximum packing density of 55,000 different shapes

Mar 05, 2014

A team of researchers at the University of Michigan has used computational and analytical analysis to find the maximum packing density of 55,000 uniquely shaped particles. In their paper published in the ...

#### Secret to the perfect pancake is discovered

Mar 04, 2014

In a collaboration with Meadowhall Shopping Centre, students from the University's Maths Society (SUMS) developed, trialled and tested a formula which enables pancake-lovers across the world to rustle-up ...

#### New data shows baseball managers when to replace the starting pitcher

Feb 28, 2014

Last October, the Detroit Tigers won the first game of the American League Championship Series against the Boston Red Sox; the Tigers led the second game, 5-1, going into the eighth inning in Boston's Fenway ...

##### Quantum_Conundrum
2 / 5 (8) Feb 12, 2010
I disagree with this finding.

It cannot be more random than "random", because in a "random" matrix there is NO pattern, there might appear to be a pattern, but in reality even that is an illusion.

In Sudoku, there is ALWAYS a pattern, and by rule/definition, there must be a pattern.

In a "random" matrix, all 1s is NOT a "pattern"...it is just all 1s, period...
##### antialias_physorg
1.3 / 5 (4) Feb 12, 2010
I think this "more random than in random generated matrixes" is a bit misleading.

Numbers in Sudoku matrices tend to be very evemly distributed (this is a direct result from the way the rules are formulated). So a sudoku matrix is closer to the mean (on average) than a purely random matrix.
##### jamey
2 / 5 (4) Feb 12, 2010
Oh, I *HOPE* this is a case of mathematics->journalism mistranslation! In a truly random matrix, determining any particular cell gives you *NO* information on what's in other cells. Whereas in a Sudoku, each cell you know gives you more and more information on the others. In the degenerate case, knowledge of four cells can completely specify a fifth cell, even if *NOTHING* is known of any other cell in the grid. Soo... seriously, "more random than random" is just crazy talk!
##### mklnk
4.4 / 5 (7) Feb 12, 2010
I believe this is a case of scientific language being dumbed down into journalistic language and losing some of its meaning in the translation. When the article says that the Sudoku puzzle is more random, I believe it means that there is a smaller chance of repeated patterns in the sudoku puzzle when the digits are read as a string.

"The imposed high level of number distribution in Sudoku gives it a higher level of entropy..." should give you an idea of what they're trying to tell us.

What they're saying is that 10,000 randomly generated sudoku puzzles have, on average, fewer repeating patterns, and therefor a higher degree of entropy than would 10,000 random 9x9 grids of digits. A grid of 81 1s, for example, might possibly be RANDOMLY GENERATED, but is much less RANDOM than a sudoku puzzle which in turn is less random than a grid of 81 unique symbols given in no particular order.
##### stealthc
4.5 / 5 (2) Feb 12, 2010
why not use a transforming 3d sudoku matrix to perform encryption? The fact that the columns add up, and that rows add up, and boxes add up, you should be-able to use this to obscure the original data pretty good, and I'd suspect the amount of bits that could be used to represent such a matrix would definitely be more than current bit width and the key would look like a harmless sudoku puzzle.
##### fourthrocker
3 / 5 (4) Feb 13, 2010
I agree with some of the posts here. A Sudoku matrix is by definition a better random distribution of numbers because of the constraints on the duplication of numbers in small areas of the overall matrix as well as the overall matrix which results in an equal qty of each number. A truly random generated distribution could be all 1's if you use a number generator or even throw dice, but it isn't a random distribution of all numbers. This study sounds totally intuitive to me, not counter-intuitive, at least from what's in the article.
##### antialias
4.3 / 5 (6) Feb 13, 2010
Case in point: A sudoku puzzle will always have the same number of 0's, 1's, 2's ... 9's

A purely random matrix might not (and in all probability will not) have such an even distribution of numbers.

So a sudoku puzzle will always have the maximal possible entropyn whereas a randomly generated matrix will likel have a lower entropy.
##### farside
3 / 5 (2) Feb 13, 2010
In physics entropy is defined as the number of assessable states for a system. A system with 9^81 possible states has a much greater entropy than one with only 6.67x 10^21.
##### ReeseJ2
5 / 5 (1) Feb 13, 2010
I agree with mklnk. This is certainly a mistranslation from math-speak to normal-speak. I suspect that what is actually meant is that the arrangement of numbers WITHIN each Sudoku matrix is more random than within the AVERAGE unconstrained matrix. A simple example is this: If you know everything about, say, a 9x9 matrix consisting of all 1's, and I ask you "A certain square has a 1 in it. What is the number directly to the left of that square?" you can answer very very easily. On the other hand, if you know exactly what the arrangement of numbers in a Sudoku matrix is, and I ask you the same question, you're going to have a very hard time answering. Your answer will probably be something like "Well, it might be a 2... or a 3... or a 5, 6, 7, 8, or 9."
##### Vikstar
5 / 5 (1) Feb 14, 2010
If anyone is interested in first reading the publication, it is available for free from http://rspa.royal...hing.org just search for sudoku.
##### billyswong
not rated yet Feb 15, 2010
The article should discuss more on what entropy is than trying to over-simplify things as 'more random than random'.

## More news stories

#### Service is key to winery sales

To buy, or not to buy? That is the question for the more than 5 million annual visitors to New York's wineries. Cornell University researchers found that customer service is the most important factor in boosting tasting room ...

#### Statue of Egypt pharoanic princess found in Luxor

(AP)—Egypt has announced that a team of European archaeologists have found a nearly 2-meter- (6 ½-foot-) tall alabaster statue of a pharoanic princess, dating from approximately 1350 B.C., outside the ...

#### Lose yourself to dance, know yourself better

Could managers gain a new kind of understanding about their interaction with colleagues and employees by 'dancing'? That's the question arising from new research published this month in the International Journal of Work Or ...

A second viewing in a police line-up may help more eyewitnesses identify the culprit, new research from Flinders University reveals.

#### Expiration of terrorism risk insurance act could hurt national security, study finds

Allowing the federal terrorism risk insurance act to expire could have negative consequences for U.S. national security, according to a new study from the RAND Corporation.

#### WISE survey finds thousands of new stars, but no 'Planet X'

(Phys.org) —After searching hundreds of millions of objects across our sky, NASA's Wide-Field Infrared Survey Explorer (WISE) has turned up no evidence of the hypothesized celestial body in our solar system ...

#### Ever-so-slight delay improves decision-making accuracy

Columbia University Medical Center (CUMC) researchers have found that decision-making accuracy can be improved by postponing the onset of a decision by a mere fraction of a second. The results could further our understanding ...

#### The dark side of fair play

We often think of playing fair as an altruistic behavior. We're sacrificing our own potential gain to give others what they deserve. What could be more selfless than that? But new research from Northeastern University assistant ...

#### Researchers claim Mojave Crater on Mars is source of Mars rocks found on Earth

(Phys.org) —A trio of researchers, two from France and one from Norway, has published a paper in the journal Science where they claim to have found sufficient evidence to identify a specific crater on Mar ...

#### Microbial detection array detects plague in ancient human remains

(Phys.org) —Scientists who study past pandemics, such as the 14th century Black Death that devastated much of Europe, might soon be turning to an innovative biological detection technology for some extra ...