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 -> Setting sudoku
View previous topic :: View next topic  
Author Message
nurreo

Joined: 04 Aug 2005
Posts: 5
:

Items
PostPosted: Thu Aug 04, 2005 5:12 pm    Post subject: Unique Solution Reply with quote

Hi! first of all sorry for my English.
I'm tring like a lot of people to realize my software and I have a lot of problems Sad
I read a lot of post but i'm not able to undertasd how can I verify if a puzzle 9x9 has a unique solution.
I mean, what are the condition to say surely this puzzle has only 1 solution?
Thank you in advance for your answer.

Marco
Italy
Back to top
View user's profile Send private message Send e-mail
Peptone69

Joined: 04 Aug 2005
Posts: 1
:

Items
PostPosted: Thu Aug 04, 2005 10:40 pm    Post subject: Reply with quote

Hi nurreo!
Od anche ciao!

Sudoku is divided in two parts (I quote Giulio Cesare Smile ):
- Open Sudoku, number already wrote are < 17; --> most then one solution
- Closed Sudoku, number already wrote are > 17; --> only one solution.
My information: "Venerdì di Repubblica" some week ago.

Ossia se hanno più di 17 numeri sono chiusi e possono avere solo una soluzione; se ne hanno meno più soluzioni. Fonte "Venerdì di Repubblica" qualche settimana fa.

I hope this is your seeked anwear!

Spero di averti dato la risposta che cercavi!

Peptone
World
Back to top
View user's profile Send private message
antony

Joined: 22 Jul 2005
Posts: 13
:

Items
PostPosted: Fri Aug 05, 2005 4:42 am    Post subject: Reply with quote

Hello Marco,
I just wrote a piece of code in Java and C for you Wink

Basically, if you have a recursive solver, testing for multiple solutions comes to exploring the tree of possibilities, and counting the solutions you reach. But you can stop it when you found 2 solutions at least. For example:
Code:
Grid grid = ...
integer count = 0

function Explore:
   if the grid is solved, then count++ and return
   choose an unsolved cell
   for every candidate it has:
      set it
      call Explore
      unset it
      if count > 1 then return

call Explore


(You can generalize this, e.g Dancing Links, by replacing "cell" and "candidates" with "constraint" and "choices")

Hope it helps,
Antony


Last edited by antony on Fri Aug 05, 2005 3:37 pm; edited 1 time in total
Back to top
View user's profile Send private message
nurreo

Joined: 04 Aug 2005
Posts: 5
:

Items
PostPosted: Fri Aug 05, 2005 4:56 am    Post subject: Reply with quote

Peptone69 wrote:
Hi nurreo!

Sudoku is divided in two parts (I quote Giulio Cesare Smile ):
- Open Sudoku, number already wrote are < 17; --> most then one solution
- Closed Sudoku, number already wrote are > 17; --> only one solution.
My information: "Venerdì di Repubblica" some week ago.



The unique solution depend not only by the exposed cell. Many grid with more then 17 exposed cell has more solution.
I stoped to play Repubblica's grid becouse thay are multiple solution in any case and I'm interested only in 'pure' Sudoku grid.

Saluti.

Marco
Italy
Back to top
View user's profile Send private message Send e-mail
nurreo

Joined: 04 Aug 2005
Posts: 5
:

Items
PostPosted: Fri Aug 05, 2005 5:04 am    Post subject: Reply with quote

antony wrote:
Hello Marco,
I just wrote a piece of code in Java and C for you :

Basically, if you have a recursive solver, testing for multiple solutions comes to exploring the tree of possibilities, and counting the solutions you reach. But you can stop it when you found 2 solutions at least.
Hope it helps,
Antony


Hi Antony,
I'm happy to see the 'light' per this tema Very Happy

I understud the concept and now I will try with my recursive solver.
If my performance are not enough I'lll insert your code to test.

Thanks a lot and if You don't mind I will ask someting again Wink

Marco
Italy
Back to top
View user's profile Send private message Send e-mail
Display posts from previous:   
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Setting 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