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:

Maggie Koerth-Baker is the science editor at BoingBoing.net. She writes a monthly column for The New York Times Magazine and is the author of Before the Lights Go Out, a book about electricity, infrastructure, and the future of energy. You can find Maggie on Twitter and Facebook.

Maggie goes places and talks to people. Find out where she'll be speaking next.

MORE: Games • math • obsessions • Science • sudoku

More at Boing Boing

Eurovision 2013: An American in London

The technology that links taxonomy and Star Trek

bcsizemo

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.
- ChicagoD
  
  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.
  - bcsizemo
    
    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.
    - ChicagoD
      
      OK. We’ll agree to disagree. I think “multiple right answers” = doodling. Doodling is fun too, it just isn’t a puzzle.
    - Melinda9
      
      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
      - bcsizemo
        
        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.
    - http://profile.yahoo.com/3Q4LHGUNYORAGQABDE53VXUGAQ MikeyZ
      
      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.
- Paul Renault
  
  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.
graywh

“they come from Japan” The phenomenon, yes. The puzzle, no. At least, according to Will Shortz.
tallpat

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. :)
- ChicagoD
  
  You say “my brother is crazy” I say “oh good, we can share a newspaper.” Perspective is a beautiful thing.
- Melinda9
  
  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.
- Tynam
  
  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.
chenille

The paper is available at http://arxiv.org/abs/1201.0749, for those interested. I wish it also covered 16×16, 25×25, and larger sudoku-type puzzles; it would be good to know the significance of seventeen in this case.
http://www.epinardscaramel.com TokenFrenchDude

He writes his ‘G’ as ‘Ct’, it bothers me.
http://www.epinardscaramel.com TokenFrenchDude

Computer scientists know how to do brute force, but it takes a mathematician to simplify the problem :)
http://twitter.com/salavant James Robson

Woo, Tellytubby Rooftop! (Top of the Maths Department in Cambridge :D).
JohnH

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

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…
- Tynam
  
  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.
http://profile.yahoo.com/3Q4LHGUNYORAGQABDE53VXUGAQ MikeyZ

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.
http://www.facebook.com/dburpee David Burpee

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.
- DrDave
  
  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.
  - http://www.facebook.com/dburpee David Burpee
    
    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.
- Tynam
  
  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.)
- mathgrrl
  
  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.