Slashdot Mirror
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."
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.
Don't trouble yourself to read to the bottom of the story....
"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. "
High-tech computers, working uninterruptedly for about 10 years, have finally discovered the exact minimum number of clues for the binary sudoku.
After a long day at work I prefer my Sudoku with 80+ clues
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).
In a bit of shameless internet panhandling, I accept Litecoin Donations at Lbd2oH9QsthD1GfuUXPyka12YxvWJYnBVf
Yes, scientific advances, mathematical, sociological or otherwise, might very well prove to be the building blocks for a solution.
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.
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.
I have a question which is somewhat related here and about which I have always wondered:
How much of a sudoku, once filled in, must be "checked" in order to be certain that the whole thing is correct?
Most newspaper puzzles have around 25 clues, with the difficulty of the puzzle decreasing as more clues are given.
That's not necessarily true. The difficulty is really determined by the algorithms required to solve the puzzle. For example, X-Wing, Swordfish, chaining, etc, are all advanced techniques. Those are really only used when they have to be - no simpler methods remain to identify a correct play. It can become very tedious poring over the pencil marks trying to identify which algorithms can be exploited, and therein lies the difficulty. Even if a puzzle has a lot of clues, if the gameplay hinges on the use of a single advanced algorithm along the way then the puzzle would be advanced.
Personally, I like to play at easier levels for pure speed, with a good time being well under 60 seconds.
Better known as 318230.
Sorry for the double-post, but I got signed out somehow:
I have a question which is somewhat related here and about which I have always wondered:
How much of a sudoku, once filled in, must be "checked" in order to be certain that the whole thing is correct?
I prefer Sudoku puzzles with only one clue. That way I can finish them any damn way I want. Multiple solutions are my friend.
Besides, I am a word geek, not a math geek. Cruciverbalism is my cup of tea (or letters).
Silence is a state of mime.
Reading TFA (I know, I know)...
look at a completed Sudoku puzzle and figure out the the minimum clues needed to make the puzzle solvable in one particular way.
17-clue puzzles have been observed (although not all the time). 16-clue puzzles haven't, and he came up with theoretical backing for that. Science!
brute-forcing would take too long, so they modified a piece of open source software to check possibilities in less time. (they still had to use a supercomputer)
they can eliminate setups that are identical for the purposes of this analysis.
The "Hitting Set Problem" isn't just an issue in Sudoku
I listen to both RIAA and non-RIAA stuff if I like the music, tangential business/politics nonwithstanding.
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.
16 clues will always generate puzzles with multiple solutions.
Does this also mean that any puzzle with 17 clues has exactly one solution?
This puzzle has only 17, but that's enough clues for me...
I listen to both RIAA and non-RIAA stuff if I like the music, tangential business/politics nonwithstanding.
People with more education than you do, apparently.
Assuming he had access to 5 supercomputers, this would suggest he ran the program continuously for at least 45+ years. Dedication!
There are only two reasons to spend taxpayer money: To defend America, and to get Republicans back into power!
Everything else is SOCIALISM!
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]
That ought to be enough for anyone.
I have always wondered how many starting Soduko puzzles there are that have a unique solution.
The minimum number of clues for the solution to be complete != the minimum number of clues to solve the puzzle.
Proof: I give you 0 clues
Then any valid solution to any puzzle of the same dimensions as my puzzle is a valid solution to my puzzle.
QED
So difficulty is only greater when there are the fewest given numbers and a unique solution. I always wondered why the ones that were mostly filled in seemed just as easy as the ones with almost none. Perhaps the ones I was doing had less than 17 and thus, no unique solution, making them easier in a way?
Now, could we perhaps put that supercomputer back to computing something relevant to widespread disease, world hunger, or solving the global stupidity+laziness=global warming problem?
This comment reminds me that it's not what you have, it's what you do with it. Sometimes you hear about an athlete that he or she has "an extra gear" in the heat of battle. I went to school with a lot of smart people. The median smart person would sometimes make a lazy statement of sentiment such as this one that would never have passed the lips of my classmates with the hard-baked intellectual edge. Hard-baked was part talent, but mostly attitude: people who just thought that the lazy use of "should" was beneath their level of intellectual determination (as it should be, in my personal opinion).
Obviously the landmark results in mathematics are the ones which forge a deep connection between branches of mathematics formerly distinct. Every proof should be one of those. Or at least that's how the coke addict would phrase it. Mathematics as Willy Wonka's chocolate factory. Who needs peas? No candy cane construction permitted by the Chocolate Port Authority if less intriguing that Dessin d'enfant.
I arrived at this page yesterday evening beginning my tour with a question about the provability of reachable states, the mechanism of temporal logic, Zermelo's contribution to set theory, the Hilbert epsilon operator, the Bourbaki group (before Sheldon Cooper there was Jean Dieudonne), and finally to Grothendieck. I have a fairly clear recollection of reading a long piece about Grothendieck several years ago which lamented the loss to mathematics when he devoted the bulk of his career to elaborating a program in algebraic geometry instead of cracking one hard problem after another, which it seemed some people thought he could do. He was regarded by some as much too brilliant for the pedestrian task of assembling an overarching synthesis.
All mathematicians should be more like Grothendieck should have been. Doesn't that sentiment become quickly cloying once you engage the mental clutch?
A year ago another tour took me to Knuth's algorithm of dancing links, which I compiled out of curiosity, then modified the decision step with the next most obvious heuristic. I was interested to watch the famous dancing links during a back-tracking step, so I searched the internet for a famously hard Sudoku example, found one, then single-stepped through the solution process in the debugger. I was disappointed: it reached solution without once backtracking. I think it made three guesses in total, either binary or trinary. I vaguely recall the odds of it guessing correctly all the way to solution was about ten to one. I loaded some other hard problems. On these it actually backtracked from time to time, but not as often I would have presumed. Even hard problems fall quickly to structured guess-work. It's only when you map Sudoku into a logic inference framework that hard problems are hard.
In the Kolmo
Sudoku's, like so much other puzzles, are basically equivalent with solving Exact Cover problems. There are two types of Exact Cover problems that have a unique solution, those that can be solved with simple elimination and those that cannot. Simple elimination means that you take two columns in the Exact Cover problem and see if there is an implication. If this is the case, the rows that have only one 1 in the two columns involved, can be removed and the two columns can be joined. This simple elimination rule proves to be quite powerful to solve Exact Cover problems with a unique solution. It is rather difficult to construct a Exact Cover problem with a single solution that cannot be solved with this elimination rule. But I guess with so less clues that there might be many Sudoku's that cannot be solved with simple logic implication, but do require some form of guessing.
Well, close: there's a grant program. Seriously.
Space game using normal deck of cards: http://BattleCards.org
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).
Learn to love Alaska
What I mean more exactly, is to use a program (like this one) that transforms a Sudoku into an Exact Cover problem, and next try to use an elimination program (like this one) to find a solution. See also this blog entry for some more information.
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
You got it backwards: a higher standard of living is followed by a decrease in population growth. E.g. European countries generally have high standards of living and they have small or even negative population growth. Compare that to poor countries.
Hunger is mostly an economic problem, not of lack of wealth but extremely unfair distribution. World hunger will only be fixed when people in poor countries have the opportunity to work and be not-so-unfairly compensated (and only giving them food doesn't work unless you have a limitless supply of food). How to do that is left as an exercise for the reader.
Well, humanity deserves what it gets when it conceives "put fish in a boat and carry them 3000 miles across the ocean" as an idea worth trying.
Is this a hard-and-firm limit? The article implies that 16 is a hard limit. 16 or fewer clues GUARANTEES multiple possible solutions, and 17 or greater GUARANTEES only one possible solution.
Yet other commenters here show that puzzles with far more than 17 clues can have multiple possible solutions. So does this mean 16 is a hard "low" limit? That there is not one single 16-clue puzzle possible that only has one possible solution?
Another non-functioning site was "uncertainty.microsoft.com."
The purpose of that site was not known.
I told her I was ok with her giving me a booty call, but I wasn't taking her out to dinner.
So this lower bound is exact.
Dude, give her right number next time. I don't appreciate when people I don't know call me in the middle of the night.
So lame. This guy sends supercomputers into years of churning to find the hardest puzzle, and he doesn't give it up? C'mon man.
You got it backwards: a higher standard of living is followed by a decrease in population growth. E.g. European countries generally have high standards of living and they have small or even negative population growth. Compare that to poor countries.
Exactly.
All of the countries in the world are on the same path, and the societies are homogenizing - http://www.google.com/publicdata/directory
Now the mathematicians are done with Sudoku, start working on Calcudoku (which is like killer Sudoku, but with more operators and no restriction on puzzle size):
For example puzzles, see online Calcudoku puzzles.
http://it.slashdot.org/comments.pl?sid=2603836&cid=38589290
Yeah, that thing is a big nightmare for many mathematicians out there, as well as many philosophers. But you need a solid background in philosophy and psicology to even understand why it is such a big deal to some.
Engineers and physicists don't give a damn, we *already* work every day in an imperfect world that surprises us at every corner, using extremely solid math as the ultimate tool, but not as The Truth. It is just a viewglass, and while it is the best we have by far, it is always going to be imperfect.
While industrialized nations do have a dropping population growth rate, they have an increasing energy consumption growth rate.
It is unlikely, bordering on impossible, that 100% of the planet can be sustained at a high enough standard of living to completely eliminate poverty and hunger worldwide, simply because we cannot safely generate that kind of energy output. At least, not in a sustainable manner.
The argument that the population will level off instead of crashing horribly does not seem to hold up in the face of more factors than just food supply. Socioeconomic factors, such as the availability of inexpensive goods, are heavily dependant upon either the exploitation of socioeconomic inequality (china, and pals), or the ubiquity of cheap energy and resources (the US, through onerous trade relations that maintain these features, again exploiting socioeconomic inequalities.)
Solving world hunger would imply either 1 of 2 things.
1) world populations plunge to locally sustainable levels following a global catastrophe, natural or otherwise. Traditonal energy and food sources become reasonable means to satisfy world hunger at these levels.
2) the world economy stops trying to exploit local disadvantages of disparate populations, and the human race produces a new, reliable, and abundant energy source that can safely sustain the inflated world population, and maintain the high standard of living which promotes the low growth rate on a global scale.
Occam's razor suggests the former will happen. It has happened before many times in human history, (fammine has decimated populations long before recorded history, as have wars, and even economic collapses) while the latter has yet to ever happen, and requires far more complications to occur.
The second option requires that growth rate reach exactly 0. Otherwise the world population will continue to grow, and outstrip its ability to be sustained. This is an unfortunate truth which comes from understanding what purpetual growth means. This fundementally goes against human nature. People will chafe under any imposed restraints to procreation. (Look at china.)
I conjecture that our species is fundementally incapable of sustained, zero growth utopian living, short of species wide sterilization and depdenance on assisted reproduction exclusively. At which point, many people would claim it is a distopia, and not a utopia.
For what it's worth, my money is on the first one happening. We see signs of a looming global economic collapse right now. We are hopelessly dependant on an energy source that degrades the habitability of our biosphere while simultaneously increasing rate of consumption for such energy per person, and also the total number of persons consuming at steady and alarming rates. At the current rate of progress for sustainable nuclear/fusion energy replacing fossil fuels, we will reach economic and biosphere collapse long before we reach the hypothetical utopia.
I don't delude myself by donning rose colored glasses when it comes to this issue. I don't look aside from what is going to happen, just because the overextended population is h. sapiens. The human race is ripe for radical decline from resource depletion.
Here's my prediction for how it will go down:
We reached peak oil sometime in the last decade. Peak oil means peak energy production; the maximum on the curve plot over time. We are riding the production slope down now. We are showing only token interest in getting off that sinking ship. Demand for energy continues to grow. As a result, energy production companies are becoming more and more desperate/wreckless to supply that energy. This is how deepwater horizon and the recent stint of induced earthquakes due to hydrofracturing came about.
The world economy is hopelssly tied to energy prices. As supply drops, and demand increases, the costs of transportation of goods between nations, and even major cities will become so high that the goods delivered must be priced accordingly.
Once again, the number 17 appears.
Who pays your salary to flip burgers all day? You don't solve world hunger serving fast food to people who could go without eating for weeks due to build up.