http://crypto.stanford.edu/pbc/notes/zdd/
description | Logic puzzle solvers, using ZDDs. |
homepage URL | http://crypto.stanford.edu/pbc/notes/zdd/ |
owner | benlynn@gmail.com |
last change | Sun, 29 Nov 2009 21:43:40 +0000 (29 13:43 -0800) |
URL | git://repo.or.cz/zddfun.git |
https://repo.or.cz/zddfun.git | |
push URL | ssh://repo.or.cz/zddfun.git |
https://repo.or.cz/zddfun.git (learn more) | |
bundle info | zddfun.git downloadable bundles |
content tags |
These programs use ZDDs (zero-suppressed binary decision diagrams) to solve logic puzzles. See Knuth, "The Art of Computer Programming", Volume 4, Fascicle 1, which I partly summarized:
http://crypto.stanford.edu/pbc/notes/zdd/
Build with make.
Puzzle |
Sample Input |
Source |
Dominosa |
dominosa.txt |
dom.c |
Fillomino |
fillomino.txt |
fill.c |
Lights Out |
light.txt |
light.c |
Slither Link |
slither.txt |
loop.c |
Nonogram |
nonogram.txt |
nono.c |
All programs read a puzzle from standard input then print the solution on standard output.
The file spi.txt is a Slither Link puzzle I used loop.c to construct. Try solving it by hand first.
Standard Sudokus are too big to be efficiently solvable by ZDDs. I found out the hard way: see sud.c.
I began a Nurikabe solver but I have since been distracted.
14 years ago | master | logtree |