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   

Checking unicity

 
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Solving sudoku
View previous topic :: View next topic  
Author Message
frisch

Joined: 16 Nov 2005
Posts: 55
:
Location: Paris, France

Items
PostPosted: Thu Nov 24, 2005 5:11 pm    Post subject: Checking unicity Reply with quote

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
View user's profile Send private message Send e-mail Visit poster's website
dukuso

Joined: 14 Jul 2005
Posts: 424
:
Location: germany

Items
PostPosted: Thu Nov 24, 2005 11:12 pm    Post subject: Reply with quote

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
View user's profile Send private message Send e-mail Visit poster's website
Lummox JR

Joined: 07 Sep 2005
Posts: 202
:

Items
PostPosted: Fri Nov 25, 2005 6:35 pm    Post subject: Reply with quote

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
View user's profile Send private message
Display posts from previous:   
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Solving 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