Slashdot Mirror
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."
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.
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.
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
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.
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).
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.
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
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.