Maths on a Mug 7

I saw someone solving a Sudoku on the train this morning, which made again think about the minimum number of ‘clues’ (numbers in the grid) required to solve a puzzle. It has been proven that you need at least 17 clues to have a unique, solvable, solution.

The proof is not for the faint hearted, for a long time it had been conjectured that 17 clues were the minimum necessary, but no one had actually proved it. The authors of the proof conducted an exhaustive computer search for 16-clue Sudoku puzzles and found none, thereby proving that the minimum number of clues required is indeed 17. Their approach involved several key steps:

1. Cataloging All Possible Sudoku Grids: They generated a comprehensive list of all valid, completed Sudoku grids. Given the vast number of possible grids, this was a significant computational task.

2. Developing an Efficient Search Algorithm: The team created a program named “checker” to systematically search each completed grid for potential 16-clue puzzles that have a unique solution. This required implementing efficient algorithms capable of handling the computational complexity involved.

3. Utilizing Unavoidable Sets and Hitting Set Algorithms: They employed the concept of unavoidable sets—specific cell groupings that must contain at least one clue to ensure a unique solution. By identifying these sets, they could focus their search more effectively. To manage the computational challenges, they developed a novel algorithm for enumerating hitting sets, which are minimal sets of clues intersecting all unavoidable sets. This approach was crucial, as traditional backtracking algorithms would have been too slow for an exhaustive search.

4. Conducting the Exhaustive Search: With their optimized algorithms, they performed a thorough search across all possible Sudoku grids. The absence of any valid 16-clue puzzles in their findings led them to conclude that at least 17 clues are necessary for a Sudoku puzzle to have a unique solution.