View previous topic :: View next topic |
Author |
Message |
| frisch
| Joined: 16 Nov 2005 | Posts: 55 | : | Location: Paris, France | Items |
|
Posted: Thu Nov 24, 2005 5:11 pm Post subject: Checking unicity |
|
|
Hello,
I'm wondering whether people know clever techniques for the following problem. We have a puzzle together with a solution. We're interested in checking whether the puzzle has another solution. In particular, do we have some properties stating that when a puzzle has more than one solution, then we can find another solution which is "close" to the solution we know. (If yes, we can use this solution to drive the solving process.) "Uniqueness" criterion can be used, of course.
Related question. We start from a puzzle with a single solution and we remove one clue. We want to check whether the resulting puzzle still has a single solution. We can start the solver with a "negative guess" (corresponding to the one we have removed), and the look for a solution. Do you see other tricks?
-- Alain |
|
Back to top |
|
|
| dukuso
| Joined: 14 Jul 2005 | Posts: 424 | : | Location: germany | Items |
|
Posted: Thu Nov 24, 2005 11:12 pm Post subject: |
|
|
we had been talking a lot about "unavailables" for a solution-grid
in the other forum, in the minimum-clues-thread
These are subsets of the 81 cells which must intersect any
sudoku over this grid.
You can't create all unavoidables, but many of those with fewer cells.
See programs
http://magictou.free.fr/unav27.exe
and ..unav36.exe
When you find an unavoidable which is not hit by the sudoku-givens
then you can easily construct another solution from it |
|
Back to top |
|
|
| Lummox JR
| Joined: 07 Sep 2005 | Posts: 202 | : | | Items |
|
Posted: Fri Nov 25, 2005 6:35 pm Post subject: |
|
|
The only real way to find whether a puzzle has multiple solutions is to 1) run it through a backtracking algorithm, or 2) try to solve it with logical tests (except for the uniqueness tests) up to and including trial and error. If logical tests fail you at some point, that gives you your answer: There are multiple solutions. Then you can simply pick a new given from the set of unsolved cells and try again. |
|
Back to top |
|
|
|