Mathematicians: You must have at least 17 clues to solve Sudoku

A recent mathematics study showed that you have to have at least 17 clues on a Sudoku grid in order for the puzzle to be solvable. You could make the game easier, by adding more clues. But if there are fewer than 17 clues, then the game becomes impossible to solve. In this video, mathematician James Grime explains how the researchers figured this out.

Video Link

Via Grrlscientist and The Guardian

PREVIOUSLY:

26

  1. Wait.  He even says 17 isn’t the smallest number you can start with.  It’s just the smallest number that you can start with and get a unique answer.  So technically you could start with less than 17, but that will yield multiple correct answers.

    1. Sure, but if I start with zero clues I can get a HUGE number of right answers. That’s not really a puzzle though, is it? I think you need a single unique solution to actually make it a puzzle.

      1. Not really.  You just need a unique answer so you can have a valid key.  Checking your work and making sure you got “the right” answer makes people feel a lot better than saying there are multiple right answers.

        1. OK. We’ll agree to disagree. I think “multiple right answers” = doodling. Doodling is fun too, it just isn’t a puzzle.

        2. I don’t know what you mean by ‘checking your work’ – if you solved the puzzle using logic, you don’t have to check anything. You can easily see that it’s correct. signed,  A Sudoku Fan

          1.  My mother and myself are like you, we finish it’s done.  My father on the other hand always meticulously compares his to the key.  I think he does it to be absolutely sure he hasn’t made any errors.  I know of one time I placed a wrong number, thought I changed it but didn’t (but still played like I had).  It worked out fine, except for having two of the same number in one section.

        3. No, bcsizemo, it is you who is wrong.  By definition, a Sudoku puzzle has one unique solution.

          As an aside, real Sudoku solvers don’t check the back of the book.  If your 9X9X9 grids all have unique numbers, then you solved the puzzle correctly.

    2. Yes, correct: if there are fewer than 17 clues, there can/will be more than one answer.  I read the paper about a week ago.

      Essentially, the proof was: we tried them all.

  2. What he says at the end really resonates with me.  Personally, I can’t stand working on sudoku puzzles because I feel like it’s just tedious wrought work, and I derive no pleasure from solving them.  I much prefer crossword puzzles because they inspire a much greater sense of imagination.  It’s kind of funny because I once argued with my brother about the merits of both puzzles, and traditionally, he’s been the one who’s “into words” (reading/writing), and I’m typically the “numbers guy” (more of an interest in math/science)…  Yet, he was defending sudoku and I was defending crosswords?!  I don’t think the argument was ever resolved with anything more than the notion that “my brother’s crazy” from the both of us. :)

    1. You say “my brother is crazy” I say “oh good, we can share a newspaper.” Perspective is a beautiful thing.

    2. It’s more a logic puzzle than a numbers puzzle – maybe that’s why your brother enjoys it more than a crossword. You could use letters of the alphabet instead of numbers.
      Or maybe you enjoy crosswords because as a math/science guy, they’re more challenging for you than a math puzzle would be.

    3. It makes perfect sense to me. I can’t stand to do Sudoku at all – I think because I’m a pure mathematician. I did my first one, found it fun, saw the general strategy for solving them, and lost interest. (Cryptonomicon has it right!)

      I guess that when simple depth-first search is a sufficiently optimal algorithm, I don’t find a puzzle very compelling.

      YMMV, of course. A physicist friend disagrees with me very emphatically.

  3. The algorithm given at Instructables is faulty — it’s only effective for up to “Medium” difficulty puzzles generally. Harder puzzles require resorting to deeper-level tricks, and sometimes even trial and error to solve. Which one might argue doesn’t change the essential nature of the puzzle, true, but then we start getting into intrinsic flaws of this whole class of logic puzzle.

  4. A brute force computer proof is OK, but surely to have real application to other fields of mathematics you would need to understand WHY the lower bound is 17.  Isn’t that where the real mathematics would be? Then you could extend the result to different and more complicated problems. So Mr McGuire, the job is not even half finished. Get back to work…

    1.  This is increasingly an issue with modern mathematics research, because sheer computing power has allowed us to prove things we couldn’t previously, but at the cost of elegance. The four-colour map theorem is the obvious famous example.

      It lets us get things done that couldn’t be previously, though, so the PCs stay.

  5. BoingBoing needs a copy writer who understands what was really meant by the authors’ proof. 

    Seventeen is the minimum number of clues for a classic Sudoku grid to  have a unique solution.  Saying “…the game becomes impossible to solve” for fewer than seventeen clues is imprecise language at best and flat-out wrong at worst.  A computer could solve a sixteen-clue puzzle, but the solution will always be non-unique and therefore not a Sudoku puzzle.

  6. Wouldn’t it make sense that it wouldbe 17? Here is my reasoning but I am simply theororizing:

    At minimum it would make sense that you would need at the very least one number clue per row/column. Imagine a board with the very left edge and the very top edge filled out. This would be nine clues across and nine clues up/down minus one overlapping in the middle which equals 17. 

    Am I the only one that thinks this? The absolute minimum would be 1 clue per row/column because without that one clue in the row/column you would never be able to deduce any of the numbers in that specific row/column, rendering the puzzle impossible to solve to one unique answer. IF you imagine that same puzzle with all the left side and the top filled with clues MINUS one there would be one blank row or column. Of course, I am only using this one example to illustrate my point, these 17 numbers could be arranged differently. 

    Simply speculation. 

    1. Not sure I follow.  If I put 9 numbers down the diagonal, then there will be one clue in every row and one clue in every column.

      1. Yes, but the clue would not be unique to that row, it would be the same clue in the row and the column. I guess I should have reworded my original statement to indicate this. 

    2.  This makes sense, and is a pretty good intuitive mental picture.  Of course, those don’t prove anything… but a lot of great maths proofs boil down to taking some clear concept like this and formalizing it.

      The formal stage is very important though, as the mental picture can easily make assumptions you hadn’t realised.

      (For example: in your example, 15 clues are actually enough for a unique solution.  If the very top and left edge are filled out, you can delete any one clue from each edge; the correct number is immediately forced by the other clues, because they’re all lined up. This doesn’t work in general, of course, because the clues won’t always be so conveniently arranged.)

    3.  it isn’t true that you need at least one clue in every row and column.  there do exist valid, one-solution Sudoku puzzles with rows and columns that don’t have clues.

Comments are closed.