Mathematician Claims Breakthrough in the Sudoku Problem

Scientists have proven that the minimum number of clues or starting digits needed to complete a Sudoku puzzle is 17.

While you might just need a pencil and your brain to fill in this week’s Sudoku puzzle, an Irish mathematician used millions of hours of supercomputing time in order to solve an important open problem in the mathematics of Sudoku; the game that was initially popularized in Japan and involves filling up a 9×9 grid with the numbers 1 to 9 according to certain rules.

Gary McGuire of the University College Dublin recently posted a proof online that showed that the minimum number of clues, or starting digits, that were needed to complete a puzzle is 17. With 16 and fewer clues, the Sudoku puzzle doesn’t have a unique solution. Most of the puzzles that you’ll find in newspapers have around 25 clues. The less clues you have, the more difficult the problem.

The consensus is that McGuire’s proof is probably valid, which means that it’s an important advance in the field of Sudoku mathematics. The rules of Sudoku are simple. Puzzlers are required to fill out a 9×9 grid with the numbers 1 to 9 so that no digit is repeated in the same column, row, or 3×3 subgrid. The clues are numbers that are already filled out within the puzzle. Enthusiasts have observed that while there are some puzzles with 17 clues, no one has come up with a valid 16-clue puzzle. This led to the conjecture that 16-clue puzzles with unique solutions do not exist.

McGuire simplified the problem by designing a hitting-set algorithm, in which he searches for unavoidable sets that allow interchanges within the puzzle, meaning that they would allow multiple solutions. Once the unavoidable sets are found, the computing task was much more manageable. It took him two years to test the algorithm. McGuire and his team used about 7 million CPU hours at the Irish Center for High-End Computing in Dublin, searching through all possible grids with the algorithm. It’s what is called a brute force approach, crunching the problem down with massive computing power and iterations.

Since it took so long to come to the proof, it will also take a while for other mathematicians to check the proof. The algorithm was developed as McGuire developed proofs for papers in gene-sequencing and cellular networks.