Lower Limit Found For Sudoku Puzzle Clues 121
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."
Proof use a lot of brute force (Score:5, Insightful)
Re:Well this will solve world hunger. (Score:5, Insightful)
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:Proof use a lot of brute force (Score:5, Insightful)
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. (Score:5, Insightful)
Somewhat misleading. (Score:5, Insightful)
Cue the morons. (Score:5, Insightful)
Re:Cue the morons. (Score:5, Insightful)
"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. "
300,000 years (Score:2, Insightful)
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:Cue the morons. (Score:5, Insightful)
Re:Well this will solve world hunger. (Score:5, Insightful)
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:Cue the morons. (Score:5, Insightful)
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:Somewhat misleading. (Score:5, Insightful)
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.
Re:Well this will solve world hunger. (Score:5, Insightful)
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).
Re:Cue the morons. (Score:3, Insightful)
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.