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:Proof use a lot of brute force (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 within it. It is possible, but IMHO highly unlikely.
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:Proof use a lot of brute force (Score:0)
Re:Proof use a lot of brute force (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:Proof use a lot of brute force (Score:1)
Interesting link.
You do realize that GÃdel Incompleteness Theorem is incomplete though, right? =)
Re:Proof use a lot of brute force (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 appendices or with a new region) and you end up needing at least n different colors.
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:Willy Wonka's chocolate factory (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:Willy Wonka's chocolate factory (Score:1)
Just sayin'
Re:Willy Wonka's chocolate factory (Score:2)
Re:Willy Wonka's chocolate factory (Score:2)
Re:Proof use a lot of brute force (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 proofs - far more important than any one mathematical problem. Welcome to the future.
Re:Proof use a lot of brute force (Score:2)
Re:Proof use a lot of brute force (Score:0)
> 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.
Re:Proof use a lot of brute force (Score:2)
In related news... (Score:5, Funny)
Re:In related news... (Score:1)
Re:In related news... (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:I prefer my Sudoku with (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:Somewhat misleading. (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 more questions to be asked. I have written code to generate sudokus using the above algorithm. I end up with between 22 and 28 numbers, though most of the time it is 24 or 25. But ending up with twentysomething numbers depends on the order I removed numbers. Maybe if I removed them in a different order, I would have been able to remove more. So can every combination of the full 81 fields be reduced to just 17 if you just find the right 64 to remove? If not what is the maximum number that would be required? And is there an efficient algorithm to find the smallest possible number of clues for a specific combination of the 81 numbers?
Cue the morons. (Score:5, Insightful)
Re:Cue the morons. (Score:0, Troll)
yes this money was well spent to figure out one of man's most complex problems ... a fucking brain teaser
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:Cue the morons. (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 very hard to make an informed decision about whether the study was merit-able.
The liberals are no better - I got sent a "99% rally" email from someone likely in the 1%, but not a millionaire - I sent back that the top 1.5% starts at $250k - you probably ARE the top 1% (I know she and her husband make about $400k since my brother and her husband are business partners). To that she replied OMG, I didn't know that!
I do have some very liberal friends that are usually objective, but we disagree on certain points. Only my moderate conservative friends are objective - the very conservative ones are frustrating. One of them was arguing that every citizen should pay at least $1 tax every year, and I was saying that's crazy - why should retired people and people that live in the street and have no money at all have to pay tax? He said "they use public streets and parks, they should pay tax - no exceptions." It is this "no exceptions" Republican mentality that makes me want to use a baseball bat on their heads - that is the absolute WORST reason I've ever heard of for taxation - we should take money from the people that don't have any just because they live here...
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:0)
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:Cue the morons. (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:Cue the morons. (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:Cue the morons. (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:Cue the morons. (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 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. (Score:3, Insightful)
When you think about it, it's insane the level of conventional military might the US can casually deploy. And it costs trillions. Wouldn't it be cheaper to buy an occasional dinner and save on the tanks and planes? Diplomacy is favored by the Republicans because they have a habit of having friends and family in the defense industry, and they also tend to vomit on world leaders.
Re:Cue the morons. (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 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? :) :D)
(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?
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 (Score:0)
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 (Score:1)
Re:Question (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:Question (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 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 (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:Difficulty (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 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 (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:Difficulty (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:I prefer... (Score:2, Funny)
It's your cup of.... Alphabet Soup?
Re:I prefer... (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:I prefer... (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 for the purposes of this analysis.
The "Hitting Set Problem" isn't just an issue in Sudoku
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:300,000 years (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:300,000 years (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.
What about... (Score:0)
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... (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:With apologies to Winger.. (Score:2)
Next you'll be quoting Slaughter or Skid Row
Re:With apologies to Winger.. (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:Millions of hours? (Score:0)
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? (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:Millions of hours? (Score:3)
Re:Millions of hours? (Score:2)
Re:Millions of hours? (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:Starting positions (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...
flaw (Score:0)
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 (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.
Proportionate difficulty...supercomputer use...? (Score:0)
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? (Score:2)
Re:How many require guessing? (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 if the correct solution would lead to another choice situation after just one or two steps.
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:"do not" or "may not"? (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 puzzles [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:Well this will solve world hunger. (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:Well this will solve world hunger. (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:Well this will solve world hunger. (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 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. (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:Well this will solve world hunger. (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 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.
Re:Well this will solve world hunger. (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.