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   

sudokus as SAT-instances

 
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Puzzles
View previous topic :: View next topic  
Author Message
dukuso

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

Items
PostPosted: Sun Nov 27, 2005 8:43 am    Post subject: sudokus as SAT-instances Reply with quote

sudokus can be converted into "SAT"-instances
(e.g. with http://magictour.free.fr/sud2sat.exe)
and then solved with common SAT-solvers,
see e.g.:
http://www.intellektik.informatik.tu-darmstadt.de/SATLIB/solvers.html
These problems are quite similar to "QWH" or "QCP" problems,
which are basically sudokus without the blocks-constraint.
So they can have any size, not just squares 9*9,16*16 as with sudoku.
For some such problems see:
http://www.menneske.no/sudoku/eng/
and then choose a size under "no boxes"


I think sudokus might be good benchmark instances
and an enrichment on research about QWH
It would be interesting to compare sudokus with QWHs
wrt. algorithms to solve them, phase-transition, etc.

-Guenter
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 -> Puzzles 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