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: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: (Score:2, Informative)
Given that Sudoku with a generalized base of size N (IE, not necessarily 9 symbols but N symbols in an N^2xN^2 grid with blocks of size N) has been shown to be NP complete since 2002 (http://www-imai.is.s.u-tokyo.ac.jp/~yato/data2/SIGAL87-2.pdf), I find it unlikely that even N=3 sudoku (given how rapidly NP complete problems scale in difficulty relative to a given N) will have any small elegant general solution, as literally speaking, all satisfiability problems up to a certain (small) size can be framed wi
Re:Proof use a lot of brute force (Score:4, Informative)
Re:Proof use a lot of brute force (Score:5, Informative)
Re:Proof use a lot of brute force (Score:5, Interesting)
Re:Proof use a lot of brute force (Score:5, Interesting)
While I am inclined to agree with you, the thing is that there is no a priori reason why such a proof should exist. We should be happy that a proof exists at all.
For some additional perspective on this, here is a very readable article by Chaitin on his Omega number [maths.org]. (Since this is a divulgation article, it may be advisable to read first his short bio at the end, otherwise this may seem crackpottery to some).
Re: (Score:2)
Thanks for that - very interesting.
I still cling to the hope that a purely analytical proof of the four colour theorem exists, since such a thing would be undeniably a thing of beauty, which is, after all, the attraction of mathematics. Just because a combination of Cantor, Godel, Turing and Chaitin's work proves that some things are unprovable doesn't mean we should stop trying, does it?
Re: (Score:1)
Interesting link.
You do realize that GÃdel Incompleteness Theorem is incomplete though, right? =)
Re: (Score:1)
The four color theorem only makes sense in 2 dimensions, since for 3 and more no number of colors is enough. To visualize this, just take any number n of spheres in 3D, add appendices to them so that each sphere touches all the other ones, without intersection, fill-in the voids with whatever you want (by thickening the appe
Re:Proof use a lot of brute force (Score:5, Interesting)
I agree on the final result, but there may be something interesting in the symmetries developed, which the researchers seem to suggest involved some interesting and/or novel techniques. If true, that could have broader applications; reducing seemingly large search spaces to equivalent smaller search spaces by taking advantages of symmetries is a recurring motif in computational X for lots of X, so if they have new techniques there that could be useful.
Willy Wonka's chocolate factory (Score:5, Interesting)
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 [wikipedia.org].
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
Re: (Score:3)
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 think that is how "the coke addict" would phrase it.
Re: (Score:1)
Just sayin'
Re: (Score:2)
Re: (Score:2)
Re: (Score:1)
You are confounding proof and theory. Proofs establish something as true and that is it. What you want is a theory consisting of many theorems that each say something about the Sudoku problem, because then you would feel that you have a better understanding. You are knocking on their accomplishment when you criticize them for not providing a whole theory of the problem. In fact their approach is superior to offering a theory of the problem, because it increases our understanding of computer approaches to pr
Re: (Score:2)
Re: (Score:2)
In related news... (Score:5, Funny)
Re: (Score:1)
Re: (Score:2)
This is not accurate. A binary Sudoku consists of 1x1x1 cells.
Of course it consists of 1x1x1x1 cells.
I prefer my Sudoku with (Score:5, Funny)
After a long day at work I prefer my Sudoku with 80+ clues
Re: (Score:3, Informative)
Somewhat misleading. (Score:5, Insightful)
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: (Score:3)
No. If you first fill in all 81 numbers with a random choice among the valid possibilities and then remove clues in a random order as long as you can do so without making the puzzle ambiguous, then you will usually end up with 24 or 25 numbers where none can be removed without making it ambiguous. That also explains why the ones you usually see have that number of clues.
But there are
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. "
Re:Cue the morons. (Score:5, Informative)
Re: (Score:2)
Like many things, you can always put a lot of negative spin on it and make it sound like the dumbest thing in the world. I got sent an article about "shrimp on a treadmill" that probably came from a Fox News writer - it was neither objective nor balanced, ignoring even mentioning the purpose of the study to hype what it called government waste. Without any objective information about what the goals of the study were or what the researchers were actually studying (it was boiled down to "pollutants"), it is v
Re:Cue the morons. (Score:5, Insightful)
Ready to be sad? (Score:4, Funny)
Well, close: there's a grant program [icr.org]. Seriously.
Re:Cue the morons. (Score:5, Interesting)
Just finished reading the full paper, and they have used some pretty neat tricks to minimise the computation needed.
So they haven't wasted time and money - they have produced a method for reducing the computation time for a whole class of related problems.
Not too bad for an investigation into a brain teaser, IMHO.
Re: (Score:3)
I may invest in nokia right now, it may pay off (it probably wont)
And if you don't invest in nokia, it definitely won't pay off.
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: (Score:2)
Naturally; by no means am I presenting an exhaustive list. In fact, the amount of knowledge you would simply not have today (or the amount of additional work you would have had to have in order to achieve it) had the theory of complex numbers not been developed, is truly amazing :)
Re: (Score:3)
Just so you know, I have no problem with that and in fact I think this is a good way of spending money. I think this is money well spend, and I find it good that the state spends money on this.
Socialism (Score:5, Funny)
There are only two reasons to spend taxpayer money: To defend America, and to get Republicans back into power!
Everything else is SOCIALISM!
Re: (Score:1)
It's not about whining about tax money. It's about ensuring that the tax money that we DO spend, is spent wisely. All too often, this does not occur. As an educated person, surely you are aware of wasteful government spending. Heck, anytime the Pentagon gets its hands on taxpayer money, it's wasteful spending, eh? So there's something you can relate to.
Calling dissenters ignorant is just sh
Re: (Score:3, Insightful)
Re: (Score:1)
We all know they are morons. But I'm sure you will agree with me, that calling them that will never ever in all of time and space of all of the universe make them go "Oh, you're so right, I am such an idiot. I must go smite myself to death right now for being so disgusting!". Right? :D
No, it will only make them angry at you (the reason/logic of this is not the point), worsening the situation. (Don't believe me? That's OK. You should never just believe. Ask him how he feels. ^^)
I found the best way to handle
Re: (Score:1)
Re: (Score:3)
Are we assuming that there was no sort of error checking on the input to begin with?
so can someone place 2 9's in the same row, column or square?
if so you need to check all the non clue squares.(now max of 64)
the proof is simple, take any checking scheme you like, and change the last number checked of a valid sudoku.
If we do have input validation and a full Sudoku we know it's right.
Re: (Score:2)
If you have checked all sub squares, and go on to check the rows and columns, you can omit every third row and column. That's because by checking the squares, you've already made sure that three consecutive squares (which contain the same fields as three consecutive lines) contain each digit three times, and by checking the first two lines you've checked that two of those are in those lines, therefore you already know that the third line contains the third occurrence of each digit, i.e. each digit exactly o
Difficulty (Score:5, Interesting)
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.
Re: (Score:2)
Yeah, I was baffled as to when we started solving Sudoku by 'brute force'. That would be incredibly time consuming.
And if that was how people solved Sudoku, adding a few more blank cells would not actually make them much harder. (Assuming some sort of moderately intelligent brute force that was not literally trying every possible combination...people would hopefully be smart enough to abort each attempt as soon as a conflict arose.)
It's nice to know that you cannot have a Sudoku puzzle with 16 or less clu
Re:Difficulty (Score:4, Interesting)
It's not the solving of the sudoku grid that is being done by "brute force" here, but the enumeration of possible solvable puzzles and the proof that no unique solutions exist for 16 clue puzzles.
It's actually quite instructive to write a sudoku solver - I did so myself a few years back when I decided to learn Python and needed a problem to work on.
There's a little more finesse involved than brute force ;-)
Re: (Score:2)
Well, I've just re-read his comment, and still can't see how I've missed the point.
The research wasn't into solving sudoku puzzles (there is a simple mechanical method to do that, though it does require some guesswork and backtracking in many cases), it was into the possibility of a puzzle with only 16 clues and a unique solution existing.
Maybe you could elucidate for me what the point that I have missed was?
Non-anonymous question (Score:1)
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... (Score:4, Funny)
Besides, I am a word geek, not a math geek. Cruciverbalism is my cup of tea (or letters).
Re: (Score:2, Funny)
It's your cup of.... Alphabet Soup?
Re: (Score:2)
I prefer Sudoku puzzles with only one clue.
I hate people who try to cramp my creative freedom. I only play blank Sudoko.
-
Re: (Score:1)
and you can always solve it the same way.
Reading TFA (Score:2)
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 f
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: (Score:2)
http://arxiv.org/abs/astro-ph/9912202 [arxiv.org] - and I'm sure there's something earlier since when I was doing my phd work (which was before that) it was a common excuse amongst those doing computation work.
Re: (Score:2)
Project proposal: Calculate [Problem]
Needed funding: 3 positions of 8 years each, plus overhead.
Working plan:
The first seven years will be used for waiting for the computers to get fast enough. In the eighth year, we then will actually do the calculation.
Re:What about... (Score:5, Informative)
No - there exist multiple solutions for up to 77 clues (81 -4), where a particular configuration of numbers exists:
1 x x 2 x x x x x
...
2 x x 1 x x x x x
x x x x x x x x x
x x x x x x x x x
x x x x x x x x x
x x x x x x x x x
x x x x x x x x x
x x x x x x x x x
x x x x x x x x x
or
2 x x 1 x x x x x
...
1 x x 2 x x x x x
x x x x x x x x x
x x x x x x x x x
x x x x x x x x x
x x x x x x x x x
x x x x x x x x x
x x x x x x x x x
x x x x x x x x x
(where the x's are the same in each configuration) are two distinct solutions, but the 77 x's are the same clues.
(Sorry - couldn't be bothered to fill the x's in!)
With apologies to Winger.. (Score:2)
This puzzle has only 17, but that's enough clues for me...
Re: (Score:2)
Next you'll be quoting Slaughter or Skid Row
Re: (Score:2)
I've been up all night, got 17 and life to go. :P
PS
IMHO, the better 80s hair/glam metal is at least decent rock music
Millions of hours? (Score:3)
Assuming he had access to 5 supercomputers, this would suggest he ran the program continuously for at least 45+ years. Dedication!
Re: (Score:2)
if those were CPU hours, please calculate for us how long before the Japanese K computer with its 68,544 CPU would reach 5 million CPU hours. hint: less than a week. If that's CPU core hours, divide your result by 8 for the 8 cores each has!
Re: (Score:3)
Re: (Score:2)
Re: (Score:3)
Actually reading the linked article (pretty strange concept to read the article before posting, I agree, but sometimes we behave irrationally)....
Little known fact: According to my calculations, if fewer than 16 slashdotters actually RTFA, there's no guarantee that we're actually commenting on the same article.
I'd post a link to my research, but nobody's going to read it anyway....
17 Clues (Score:2)
That ought to be enough for anyone.
Starting positions (Score:3)
Re: (Score:2)
I got to trying to work that one out for myself a little while ago. I couldn't solve it on my own so I went to the internet for assistance. The solution I found multiplied by some huge prime number at the end, and I could never work out why, so I've shelved that problem for a little while...
Re: (Score:2)
it's not a valid puzzle if it has more than one solution. if it has more than one solution you're playing something other than sudoku.
How many require guessing? (Score:2)
Re: (Score:2)
What is simple guessing?
Maybe the author of this paper should use his supercomputer to find the soduko for the following rules:
* the are at least two possible solutions from the information given in the first clues
* following one of the incorrect clues will not be proved incorrect until the last five figures is about to be filled in.
I ran up on hard sudokus where I had to 'guess' or follow through a faulty solution for 20 steps until it proved itself wrong.
I think this is the trademark for a hard solution i
Programs (Score:2)
"do not" or "may not"? (Score:2)
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?
Re: (Score:1)
So....the hardest sudoku is?!?! (Score:1)
next, try Calcudoku... (Score:1)
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 puzz [calcudoku.org]
Yellow Pigs Strike Again (Score:1)
Re:Well this will solve world hunger. (Score:5, Informative)
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. "
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: (Score:1)
I told her I was ok with her giving me a booty call, but I wasn't taking her out to dinner.
Re: (Score:1)
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.
Re:Well this will solve world hunger. (Score:5, Insightful)
Re:Well this will solve world hunger. (Score:5, Funny)
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: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: (Score:3, Interesting)
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 un
Re: (Score:2)
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 [google.com]
Re: (Score:2)
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 t
Re: (Score:1)
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.