Lower Limit Found For Sudoku Puzzle Clues

Proof use a lot of brute force by JoshuaZ · 2012-01-08 06:56 · Score: 5, Insightful

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 by Anonymous Coward · 2012-01-08 07:00 · 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 by JoshuaZ · 2012-01-08 07:00 · Score: 4, Informative

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 by The+Askylist · 2012-01-08 07:15 · Score: 4, Interesting

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 by Trepidity · 2012-01-08 07:22 · 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.

--
10 PRINT CHR$(205.5+RND(1)); : GOTO 10
Re:Proof use a lot of brute force by rmstar · 2012-01-08 08:27 · Score: 5, Interesting

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. (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 by Anonymous Coward · 2012-01-08 08:58 · 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 by JoshuaZ · 2012-01-08 09:13 · Score: 3, Informative

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:Well this will solve world hunger. by Malk-a-mite · 2012-01-08 06:56 · 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. "

In related news... by jcreus · 2012-01-08 06:56 · Score: 5, Funny

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

Re:In related news... by maxwell+demon · 2012-01-08 08:49 · Score: 2

This is not accurate. A binary Sudoku consists of 1x1x1 cells.
Of course it consists of 1x1x1x1 cells.

--
The Tao of math: The numbers you can count are not the real numbers.

I prefer my Sudoku with by Anonymous Coward · 2012-01-08 06:59 · Score: 5, Funny

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

Re:I prefer my Sudoku with by tempest69 · 2012-01-08 07:17 · Score: 2, Informative

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

Re:Well this will solve world hunger. by Linsaran · 2012-01-08 06:59 · 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).

--
In a bit of shameless internet panhandling, I accept Litecoin Donations at Lbd2oH9QsthD1GfuUXPyka12YxvWJYnBVf

Re:Well this will solve world hunger. by walkerp1 · 2012-01-08 07:00 · Score: 5, Insightful

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

Somewhat misleading. by drfuchs · 2012-01-08 07:01 · Score: 4, Insightful

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. by Anonymous Coward · 2012-01-08 08:28 · 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. by kasperd · 2012-01-08 23:35 · Score: 2

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

--

Do you care about the security of your wireless mouse?

Cue the morons. by Beelzebud · 2012-01-08 07:07 · Score: 5, Insightful

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. by Beelzebud · 2012-01-08 07:16 · Score: 5, Insightful

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. by TheRaven64 · 2012-01-08 07:42 · Score: 4, Informative

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.

--
I am TheRaven on Soylent News
Re:Cue the morons. by Beelzebud · 2012-01-08 07:49 · Score: 4, Insightful

If only there were a medal for those being most proud of their own ignorance.
Re:Cue the morons. by The+Askylist · 2012-01-08 08:02 · Score: 4, 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. by doshell · 2012-01-08 08:20 · 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.

--
Score: i, Imaginary
Re:Cue the morons. by rmstar · 2012-01-08 08:40 · Score: 2

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.
Re:Cue the morons. by AK+Marc · 2012-01-08 10:50 · Score: 2, Insightful

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.

--
Learn to love Alaska
Re:Cue the morons. by The_Wilschon · 2012-01-08 10:56 · Score: 2

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.

--
SIGSEGV caught, terminating

wait... not that kind of sig.

Difficulty by Dan+East · 2012-01-08 07:09 · 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.

--
Better known as 318230.

Re:Difficulty by The+Askylist · 2012-01-08 08:25 · Score: 3, 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 ;-)

I prefer... by wbr1 · 2012-01-08 07:11 · Score: 3, Funny

I prefer Sudoku puzzles with only one clue. That way I can finish them any damn way I want. Multiple solutions are my friend.
Besides, I am a word geek, not a math geek. Cruciverbalism is my cup of tea (or letters).

--
Silence is a state of mime.

Re:I prefer... by Anonymous Coward · 2012-01-08 08:02 · Score: 2, Funny

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

300,000 years by Anonymous Coward · 2012-01-08 07:24 · 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 by maxwell+demon · 2012-01-08 09:13 · 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.

--
The Tao of math: The numbers you can count are not the real numbers.

Re:Question by tempest69 · 2012-01-08 07:30 · Score: 2

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:Well this will solve world hunger. by toomanyhandles · 2012-01-08 07:48 · Score: 5, Funny

People with more education than you do, apparently.

Millions of hours? by NEDHead · 2012-01-08 07:49 · Score: 2

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? by FaxeTheCat · 2012-01-08 09:57 · Score: 2

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? by grcumb · 2012-01-08 16:25 · Score: 2

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

--
Crumb's Corollary: Never bring a knife to a bun fight.

Socialism by Anonymous Coward · 2012-01-08 07:50 · 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:Well this will solve world hunger. by NFN_NLN · 2012-01-08 08:06 · 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]

Starting positions by byteherder · 2012-01-08 08:15 · Score: 2

I have always wondered how many starting Soduko puzzles there are that have a unique solution.

Re:What about... by The+Askylist · 2012-01-08 08:15 · Score: 4, 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!)

Willy Wonka's chocolate factory by epine · 2012-01-08 08:55 · Score: 5, Interesting

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.

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 Kolmo

Re:Willy Wonka's chocolate factory by kestasjk · 2012-01-08 12:30 · Score: 2

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.

--
// MD_Update(&m,buf,j);

Re:Question by maxwell+demon · 2012-01-08 09:03 · 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.

--
The Tao of math: The numbers you can count are not the real numbers.

Ready to be sad? by SteveFoerster · 2012-01-08 10:00 · Score: 3, Funny

Well, close: there's a grant program. Seriously.

--
Space game using normal deck of cards: http://BattleCards.org

Re:Well this will solve world hunger. by AK+Marc · 2012-01-08 10:03 · Score: 4, 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).

--
Learn to love Alaska

Re:Well this will solve world hunger. by Anonymous Coward · 2012-01-08 11:09 · 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.

Slashdot Mirror

Lower Limit Found For Sudoku Puzzle Clues

48 of 121 comments (clear)