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   

Unique Solution

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

Joined: 20 Apr 2006
Posts: 1
:

Items
PostPosted: Thu Apr 20, 2006 1:51 am    Post subject: Unique Solution Reply with quote

Can someone provide an explination or proof, perhaps using the idea of Latin Squares, on why a proper sudoku puzzle will always have one unique solution?

Thanks
Back to top
View user's profile Send private message
Ruud
Site Admin
Joined: 17 Sep 2005
Posts: 708
:
Location: Netherlands

Items
PostPosted: Thu Apr 20, 2006 2:13 am    Post subject: Reply with quote

I'm not sure what you're asking for.

A sudoku is a proper sudoku because it has a unique solution. It is a qualification by convention.

You can examine a sudoku with a backtracking solver. When the solver finds exactly one solution, you may label it 'proper'.

If this is not what you're looking for, please explain what you need to know,

Ruud.
_________________
Meet me at sudocue.net
Back to top
View user's profile Send private message Visit poster's website
coloin

Joined: 05 May 2005
Posts: 97
:

Items
PostPosted: Thu Apr 20, 2006 8:38 am    Post subject: Reply with quote

There are three aspects here:
the final grid
the given clues
the generated clues

the final grid has to be valid before you start
Code:
+---+---+---+   Complete grid
|439|286|157|
|176|593|284|
|258|147|396|
+---+---+---+
|381|754|629|
|795|632|841|
|624|918|735|
+---+---+---+
|542|371|968|
|867|429|513|
|913|865|472|
+---+---+---+

all variations of the given glues [taken from the vaild completed grid] will therefore be valid


the question of whether it will be solved uniquely is down to whether each "unavoidable set" in the grid has at least one given clue in it.

Each complete grid has THOUSANDS of unavoidable sets ! - it is remarkable that some grids can be solved in 17 clues....but almost all grids have a combination of 19 given clues which cover all the sets and define the grid.

The simplest unavoidable sets have 4 clues - one of these clues in the set must be one of the given clues.
Code:
+---+---+---+4 set unavoidable - this has 2 grid solutions
|439|286|157|
|176|593|284|
|258|147|396|
+---+---+---+
|381|754|629|
|795|632|841|
|6..|918|735|
+---+---+---+
|5..|371|968|
|867|429|513|
|913|865|472|
+---+---+---+

+---+---+---+  6 set unavoidable - 2 solutions
|439|.86|.57|
|.76|593|.84|
|.58|.47|396|
+---+---+---+
|381|754|629|
|795|632|841|
|624|918|735|
+---+---+---+
|542|371|968|
|867|429|513|
|913|865|472|
+---+---+---+

there are also 36[8+7+6+5+4+3+2+1],18 clue unavoidable sets consisting of 9 of one number and 9 of another.......this explains why you can only have one absent clue number.
Code:
+---+---+---+18 set unavoidable - no3s and no4s! - this has 2 grid solutions
|..9|286|157|
|176|59.|28.|
|258|1.7|.96|
+---+---+---+
|.81|75.|629|
|795|6.2|8.1|
|62.|918|7.5|
+---+---+---+
|5.2|.71|968|
|867|.29|51.|
|91.|865|.72|
+---+---+---+

a generated clue can be inserted when ALL the unavoidable sets with this clue in it already have in them at least one given clue.

the program "unavoid" in "checker" will print out all the smaller unavoidable sets in any given grid. http://www.maths.nuim.ie/staff/gmg/sudoku/

I hope this explains to all !


Last edited by coloin on Thu Apr 20, 2006 3:34 pm; edited 1 time in total
Back to top
View user's profile Send private message
Papy

Joined: 14 Jul 2006
Posts: 12
:

Items
PostPosted: Thu Aug 17, 2006 11:13 am    Post subject: Unique solutionn Reply with quote

You don't have to proof that there is only one solution:
by definition a sudoku grid have only one solution!!!
Multiply solutions don't dive sudoku
Papy
Back to top
View user's profile Send private message Send e-mail
Catweazle

Joined: 30 Jul 2006
Posts: 8
:
Location: Brazil

Items
PostPosted: Fri Aug 18, 2006 2:42 am    Post subject: Reply with quote

I agree with Papy.

If a sudoku has more than one solution, you simply cannot solve the puzzle with logic.
And therefore it is no puzzle because you cannot finish it.
This because at a certain point you do not have a clue which number to fill in next.
Therefore a sudoku puzzle has to have 1 solution so it can be solved with logic until the end.

I hope this answers your question fully.

Theo
_________________
More puzzles please......
Back to top
View user's profile Send private message Send e-mail Visit poster's website
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