View previous topic :: View next topic |
Author |
Message |
| nurreo
| Joined: 04 Aug 2005 | Posts: 5 | : | | Items |
|
Posted: Thu Aug 04, 2005 5:12 pm Post subject: Unique Solution |
|
|
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
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 |
|
|
| Peptone69
| Joined: 04 Aug 2005 | Posts: 1 | : | | Items |
|
Posted: Thu Aug 04, 2005 10:40 pm Post subject: |
|
|
Hi nurreo!
Od anche ciao!
Sudoku is divided in two parts (I quote Giulio Cesare ):
- 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 |
|
|
| antony
| Joined: 22 Jul 2005 | Posts: 13 | : | | Items |
|
Posted: Fri Aug 05, 2005 4:42 am Post subject: |
|
|
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. 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 |
|
|
| nurreo
| Joined: 04 Aug 2005 | Posts: 5 | : | | Items |
|
Posted: Fri Aug 05, 2005 4:56 am Post subject: |
|
|
Peptone69 wrote: | Hi nurreo!
Sudoku is divided in two parts (I quote Giulio Cesare ):
- 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 |
|
|
| nurreo
| Joined: 04 Aug 2005 | Posts: 5 | : | | Items |
|
Posted: Fri Aug 05, 2005 5:04 am Post subject: |
|
|
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
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
Marco
Italy |
|
Back to top |
|
|
|