Lower Limit Found For Sudoku Puzzle Clues

ananyo writes "An Irish mathematician has used a complex algorithm and millions of hours of supercomputing time to solve an important open problem in the mathematics of Sudoku, the game popularized in Japan that involves filling in a 9X9 grid of squares with the numbers 1–9 according to certain rules. Gary McGuire of University College Dublin shows in a proof posted online [PDF] that the minimum number of clues — or starting digits — needed to complete a puzzle is 17; puzzles with 16 or fewer clues do not have a unique solution. Most newspaper puzzles have around 25 clues, with the difficulty of the puzzle decreasing as more clues are given."

Comments

Proof use a lot of brute force

[JoshuaZ]

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

[Anonymous Coward]

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

[JoshuaZ]

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

[The Askylist]

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

[Trepidity]

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.

Re:Proof use a lot of brute force

[rmstar]

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

[Malk-a-mite]

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

[jcreus]

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

I prefer my Sudoku with

[Anonymous Coward]

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

Re:Well this will solve world hunger.

[Linsaran]

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.

[walkerp1]

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

Somewhat misleading.

[drfuchs]

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.

[Anonymous Coward]

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.

[Beelzebud]

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.

[Beelzebud]

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.

[TheRaven64]

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.

[Beelzebud]

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

Re:Cue the morons.

[The Askylist]

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.

[doshell]

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.

Difficulty

[Dan East]

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

[toomanyhandles]

People with more education than you do, apparently.

Socialism

[Anonymous Coward]

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.

[NFN_NLN]

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:What about...

[The Askylist]

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

[epine]

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

[AK Marc]

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