The answer is 17


I think that most people are familiar with Sudoku puzzles. There are some interesting questions that can be asked such as what is the minimum number of the 81 boxes in the grid that need to be filled in initially (the ‘clues’) in order to be able to obtain a unique solution?

It is known that for at least some puzzles one can obtain a unique solution with 17 clues, and no one had found any puzzles with 16 clues that had unique solutions. But is 17 the minimum number required? If you could show that none of the 16-clue puzzles had unique solutions, then you would have proven that the minimum number was 17.

One way to prove it is by brute force, using a computer to attempt to solve every possible 16-clue combination. But it turns out that the number of such possibilities is about 3.3×1016, much less than the 6.7×1021 total number of possible Sudoku arrangements but still staggeringly large, and this would require a huge amount of computer time, about 300,000 years.

So mathematician Gary McGuire used the various symmetries that exist in these puzzles to reduce the number of different puzzles to be solved by a computer. Even then the final number of puzzles took 7 million computer hours and took about a year to carry out. You can read his paper here and an article about it here.

Here is an entertaining video from mathematician James Grime explaining the problem and how it was solved.

Comments

  1. says

    If you could show that none of the 16-clue puzzles had unique solutions, then you would have proven that the minimum number was 17.

    If we prove that no n-clue puzzle has a unique solution, can it be taken for granted that no puzzle with fewer than n clues has a unique solution? It sounds like a reasonable assumption to me, but I assume that there is a mathematically rigorous proof of it available?

  2. P Smith says

    He says in the last 40 seconds that he doesn’t like sudoku because “it’s a game of pure logic.” I find that many people who enjoy sudoku the most are uninquisitive about science and believe religion unquestioningly.

    They seem capable of thinking rationally, but choose not to be. I’ve tried and failed to get them to understand that the same methods which apply to solving sudokus are very much the same methods that can apply to any field of science – eliminating impossibilities, finding and eliminating contradictions, comparing data to find single possibilities, etc.

    .

  3. Mano Singham says

    Suppose you had a unique solution to a puzzle that had only 15 clues (say), then by adding a clue to it in the appropriate location (dictated by the 15-clue solution) you would have a 16-clue puzzle with a unique solution, which would contradict the above result.

  4. F says

    But that doesn’t include short-term situations of numbers only, handed to you in a table.

    But yeah.

    The religious have their way with logic, too, but start with faulty assumptions.

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>