PROOF THAT NO 16-CLUE
SUDOKU PUZZLE EXISTS
By Néstor Romeral Andrés
November – 28 - 2010
Dedicated to my daughter.
INTRODUCTION:
I will demonstrate that no set of 16
clues that uniquely defines a Sudoku grid exists. To do so, I will take 2
steps:
I assume the reader is already
familiar with the Sudoku puzzle.
I’ve also included the general
formula for any given size at the end of the proof.
I’m an engineer, not a
mathematician. So my mathematical language and notation are far from perfect.
However, the proof is so simple that this shouldn’t be a problem for the
reader.
I’m Spanish. Please forgive my English.
PROOF:
We define the relation ‘cannot be
equal to’ between 2 cells of a Sudoku. Each cell is then related to other 20
cells:
Cell ‘A’ cannot be equal to any of the ‘x’ cells.
Every cell of the Sudoku is then
related to exactly 20 other cells. As there are 81 cells, the graph of
relations for the puzzle has 810 edges in total.
But the 20 relations of a given cell
(A) are redundant, as there are only 8 numbers different than ‘A’, so each number
appears several times in the ‘x’ cells.
Example: Cell ‘A’ has a value of 1.
It is related to other 20 cells that have a value other than 1.
(Exactly 4 numbers appear 2 times
each, and exactly 4 numbers appear 3 times each. This happens always for any
cell.)
Redundant relations are redundant
pieces of information. We don’t need redundant information to solve the graph. Suppose
we remove the ‘redundant’ copies of every relation for every cell, so each cell
ends up with 8 ‘relations’:
The new graph will have 324 edges: 8x81/2
= 324.
This is the minimum number of relations
we need to solve a puzzle; as if we remove any one of the edges of this new
graph we will get 2 ‘undefined’ cells.
Note that I’m not saying that we can
actually create this graph, but that 324 is the lower bound for the number of
relations.
So we’ve determined a lower bound
for the number of ‘…cannot be equal to…’ relations we need.
Now, how many clues do we need to
reach this number of relations?
One isolated clue determines 20
relations (as we’ve seen above).
Example: The puzzle above has 9 clues
determining 9x20=180 relations.
So 20 is an upper bound for the
number of relations created by each clue.
If we add 16 clues to an empty
graph, we will be adding at most 16
x 20 = 320 non-redundant relations. But we
need at least 324 to determine a
unique puzzle.
So it is
not possible to create a unique puzzle with just 16 clues.
Note: For 17 clues, the upper bound for the number of relations is 340, that is bigger than 324.
The general formula for any given
size can be easily obtained from the above procedure:
With ‘n’ being the size of the
puzzle (side) and C being the minimum number of clues needed to make it unique
and solvable.
Examples:
4x4 Sudoku:
n=4 => C=4
16x16 Sudoku
n=16 => C=50
Edited: Removed observations and supposed best solutions, as they could be wrong.
PROOF THAT NO 16-CLUE SUDOKU PUZZLE EXISTS by NESTOR ROMERAL ANDRES is licensed under a Creative Commons Reconocimiento-NoComercial-SinObraDerivada 3.0 Unported License.