| dukuso
| Joined: 14 Jul 2005 | Posts: 424 | : | Location: germany | Items |
|
Posted: Sun Nov 27, 2005 8:43 am Post subject: sudokus as SAT-instances |
|
|
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 |
|