Sudoku Programmers Forum Index

 
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister   ProfileProfile   Log inLog in          Games  Calendar

Log in to check your private messagesLog in to check your private messages   

Minimum number of clues needed

 
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> The mathematics of sudoku
View previous topic :: View next topic  
Author Message
kmin

Joined: 22 Apr 2006
Posts: 1
:

Items
PostPosted: Sat Apr 22, 2006 9:55 am    Post subject: Minimum number of clues needed Reply with quote

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
View user's profile Send private message
gsf

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

Items
PostPosted: Sat Apr 22, 2006 10:31 am    Post subject: Re: Minimum number of clues needed Reply with quote

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
View user's profile Send private message Visit poster's website
The Ostrich

Joined: 20 Apr 2006
Posts: 49
:

Items
PostPosted: Sun May 21, 2006 11:31 pm    Post subject: Reply with quote

The answer is that no-one has yet proved that the answer is 17.
Back to top
View user's profile Send private message
Papy

Joined: 14 Jul 2006
Posts: 12
:

Items
PostPosted: Thu Aug 17, 2006 10:28 am    Post subject: Minimu clues Reply with quote

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)
Back to top
View user's profile Send private message Send e-mail
Obi-Wahn

Joined: 21 Aug 2006
Posts: 15
:

Items
PostPosted: Mon Aug 21, 2006 8:53 am    Post subject: Reply with quote

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
View user's profile Send private message
Display posts from previous:   
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> The mathematics of sudoku All times are GMT
Page 1 of 1

 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
Sudoku Programmers topic RSS feed 


Powered by phpBB © 2001, 2005 phpBB Group

Igloo Theme Version 1.0 :: Created By: Andrew Charron