It has been proven that a standard Sudoku puzzle must have at least 17 clues to have a unique solution.
Sudoku rules:
Fill in the numbers 1-9 in each row, column, and 3x3 subgrid in a 9x9 grid.
Each number can only appear once in each row, column, and 3x3 subgrid.
Fill in the blank spaces with the numbers 1-9 so that each row, column, and 3x3 subgrid has all the numbers 1-9.
Sudoku is a logic-based number-placement puzzle. The objective is to fill a 9x9 grid with the numbers 1-9, so that each row, column, and 3x3 subgrid contains all nine numbers exactly once.
In 2009, Gary McGuire and his team proved that any Sudoku puzzle with 16 clues must have at least two solutions. They did this by using a technique called "dead patterns."
A dead pattern is a Sudoku configuration that has two or more possible solutions. McGuire and his team found that any Sudoku puzzle with 16 clues must contain at least one dead pattern. Therefore, these puzzles must have at least two solutions.
This result has several implications. First, it means that there is no such thing as a 16-clue Sudoku puzzle with a unique solution. Second, it means that any 16-clue Sudoku puzzle can be solved in multiple ways. Third, it means that there are an infinite number of 16-clue Sudoku puzzles.
Here is a more technical explanation of the proof that Sudoku puzzles must have at least 17 clues to have a unique solution:
The proof begins by considering a Sudoku puzzle with 16 clues. We can think of this puzzle as a set of constraints on the numbers that can be placed in the empty squares.
We can then use a technique called "backtracking" to try to find a solution to the puzzle. Backtracking is a recursive algorithm that tries all possible combinations of numbers in the empty squares until it finds a solution.
If there is a unique solution to the puzzle, then backtracking will eventually find it. However, if there are multiple solutions, then backtracking may never find a solution.
McGuire and his team used backtracking to show that if there is a 16-clue Sudoku puzzle with a unique solution, then there must be a way to start the backtracking algorithm in such a way that it always finds the solution.
They then showed that this is not possible. They did this by constructing a set of 16 clues that leads to a dead pattern. This dead pattern means that there are two possible solutions to the puzzle, and no way to start the backtracking algorithm in such a way that it always finds the same solution.
This result shows that any 16-clue Sudoku puzzle must have at least two solutions.