Sudoku puzzles are as ubiquitous as reality shows these days, and enthusiastic solvers can find puzzles of nearly any difficulty with ease.
Sudoku puzzles are usually ranked from one to five stars, with five star puzzles being the most difficult. Difficulty can depend not only on the number of starting digits, but their placement and the level of deduction involved.
Sudoku enthusiasts were the first to notice that the lowest number of clues required for a unique solution is 17. Puzzles with 16 clues invariably had alternate solutions.
For comparison purposes, the average newspaper sudoku has 25 set numbers. The sudoku puzzles on PuzzleNation vary in difficulty, but our easy puzzles range from 30 to 36 clues and our expert puzzles range from 25 to 30 clues, with medium and hard puzzles clue counts falling in between.
But the 17-clue threshold was all conjecture until a mathematician from University College Dublin named Gary McGuire put in the time (and the computer processing power) to write a mathematical proof confirming the suspicions of sudoku enthusiasts.
He designed a specific computer algorithm to process various sudoku grid patterns, allowing him to cut down on the computing time necessary to verify his conjecture. (Even with the reduced computing time, it took 7 million CPU hours in total, a monumental amount of processing time.)
From the nature.com article:
The idea behind this was to search for what he calls unavoidable sets, or arrangements of numbers within the completed puzzle that are interchangeable and so could result in multiple solutions. To prevent the unavoidable sets from causing multiple solutions, the clues must overlap, or ‘hit’, the unavoidable sets. Once the unavoidable sets are found, it is a much smaller—although still non-trivial—computing task to show that no 16-clue puzzle can hit them all.
Of course, as I said before, difficulty isn’t just about the number of clues. The puzzle widely regarded as the world’s hardest sudoku puzzle has 21 clues, but their placement makes for a much more mentally-taxing solving exercise.
I guess it just goes to show the old real estate cliche is true: it’s all about location, location, location.