×

Welcome to the Slashdot Beta site -- learn more here. Use the link in the footer or click here to return to the Classic version of Slashdot.

Thank you!

Before you choose to head back to the Classic look of the site, we'd appreciate it if you share your thoughts on the Beta; your feedback is what drives our ongoing development.

Beta is different and we value you taking the time to try it out. Please take a look at the changes we've made in Beta and  learn more about it. Thanks for reading, and for making the site better!

Lower Limit Found For Sudoku Puzzle Clues

timothy posted more than 2 years ago | from the 17-ain't-young dept.

Japan 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."

cancel ×
This is a preview of your comment

No Comment Title Entered

Anonymous Coward 1 minute ago

No Comment Entered

121 comments

Well this will solve world hunger. (-1)

Anonymous Coward | more than 2 years ago | (#38630876)

Seriously, who pays these motherfuckers' salaries????

Re:Well this will solve world hunger. (5, Informative)

Malk-a-mite (134774) | more than 2 years ago | (#38630906)

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. (5, Insightful)

Linsaran (728833) | more than 2 years ago | (#38630942)

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. (-1, Offtopic)

Anonymous Coward | more than 2 years ago | (#38632504)

Duh, Katy Perry isn't dating anyone. Russell only filed for divorce a week ago.

Re:Well this will solve world hunger. (1)

Anonymous Coward | more than 2 years ago | (#38633578)

I told her I was ok with her giving me a booty call, but I wasn't taking her out to dinner.

Re:Well this will solve world hunger. (1)

Anonymous Coward | more than 2 years ago | (#38633768)

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. (5, Insightful)

walkerp1 (523460) | more than 2 years ago | (#38630968)

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

Re:Well this will solve world hunger. (5, Insightful)

NFN_NLN (633283) | more than 2 years ago | (#38631366)

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. (4, Insightful)

AK Marc (707885) | more than 2 years ago | (#38632212)

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:Well this will solve world hunger. (3, Interesting)

Anonymous Coward | more than 2 years ago | (#38632680)

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.

Re:Well this will solve world hunger. (1)

jovius (974690) | more than 2 years ago | (#38635360)

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:Well this will solve world hunger. (0)

Anonymous Coward | more than 2 years ago | (#38632982)

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.

Re:Well this will solve world hunger. (-1, Offtopic)

Anonymous Coward | more than 2 years ago | (#38632920)

I wouldn't solve world hunger even if I knew how. This, on the other hand, is interesting. Fuck you.

Proof use a lot of brute force (5, Insightful)

JoshuaZ (1134087) | more than 2 years ago | (#38630904)

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 (5, Insightful)

Anonymous Coward | more than 2 years ago | (#38630956)

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:Proof use a lot of brute force (2, Informative)

Anonymous Coward | more than 2 years ago | (#38631764)

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 within it. It is possible, but IMHO highly unlikely.

Re:Proof use a lot of brute force (3, Informative)

JoshuaZ (1134087) | more than 2 years ago | (#38631848)

This doesn't follow. The question here isn't the general question of solving a generalized Sudoku grid (which is NP complete) but rather the problem of the minimum size needed for a unique solution. This isn't the same problem. It could very well be that there's an easy answer to this question and that the numbers follow some easy pattern (like say 2n-1 for n symbols).

Re:Proof use a lot of brute force (4, Informative)

JoshuaZ (1134087) | more than 2 years ago | (#38630958)

Er, I made a mistake here. One just needs to check this for 16 clues, so 81 choose 16, and 9^16 are the numbers one cases about, so one gets around 10^30. The other important thing to note is that this is the set of possible clue arrangements. Not all of these lead to valid sudokus at all. There are only around 10^21 of those.

Re:Proof use a lot of brute force (4, Interesting)

The Askylist (2488908) | more than 2 years ago | (#38631082)

Pretty much like the proof of the four colour theorem, then. A really good proof would be able to show a solution for n dimensions, where n > 2, but all we have as a proof is an exhaustive enumeration of the possible networks in 2 dimensions. Most unsatisfying, to those of us who like to see analytical proofs that don't rely on mechanical methods, but there you go. It's still a clever bit of work, and the technique may come in useful elsewhere, but I'd rather see a pencil and paper proof any day.

Re:Proof use a lot of brute force (5, Interesting)

rmstar (114746) | more than 2 years ago | (#38631524)

A really good proof would be able to show a solution for n dimensions, where n > 2, but all we have as a proof is an exhaustive enumeration of the possible networks in 2 dimensions. Most unsatisfying, to those of us who like to see analytical proofs that don't rely on mechanical methods.

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:Proof use a lot of brute force (1)

The Askylist (2488908) | more than 2 years ago | (#38632300)

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:Proof use a lot of brute force (0)

UnknownSoldier (67820) | more than 2 years ago | (#38632876)

Interesting link.

You do realize that GÃdel Incompleteness Theorem is incomplete though, right? =)

Re:Proof use a lot of brute force (5, Interesting)

Trepidity (597) | more than 2 years ago | (#38631136)

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 (5, Interesting)

epine (68316) | more than 2 years ago | (#38631720)

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.

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

This discovery, which is technically so simple, made a very strong impression on me, and it represents a decisive turning point in the course of my reflections, a shift in particular of my centre of interest in mathematics, which suddenly found itself strongly focussed. I do not believe that a mathematical fact has ever struck me quite so strongly as this one, nor had a comparable psychological impact. This is surely because of the very familiar, non-technical nature of the objects considered, of which any childâ(TM)s drawing scrawled on a bit of paper (at least if the drawing is made without lifting the pencil) gives a perfectly explicit example. To such a dessin we find associated subtle arithmetic invariants, which are completely turned topsy-turvy as soon as we add one more stroke.

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 Kolmogorov-Chaitin view, one learns that truth is commonplace yet for the most part extraordinarily dull. Deep truth with compelling proof is exceedingly rare in the total perspective vortex of Chaitin's omega.

Whoever expected the precise integral solution for minimal Sudoku clueness to lead to a deep result? Most likely its one of the great multitudes of petty truths with no deep support. But if you feel differently, I'm interested in your compelling proof that longest win in KRBKNN has a DTM of 238 moves [youtube.com]. Feel enlightened on deep chess strategy by watching the video?

This doesn't mean that no-one should ever come along and chew some silage. We can't all be Grothendiecks. And maybe we learn some cool computational techniques along the way, such as the general applicability of dancing links to problems in exact cover.

Re:Willy Wonka's chocolate factory (2)

kestasjk (933987) | more than 2 years ago | (#38633308)

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:Willy Wonka's chocolate factory (1)

Anonymous Coward | more than 2 years ago | (#38634122)

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

Just sayin'

Re:Proof use a lot of brute force (1)

Anonymous Coward | more than 2 years ago | (#38631888)

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 proofs - far more important than any one mathematical problem. Welcome to the future.

Re:Proof use a lot of brute force (1)

AK Marc (707885) | more than 2 years ago | (#38632332)

Proofs also demonstrate How, and the "how" can imply a "why" and it's the how and why that are the important parts of many proofs, not just the answer.

Re:Proof use a lot of brute force (0)

Anonymous Coward | more than 2 years ago | (#38632112)

> never done anything of note in mathematics.
> criticizes those who have for not "providing enough insight."

Rock on with your bad self, Corky. I'm sure the guys who developed this proof are going to lose sleep over what some psuedo-intellectual giant on Slashdot thinks of their methods.

In related news... (5, Funny)

jcreus (2547928) | more than 2 years ago | (#38630916)

High-tech computers, working uninterruptedly for about 10 years, have finally discovered the exact minimum number of clues for the binary sudoku [xkcd.com].

I prefer my Sudoku with (5, Funny)

Anonymous Coward | more than 2 years ago | (#38630940)

After a long day at work I prefer my Sudoku with 80+ clues

Re:I prefer my Sudoku with (2, Informative)

tempest69 (572798) | more than 2 years ago | (#38631098)

Though there must be at least 78 clues to prevent the author from having the opportunity of slipping you an ambiguous puzzle.

Somewhat misleading. (4, Insightful)

drfuchs (599179) | more than 2 years ago | (#38630970)

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. (5, Insightful)

Anonymous Coward | more than 2 years ago | (#38631536)

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. (5, Insightful)

Beelzebud (1361137) | more than 2 years ago | (#38631012)

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. (-1, Troll)

Osgeld (1900440) | more than 2 years ago | (#38631026)

yes this money was well spent to figure out one of man's most complex problems ... a fucking brain teaser

Re:Cue the morons. (5, Insightful)

Beelzebud (1361137) | more than 2 years ago | (#38631086)

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. (-1, Troll)

Osgeld (1900440) | more than 2 years ago | (#38631232)

I did RTFA, whoopie shit "may pay off" != it is paying off

I may invest in nokia right now, it may pay off (it probably wont), and frankly if this sort of stunt is needed to stimulate interest in the circles of math nerds then we are truly fucked

Grats! the guy wasted time money and resources to brute force a solution to something no one cares about in the hopes that someone somewhere might shoehorn said brute force application into something totally unrelated

let me just crap my pants

Re:Cue the morons. (4, Insightful)

Beelzebud (1361137) | more than 2 years ago | (#38631264)

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

Re:Cue the morons. (0)

Anonymous Coward | more than 2 years ago | (#38634082)

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

There is, it's called a career in politics.

Re:Cue the morons. (0)

Anonymous Coward | more than 2 years ago | (#38631290)

Yes, we could tell you were somehow uneducated, yet an anal-retentive. Monkeys at the zoo find all kinds of things enjoyable about their excrement, and possess both of those qualities you possess. I suggest you give it a taste.

Re:Cue the morons. (4, Interesting)

The Askylist (2488908) | more than 2 years ago | (#38631332)

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:Cue the morons. (2)

The_Wilschon (782534) | more than 2 years ago | (#38632582)

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. (4, Informative)

TheRaven64 (641858) | more than 2 years ago | (#38631236)

Or, for those more interested in computers, sudoku has quite a few things in common with a number of error correction techniques and some compression algorithms. This particular result is moderately interesting from an information theoretic perspective and is probably a fairly minor part of a larger project that may well yield practical results.

Re:Cue the morons. (5, Insightful)

doshell (757915) | more than 2 years ago | (#38631480)

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. (2)

rmstar (114746) | more than 2 years ago | (#38631602)

yes this money was well spent to figure out one of man's most complex problems ... a fucking brain teaser

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 (5, Funny)

Anonymous Coward | more than 2 years ago | (#38631270)

There are only two reasons to spend taxpayer money: To defend America, and to get Republicans back into power!

Everything else is SOCIALISM!

Re:Socialism (0)

Anonymous Coward | more than 2 years ago | (#38635182)

The Republicans, the other Socialists.

Re:Cue the morons. (2)

DNS-and-BIND (461968) | more than 2 years ago | (#38631286)

I see we already have one ignoramus calling others idiots for daring to dissent with the prevailing narrative.

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 shilling for the mainstream narrative. "If you don't agree with my political points, you must be stupid. There is no other possible explanation for your disagreement with what me and all my friends agree to be totally obvious."

Re:Cue the morons. (-1)

Anonymous Coward | more than 2 years ago | (#38631606)

I see we already have one ignoramus calling others idiots for daring to dissent with the prevailing narrative.

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 shilling for the mainstream narrative. "If you don't agree with my political points, you must be stupid. There is no other possible explanation for your disagreement with what me and all my friends agree to be totally obvious."

Go back to your sociology class with its fancy hegemony this and military-industrial complex that while the men do the heavy lifting.

Re:Cue the morons. (2, Insightful)

AK Marc (707885) | more than 2 years ago | (#38632546)

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.

Re:Cue the morons. (1)

Anonymous Coward | more than 2 years ago | (#38631772)

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 an idiot, is very counter-intuitive: You have to treat him seriously, be polite, and truly understand him. (Unless that is too much work. But then, don't bother and walk away, since all other options will only make it worse. Something that is certainly not in your interest, is it?)

If you do that, you will know that from their pov, with their experiences and thoughts, their view by definition makes sense. But you know it doesn't. And you know why. So you see the holes in their information and thoughts, and can, in (their) character, ask those questions.
The beauty of asking it as questions, is that 1. the idiot does the work, while you can relax and poke at the holes, and 2. if he finds his former opinion to be wrong, it will be *him* who found it out. So he can keep his pride. Which is key to him accepting the whole thing.
This results in a very strong supporter of the newly found knowledge, and perhaps even a friend. You don't need to push it into him. It will be part of him from the beginning.

Does that sound better than getting all angry, being called a dick, and making things worse? :)
(Yeah, I know, I'm having trouble doing it right now, and not falling into total rage about you. Forgive me that, and may he forgive you. But: Was it worth it? What do you think? :D)

Now about the "What's the point?" question: What if you looked at it like a valid question? That doesn't sound that far-fetched, does it? Can you yourself give a valid answer to that question? Yes? Why didn't you do that then? Was there a reason not to? What do you think happens, when somebody constantly gets reactions like your comment, and is a moron? Does it sound like something good?

See...

Question (0)

Anonymous Coward | more than 2 years ago | (#38631024)

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?

Re:Question (2)

tempest69 (572798) | more than 2 years ago | (#38631184)

Your question needs clarification

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:Question (2)

maxwell demon (590494) | more than 2 years ago | (#38631794)

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 once, and analogously for the columns.

Also note that when checking a sub square, line or column, you only have to check that every digit occurs; if so, then you already know that each occurs exactly once.

Difficulty (5, Interesting)

Dan East (318230) | more than 2 years ago | (#38631028)

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:Difficulty (1)

DavidTC (10147) | more than 2 years ago | (#38631276)

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 clues, but it is entirely possible to have, for example, a 17 clue puzzle that is, in fact, unsolvable except via computer, or via actual brute force, is not really a plausible solution for most people.

Re:Difficulty (3, Interesting)

The Askylist (2488908) | more than 2 years ago | (#38631512)

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:Difficulty (-1)

Anonymous Coward | more than 2 years ago | (#38631964)

Woooosh.

Not comedic, but... You missed the entire point of his comment, and substituted yours. I'm assuming just so that you could call him wrong on that.

Re:Difficulty (1)

The Askylist (2488908) | more than 2 years ago | (#38632132)

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 (0)

wrencherd (865833) | more than 2 years ago | (#38631042)

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?

Re:Non-anonymous question (0)

Anonymous Coward | more than 2 years ago | (#38634822)

Depends on what you assume for the given solution. In the most general case, you need to know everything.

I prefer... (3, Funny)

wbr1 (2538558) | more than 2 years ago | (#38631054)

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

Re:I prefer... (2, Funny)

Anonymous Coward | more than 2 years ago | (#38631328)

It's your cup of.... Alphabet Soup?

Antalya ilanlar (-1)

Anonymous Coward | more than 2 years ago | (#38631112)

http://www.ilantalya.com
Antalya emlak, otomobil, i ilanlar

Reading TFA (1)

KingAlanI (1270538) | more than 2 years ago | (#38631142)

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

300,000 years (2, Insightful)

Anonymous Coward | more than 2 years ago | (#38631150)

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:300,000 years (1)

nedlohs (1335013) | more than 2 years ago | (#38631272)

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:300,000 years (2)

maxwell demon (590494) | more than 2 years ago | (#38631858)

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.

What about... (0)

Anonymous Coward | more than 2 years ago | (#38631242)

16 clues will always generate puzzles with multiple solutions.
Does this also mean that any puzzle with 17 clues has exactly one solution?

Re:What about... (4, Informative)

The Askylist (2488908) | more than 2 years ago | (#38631440)

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.. (1)

KingAlanI (1270538) | more than 2 years ago | (#38631256)

This puzzle has only 17, but that's enough clues for me...

Re:With apologies to Winger.. (1)

karnal (22275) | more than 2 years ago | (#38631342)

Next you'll be quoting Slaughter or Skid Row

Re:With apologies to Winger.. (1)

KingAlanI (1270538) | more than 2 years ago | (#38631640)

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? (2)

NEDHead (1651195) | more than 2 years ago | (#38631266)

Assuming he had access to 5 supercomputers, this would suggest he ran the program continuously for at least 45+ years. Dedication!

Re:Millions of hours? (0)

Anonymous Coward | more than 2 years ago | (#38631530)

And yet this isn't 1967. So instead Of having only 5 readily available supercomputers, he had probably more like 4500 available. Give me your calculations, how long would that tale?

Re:Millions of hours? (1)

iggymanz (596061) | more than 2 years ago | (#38631632)

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:Millions of hours? (2)

FaxeTheCat (1394763) | more than 2 years ago | (#38632174)

Actually reading the linked article (pretty strange concept to read the article before posting, I agree, but sometimes we behave irrationally), reveals the sentence "Having spent two years testing the algorithm, McGuire and his team used about 7 million CPU hours ".

Re:Millions of hours? (2)

grcumb (781340) | more than 2 years ago | (#38634668)

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

flaw (0)

Anonymous Coward | more than 2 years ago | (#38631506)

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

Re:flaw (1)

OrangeTide (124937) | more than 2 years ago | (#38632462)

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.

Proportionate difficulty...supercomputer use...? (0)

Anonymous Coward | more than 2 years ago | (#38631674)

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?

How many require guessing? (1)

Frans Faase (648933) | more than 2 years ago | (#38631832)

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.

Re:How many require guessing? (1)

pacc (163090) | more than 2 years ago | (#38631928)

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 if the correct solution would lead to another choice situation after just one or two steps.

Programs (1)

Frans Faase (648933) | more than 2 years ago | (#38632446)

What I mean more exactly, is to use a program (like this one [iwriteiam.nl]) that transforms a Sudoku into an Exact Cover problem, and next try to use an elimination program (like this one [iwriteiam.nl]) to find a solution. See also this blog entry [iwriteiam.nl] for some more information.

"do not" or "may not"? (1)

Anonymous Freak (16973) | more than 2 years ago | (#38633544)

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?

Also, a 17-clue puzzle exists IIRC (0)

Anonymous Coward | more than 2 years ago | (#38633582)

So this lower bound is exact.

So....the hardest sudoku is?!?! (1)

JimboTheProgrammer (1756970) | more than 2 years ago | (#38634422)

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.

next, try Calcudoku... (1)

dr_blurb (676176) | more than 2 years ago | (#38635696)

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):

  • how many different puzzles are possible, given a certain puzzle size and a distribution of cage sizes?
  • how to deterministically create a puzzle with a unique solution?
  • how to compute a measure of the difficulty level of a puzzle?
  • how many (and which) clues are needed for a "single path" solution?
  • ...

For example puzzles, see online Calcudoku puzzles [calcudoku.org].

Load More Comments
Slashdot Account

Need an Account?

Forgot your password?

Don't worry, we never post anything without your permission.

Submission Text Formatting Tips

We support a small subset of HTML, namely these tags:

  • b
  • i
  • p
  • br
  • a
  • ol
  • ul
  • li
  • dl
  • dt
  • dd
  • em
  • strong
  • tt
  • blockquote
  • div
  • quote
  • ecode

"ecode" can be used for code snippets, for example:

<ecode>    while(1) { do_something(); } </ecode>
Sign up for Slashdot Newsletters
Create a Slashdot Account

Loading...