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.
Not to be pedantic but the answer is 42.
I forget, what was the question again?
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?
I thought the answer was Jesus!
(Boy, have I got the wrong blog!)
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.
.
“What do you get if you multiply six by nine?”
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.
Duh. That sounds right to me. Thanks.
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.
Perfectly accurate if we are using Base 13!