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×10^{16}, much less than the 6.7×10^{21} 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.

Mr Ed says

Not to be pedantic but the answer is 42.

noastronomer says

I forget, what was the question again?

Carl says

If we prove that no

n-clue puzzle has a unique solution, can it be taken for granted that no puzzle with fewer thannclues 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?Pope Bandar bin Turtle says

I thought the answer was

Jesus!(Boy, have

Igot the wrong blog!)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.

.

Chrisj says

“What do you get if you multiply six by nine?”

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.

Carl says

Duh. That sounds right to me. Thanks.

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.

Malky says

Perfectly accurate if we are using Base 13!