Sudoku is a mathematic puzzle that has gained considerable popularity in the 21st century, rivalling the classic puzzle that is the crossword. You are given a 9×9 table divided into 9 equal squares, filled with a certain number of digits. Your goal is to fill in the table so that each row, column and subsquare (of 9 small squares) contains every digit from 1 to 9. You are not allowed to have the same number appear on the same row, column or subsquare, as there are not enough spaces for spare digits.
The more digits (“clues”) that you are given at the start of the puzzle, the easier it is to solve it. This begs the question: what is the minimum number of clues that you need to solve a sudoku puzzle?
Sudoku puzzles with 17 clues have been completed traditionally. We know that 7 clues is not enough as the last 2 digits can be interchanged, creating puzzles with more than one solution. Using mathematics, we know that if we can solve a puzzle with n clues, then a puzzle with n+1 clues can be solved as well. Ergo, the answer lies somewhere between 8 and 16.
In 2012, Gary McGuire, Bastian Tugemann and Gilles Civario tackled this problem using one of the oldest tricks in mathematical analysis: brute force. The total number of possible sudoku puzzles that can be generated is 6,670,903,752,021,072,936,960, or 6.67 x 10²¹. After accounting for symmetry arguments (meaning that two puzzles may be essentially identical, but just rotated or flipped), we are left with 5,472,730,538 possible unique solutions.
The team used supercomputers to analyse all of these possibilities to see if any puzzle can be solved with just 16 clues, as the conventional thought was that 17 was the minimum number of clues possible from traditional methods. After a year of calculations, the computer found no sudoku puzzle could be solved with only 16 clues. This was confirmed by another team from Taiwan a year later, proving that the minimum number of clues required for sudoku is indeed 17.
