Forgot your password?
typodupeerror
Japan Math Supercomputing Idle Entertainment Science

Lower Limit Found For Sudoku Puzzle Clues 121

Posted by timothy
from the 17-ain't-young dept.
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."
This discussion has been archived. No new comments can be posted.

Lower Limit Found For Sudoku Puzzle Clues

Comments Filter:
  • by JoshuaZ (1134087) on Sunday January 08, 2012 @02:56PM (#38630904) Homepage
    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.
    • by Anonymous Coward on Sunday January 08, 2012 @03:00PM (#38630956)

      This is true.

      But you dismiss the fact that hard proofs are often done gradually: it's usually easier to prove something you know beforehand than take a stab at the dark.

      What I mean is, now that this brute force approach has shown that 9^2 requires at least 17 to get a general solution, then we can now go on to prove it using standard methods.

      • Re: (Score:2, Informative)

        by Anonymous Coward

        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 wi

        • by JoshuaZ (1134087) on Sunday January 08, 2012 @05:13PM (#38631848) Homepage
          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).
    • by JoshuaZ (1134087) on Sunday January 08, 2012 @03:00PM (#38630958) Homepage
      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.
    • by The Askylist (2488908) on Sunday January 08, 2012 @03:15PM (#38631082)
      Pretty much like the proof of the four colour theorem, then. A really good proof would be able to show a solution for n dimensions, where n > 2, but all we have as a proof is an exhaustive enumeration of the possible networks in 2 dimensions. Most unsatisfying, to those of us who like to see analytical proofs that don't rely on mechanical methods, but there you go. It's still a clever bit of work, and the technique may come in useful elsewhere, but I'd rather see a pencil and paper proof any day.
      • by rmstar (114746) on Sunday January 08, 2012 @04:27PM (#38631524)

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

        While I am inclined to agree with you, the thing is that there is no a priori reason why such a proof should exist. We should be happy that a proof exists at all.

        For some additional perspective on this, here is a very readable article by Chaitin on his Omega number [maths.org]. (Since this is a divulgation article, it may be advisable to read first his short bio at the end, otherwise this may seem crackpottery to some).

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

        • Interesting link.

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

      • by abell (523485)

        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.

        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 appe

    • by Trepidity (597) <delirium-slashdo ... org minus author> on Sunday January 08, 2012 @03:22PM (#38631136)

      I agree on the final result, but there may be something interesting in the symmetries developed, which the researchers seem to suggest involved some interesting and/or novel techniques. If true, that could have broader applications; reducing seemingly large search spaces to equivalent smaller search spaces by taking advantages of symmetries is a recurring motif in computational X for lots of X, so if they have new techniques there that could be useful.

    • by epine (68316) on Sunday January 08, 2012 @04:55PM (#38631720)

      Proofs really should give us insight into why statements are true, and this one really doesn't. That's not to knock on the accomplishment: this clearly took a lot of effort, some very smart work, and some clever use of group theory and very skilled programming.

      This comment reminds me that it's not what you have, it's what you do with it. Sometimes you hear about an athlete that he or she has "an extra gear" in the heat of battle. I went to school with a lot of smart people. The median smart person would sometimes make a lazy statement of sentiment such as this one that would never have passed the lips of my classmates with the hard-baked intellectual edge. Hard-baked was part talent, but mostly attitude: people who just thought that the lazy use of "should" was beneath their level of intellectual determination (as it should be, in my personal opinion).

      Obviously the landmark results in mathematics are the ones which forge a deep connection between branches of mathematics formerly distinct. Every proof should be one of those. Or at least that's how the coke addict would phrase it. Mathematics as Willy Wonka's chocolate factory. Who needs peas? No candy cane construction permitted by the Chocolate Port Authority if less intriguing that Dessin d'enfant [wikipedia.org].

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

      I arrived at this page yesterday evening beginning my tour with a question about the provability of reachable states, the mechanism of temporal logic, Zermelo's contribution to set theory, the Hilbert epsilon operator, the Bourbaki group (before Sheldon Cooper there was Jean Dieudonne), and finally to Grothendieck. I have a fairly clear recollection of reading a long piece about Grothendieck several years ago which lamented the loss to mathematics when he devoted the bulk of his career to elaborating a program in algebraic geometry instead of cracking one hard problem after another, which it seemed some people thought he could do. He was regarded by some as much too brilliant for the pedestrian task of assembling an overarching synthesis.

      All mathematicians should be more like Grothendieck should have been. Doesn't that sentiment become quickly cloying once you engage the mental clutch?

      A year ago another tour took me to Knuth's algorithm of dancing links, which I compiled out of curiosity, then modified the decision step with the next most obvious heuristic. I was interested to watch the famous dancing links during a back-tracking step, so I searched the internet for a famously hard Sudoku example, found one, then single-stepped through the solution process in the debugger. I was disappointed: it reached solution without once backtracking. I think it made three guesses in total, either binary or trinary. I vaguely recall the odds of it guessing correctly all the way to solution was about ten to one. I loaded some other hard problems. On these it actually backtracked from time to time, but not as often I would have presumed. Even hard problems fall quickly to structured guess-work. It's only when you map Sudoku into a logic inference framework that hard problems are hard.

      In the Kolmo

      • by kestasjk (933987) *

        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.

      • by Anonymous Coward

        people who just thought that the lazy use of "should" was beneath their level of intellectual determination (as it should be, in my personal opinion).

        Just sayin'

      • by tehcyder (746570)
        Jesus Christ you're a wanker.
    • by Anonymous Coward

      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 pr

      • by AK Marc (707885)
        Proofs also demonstrate How, and the "how" can imply a "why" and it's the how and why that are the important parts of many proofs, not just the answer.
  • by jcreus (2547928) on Sunday January 08, 2012 @02:56PM (#38630916)
    High-tech computers, working uninterruptedly for about 10 years, have finally discovered the exact minimum number of clues for the binary sudoku [xkcd.com].
  • by Anonymous Coward on Sunday January 08, 2012 @02:59PM (#38630940)

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

    • Re: (Score:3, Informative)

      by tempest69 (572798)
      Though there must be at least 78 clues to prevent the author from having the opportunity of slipping you an ambiguous puzzle.
  • by drfuchs (599179) on Sunday January 08, 2012 @03:01PM (#38630970)
    But that does not mean that in all puzzles with more than 17 clues you can remove a clue and still have a unique solution. This makes the last sentence in the main post kind of meaningless; plenty of (x+1)-clue puzzles are harder than some x-clue ones.
    • by Anonymous Coward on Sunday January 08, 2012 @04:28PM (#38631536)

      No, they proved that there are no puzzles with 16 clues that have a unique solution. There are plenty of puzzles with more clues that don't have a unique solution. e.g. a sudoku with columns 8 and 9 missing. So removing a clue from a 55 clue puzzle could lead to a puzzle with no unique solution.

    • by kasperd (592156)

      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

  • Cue the morons. (Score:5, Insightful)

    by Beelzebud (1361137) on Sunday January 08, 2012 @03:07PM (#38631012)
    I see we already have one idiot asking "what's the point", much like John McCain or Sarah Palin asking why we need to research the fruit fly genome, or put money into a planetarium. This is news for nerds. If you want to whine about tax money, and don't understand why fundamental research is important, then find some place else to stink up with your ignorance.
    • Socialism (Score:5, Funny)

      by Anonymous Coward on Sunday January 08, 2012 @03:50PM (#38631270)

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

      Everything else is SOCIALISM!

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

      It's not about whining about tax money. It's about ensuring that the tax money that we DO spend, is spent wisely. All too often, this does not occur. As an educated person, surely you are aware of wasteful government spending. Heck, anytime the Pentagon gets its hands on taxpayer money, it's wasteful spending, eh? So there's something you can relate to.

      Calling dissenters ignorant is just sh

    • by Anonymous Coward

      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

  • Difficulty (Score:5, Interesting)

    by Dan East (318230) on Sunday January 08, 2012 @03:09PM (#38631028) Homepage Journal

    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.

    • by DavidTC (10147)

      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 clu

      • Re:Difficulty (Score:4, Interesting)

        by The Askylist (2488908) on Sunday January 08, 2012 @04:25PM (#38631512)

        It's not the solving of the sudoku grid that is being done by "brute force" here, but the enumeration of possible solvable puzzles and the proof that no unique solutions exist for 16 clue puzzles.

        It's actually quite instructive to write a sudoku solver - I did so myself a few years back when I decided to learn Python and needed a problem to work on.

        There's a little more finesse involved than brute force ;-)

  • Sorry for the double-post, but I got signed out somehow:

    I have a question which is somewhat related here and about which I have always wondered:

    How much of a sudoku, once filled in, must be "checked" in order to be certain that the whole thing is correct?
  • I prefer... (Score:4, Funny)

    by wbr1 (2538558) on Sunday January 08, 2012 @03:11PM (#38631054)
    I prefer Sudoku puzzles with only one clue. That way I can finish them any damn way I want. Multiple solutions are my friend.
    Besides, I am a word geek, not a math geek. Cruciverbalism is my cup of tea (or letters).
    • Re: (Score:2, Funny)

      by Anonymous Coward

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

    • by Alsee (515537)

      I prefer Sudoku puzzles with only one clue.

      I hate people who try to cramp my creative freedom. I only play blank Sudoko.

      -

  • 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 f

  • 300,000 years (Score:2, Insightful)

    by Anonymous Coward

    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.

    • by nedlohs (1335013)

      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.

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

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

  • by NEDHead (1651195) on Sunday January 08, 2012 @03:49PM (#38631266)

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

    • by iggymanz (596061)

      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!

    • 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 ".
      • Someone didn't read the article they are commenting on? Shocking! You must be new here.
      • by grcumb (781340)

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

  • That ought to be enough for anyone.

  • by byteherder (722785) on Sunday January 08, 2012 @04:15PM (#38631438)
    I have always wondered how many starting Soduko puzzles there are that have a unique solution.
    • 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...

  • Sudoku's, like so much other puzzles, are basically equivalent with solving Exact Cover problems. There are two types of Exact Cover problems that have a unique solution, those that can be solved with simple elimination and those that cannot. Simple elimination means that you take two columns in the Exact Cover problem and see if there is an implication. If this is the case, the rows that have only one 1 in the two columns involved, can be removed and the two columns can be joined. This simple elimination r
    • by pacc (163090)

      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 i

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

  • So lame. This guy sends supercomputers into years of churning to find the hardest puzzle, and he doesn't give it up? C'mon man.
  • Now the mathematicians are done with Sudoku, start working on Calcudoku (which is like killer Sudoku, but with more operators and no restriction on puzzle size):

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

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

  • Once again, the number 17 appears.

Work is the crab grass in the lawn of life. -- Schulz

Working...