Lower Limit Found For Sudoku Puzzle Clues

ananyo writes "An Irish mathematician has used a complex algorithm and millions of hours of supercomputing time to solve an important open problem in the mathematics of Sudoku, the game popularized in Japan that involves filling in a 9X9 grid of squares with the numbers 1–9 according to certain rules. Gary McGuire of University College Dublin shows in a proof posted online [PDF] that the minimum number of clues — or starting digits — needed to complete a puzzle is 17; puzzles with 16 or fewer clues do not have a unique solution. Most newspaper puzzles have around 25 clues, with the difficulty of the puzzle decreasing as more clues are given."

Comments

Proof use a lot of brute force

[JoshuaZ]

This isn't a proof that really gives us any understanding of the problem. They used various symmetries of the problem to reduce how many cases they'd need to check and then checked it for all cases using a lot computing power (without reducing the cases there are around 10^33 separate cases to check (since 81 choose 17 is around 10^17 and 9^17 is around 10^16) .So they did due some good work in reducing the case set, but they still had a lot left over. A result of this brute force approach this means that there's no obvious way to generalize this proof to get the minimum number needed when one has n^2 symbols in general. Proofs really should give us insight into why statements are true, and this one really doesn't. That's not to knock on the accomplishment: this clearly took a lot of effort, some very smart work, and some clever use of group theory and very skilled programming.

Re:Proof use a lot of brute force

[Anonymous Coward]

This is true.

But you dismiss the fact that hard proofs are often done gradually: it's usually easier to prove something you know beforehand than take a stab at the dark.

What I mean is, now that this brute force approach has shown that 9^2 requires at least 17 to get a general solution, then we can now go on to prove it using standard methods.

Re:Well this will solve world hunger.

[Linsaran]

Hey his salary is at least as justifiable an expense as a tabloid magazine editor's. They're both providing a service that is related to an entertainment medium. Granted it's a wildly different demographic of people who are entertained by SuDoKu vs who care about who Katy Perry happens to be dating, but in the grand scheme of society I don't think it's any less justifiable.

Of course then there's the arguement that all entertainment is extraneous to society, which I also disagree with (but that's another can of worms entirely).

Re:Well this will solve world hunger.

[walkerp1]

Yes, scientific advances, mathematical, sociological or otherwise, might very well prove to be the building blocks for a solution.

Somewhat misleading.

[drfuchs]

But that does not mean that in all puzzles with more than 17 clues you can remove a clue and still have a unique solution. This makes the last sentence in the main post kind of meaningless; plenty of (x+1)-clue puzzles are harder than some x-clue ones.

Re:Somewhat misleading.

[Anonymous Coward]

No, they proved that there are no puzzles with 16 clues that have a unique solution. There are plenty of puzzles with more clues that don't have a unique solution. e.g. a sudoku with columns 8 and 9 missing. So removing a clue from a 55 clue puzzle could lead to a puzzle with no unique solution.

Cue the morons.

[Beelzebud]

I see we already have one idiot asking "what's the point", much like John McCain or Sarah Palin asking why we need to research the fruit fly genome, or put money into a planetarium. This is news for nerds. If you want to whine about tax money, and don't understand why fundamental research is important, then find some place else to stink up with your ignorance.

Re:Cue the morons.

[Beelzebud]

RTFA, if it's not too much of a fucking brain teaser for you. There is a little nugget at the end.

"McGuire says that his approach may pay off in other ways. The hitting-set idea that he developed for the proof has been used in papers on gene-sequencing analysis and cellular networks, and he looks forward to seeing if his algorithm can be usefully adapted by other researchers. “Hopefully this will stimulate more interest,” he says. "

Re:Cue the morons.

[Beelzebud]

If only there were a medal for those being most proud of their own ignorance.

Re:Cue the morons.

[doshell]

In the seventeenth century, Pierre de Fermat and Blaise Pascal spent quite a good time reasoning about "fucking brain teasers". The eventual outcome of this work was the theory of probabilities, without which much of today's knowledge in engineering, economics, biology and countless other fields would be pretty much impossible.

