Best of 2012: Mathematicians Solve Minimum Sudoku Problem
“Sudoku is a number puzzle consisting of a 9 x 9 grid in which some cells contain clues in the form of digits from 1 to 9. The solver’s jobs is to fill in the remaining cells so that each row, column and 3×3 box in the grid contains all nine digits.
There’s another unwritten rule: the puzzle must have only one solution. So grids cannot contain just a few starting clues.
It’s easy to see why. A grid with 7 clues cannot have a unique answer because the two missing digits can always be interchanged in any solution. A similar argument explains why grids with fewer clues must also have multiple solutions.
But it’s not so easy to see why a grid with 8 clues cannot have a unique solution, or indeed one with 9 or more clues.
That raises an interesting question for mathematicians: what is the minimum number of Sudoku clues that produces a unique answer?
This is a question that has hung heavy over the Sudoku community, not least because they think they know the answer. Sudoku fanatics have found numerous examples of grids with 17 clues that have a unique solution but they have never found one with 16 clues.
That suggests the minimum number is 17 but nobody has been able to prove that there isn’t a 16-clue solution lurking somewhere in puzzle space.
Enter Gary McGuire and pals at University College Dublin. These guys have solved the problem using the tried and trusted mathematical technique of sheer brute force.
Keep Reading
Most Popular
Large language models can do jaw-dropping things. But nobody knows exactly why.
And that's a problem. Figuring it out is one of the biggest scientific puzzles of our time and a crucial step towards controlling more powerful future models.
The problem with plug-in hybrids? Their drivers.
Plug-in hybrids are often sold as a transition to EVs, but new data from Europe shows we’re still underestimating the emissions they produce.
Google DeepMind’s new generative model makes Super Mario–like games from scratch
Genie learns how to control games by watching hours and hours of video. It could help train next-gen robots too.
How scientists traced a mysterious covid case back to six toilets
When wastewater surveillance turns into a hunt for a single infected individual, the ethics get tricky.
Stay connected
Get the latest updates from
MIT Technology Review
Discover special offers, top stories, upcoming events, and more.