Minimum number of clues needed

kmin · Posted: Sat Apr 22, 2006 9:55 am Post subject: Minimum number of clues needed

Does anybody know what is the minumum number of clues that would lead to a uniqe solution? and if so how was it calculated?

gsf

The Ostrich · Posted: Sun May 21, 2006 11:31 pm Post subject:

The answer is that no-one has yet proved that the answer is 17.

Papy · Posted: Thu Aug 17, 2006 10:28 am Post subject: Minimu clues

The answer is 17
@The Ostrich

Here MY demonstration:

A sudoku grid is a 9x9 matrix 9 rows and 9 colons

If you want to reffer to a particular cell you have to give X and Y coordonates
Put the numbers on a grid You need 17 numbers 9 for the rows and only 8 for the colons (the first is common)

Suppose that you have a function f(x,y) that determine the value of a
case you will use the 17 numbers(but 18 values) to access to the 81 cells
If you remove a numbers you will acces to only 72 celles so your function will not 'see' the last 9!
So to refer a 9x9 grids you need 17 interconactable references

a 16*16 grids will need at least 31 (16+16-1) clues!....

Sorry I' m not matematician only programmer so my demonstreation does not have a mathématical apparence but I think ythat tha logic is good.

Papy
(French lover)

Obi-Wahn · Posted: Mon Aug 21, 2006 8:53 am Post subject:

Sorry, Papy. Although I don't fully understand your reasoning, the resulting formula can't be correct, because it suggests that 3 clues (2+1) would be required for a 2*2 grid and 5 clues (2+3) for a 3*3 grid.
Nevertheless there are only 2 possible solutions for a latin square of size 2 requiring only 1 clue to make it unique.
For a latin square of size 3 there are 12 possible solutions. The first clue reduces it to 4 and the second clue can make it unique but you have to choose it carefully. It must not have the same value or share a row or column with the first clue. But the minimum number of clues is 2.
And that's without any kind of box restraints like we have in a Sudoku.

It's like The Ostrich said. There are many Sudokus with 17 clues and a unique solution but no one found a Sudoku with only 16 clues that meets this condition. But that's not a proof.