Also around the seventeenth century, other people who were also fond of "fucking brain teasers" wondered what could happen if one assumed some numerical quantity to exist whose square was -1. The eventual outcome was the theory of complex numbers, without which, arguably, modern quantum mechanics would never have been developed. Quantum mechanics itself, at the time of its discovery in the early twentieth century, was pretty much useless in practical terms; but modern electronics would have been impossible without it.

One could also mention the whole plethora of "fucking brain teasers" that led to the discovery of group theory, a branch of mathematics dating to the late nineteenth century. Without it, modern cryptography would not exist at all.

These stories are meant to illustrate that your ignorant comment fails to recognize the potential long-term consequences of discoveries that have no short-term practical outcome. And that's assuming practical outcomes are all that matter; in past times we used to think that "knowledge for knowledge's sake" was a motto to live by. People who think like you (and there are unfortunately a lot of them in positions where they can influence public policy) are ultimately setting back the scientific and technological progress of mankind.

Re:Cue the morons.

[AK Marc]

The simple fact of the matter is that, unless deliberately sabotaged by politicians trying to make a point, the US could completely abandon the US military and still have a military force strong enough to fight off any and all prospective attackers. That is, abolish the standing US military, let the infrastructure and planes rot for 10-15 years, then have China try to invade. Unless politicians purposefully bungled the response to prove a point (and they've done it in the past). China might be able to take an uninhabited Aleutian island, but would be unable to land a significant force on the west coast, and if they did try, the civilian population is sufficiently armed as to repel them. There are no credible threats in the world that the US couldn't repel. We have a standing army large enough to win a war if every other country on the planet tried their best to invade. That seems a little silly. In North American vs the rest of the world, there's no country that the US couldn't level to the point they had no standing buildings older than a few hours, no matter where in the world, and no matter what counter-attacks were being waged at the same time. As long as Mexico and Canada weren't massive staging grounds against the USA, the USA could project enough might to destroy anything (or everything, given enough time), even if the rest of the world was focused on the sole goal of destroying Washington D.C., which they'd be unable to do.

When you think about it, it's insane the level of conventional military might the US can casually deploy. And it costs trillions. Wouldn't it be cheaper to buy an occasional dinner and save on the tanks and planes? Diplomacy is favored by the Republicans because they have a habit of having friends and family in the defense industry, and they also tend to vomit on world leaders.

300,000 years

[Anonymous Coward]

From the paper: ". . . the paper estimates that our original version would take over 300,000 years on
one computer to finish this project."

Assuming Moore's law continues, it would take about 28 years, but you would have to wait 27 years to buy the computer.

Re:Well this will solve world hunger.

[NFN_NLN]

Well this will solve world hunger.

The problem of world hunger has been solved multiple times already. The real problem is, every time we are able to increase food production, it results in a short term increase in the standard of living. Which is immediately followed by uncontrolled population growth and then back to square one.

1. Discovery the the New World
John Cabot - The fish were very plentiful and he would send word to King Henry VII that they would no longer need to fish in common waters as there was enough cod fish to feed England for an eternity.

2. Introduction of chemically produced fertilizers
Inorganic fertilizer use has also significantly supported global population growth — it has been estimated that almost half the people on the Earth are currently fed as a result of synthetic nitrogen fertilizer use.[4]

3. Genetically modified crops
During the mid-20th century, Borlaug led the introduction of these high-yielding varieties combined with modern agricultural production techniques to Mexico, Pakistan, and India. As a result, Mexico became a net exporter of wheat by 1963. Between 1965 and 1970, wheat yields nearly doubled in Pakistan and India, greatly improving the food security in those nations.[4] These collective increases in yield have been labeled the Green Revolution, and Borlaug is often credited with saving over a billion people worldwide from starvation.[5]

Re:Well this will solve world hunger.

[AK Marc]

The real problem is, every time we are able to increase food production, it results in a short term increase in the standard of living. Which is immediately followed by uncontrolled population growth and then back to square one.

On a global scale, it's never been fixed. There have always been areas where food was scarce. "World hunger" is not a problem of production, but logistics, and has *never* been solved. Uncontrolled population growth happened only in the sense that one of the controls was eliminated, people lived. But if you look at fertility rates, often such advances are linked with decreased population growth rate (though something like a war will decrease the population while increasing population growth rate, so the terms don't always mean what people take them to mean).