View previous topic :: View next topic 
Author 
Message 
 kmin
 Joined: 22 Apr 2006  Posts: 1  :   Items 

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? 

Back to top 


 gsf
 Joined: 18 Aug 2005  Posts: 408  :  Location: NJ USA  Items 

Posted: Sat Apr 22, 2006 10:31 am Post subject: Re: Minimum number of clues needed 


kmin wrote:  Does anybody know what is the minumum number of clues that would lead to a uniqe solution? and if so how was it calculated? 
maybe (empirical, no proof)
google "sudoku minimum" 

Back to top 


 The Ostrich
 Joined: 20 Apr 2006  Posts: 49  :   Items 

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


The answer is that noone has yet proved that the answer is 17. 

Back to top 


 Papy
 Joined: 14 Jul 2006  Posts: 12  :   Items 

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+161) 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) 

Back to top 


 ObiWahn
 Joined: 21 Aug 2006  Posts: 15  :   Items 

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. 

Back to top 


