By Néstor Romeral Andrés
 

November – 28 - 2010

 

Dedicated to my daughter.

 

 

I will demonstrate that no set of 16 clues that uniquely defines a Sudoku grid exists. To do so, I will take 2 steps:

 

1. Determine the lower bound for the number of ‘relations’ needed to solve a puzzle.
2. Determine the minimum number of clues needed to reach that lower bound.

 

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.

 

 

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.