descriptionLogic puzzle solvers, using ZDDs.
homepage URLhttp://crypto.stanford.edu/pbc/notes/zdd/
ownerbenlynn@gmail.com
last changeSun, 29 Nov 2009 21:43:40 +0000 (29 13:43 -0800)
content tags
add:
readme

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.

shortlog
2009-11-29 Ben LynnMinor documentation edits.master
2009-11-29 Ben LynnAdded comments.
2009-07-30 Ben LynnAdded README. Improved Makefile.
2009-06-25 Ben LynnStarted nurikabe solver.
2009-06-20 Ben LynnCompute standard deviations in cycle_test.
2009-06-03 Ben LynnCompute average cycle length.
2009-06-03 Ben LynnDynamic allocation for zdd_count().
2009-06-03 Ben LynnAdded zdd_forlargest(). Improved cycle_test.
2009-06-03 Ben LynnHandle empty case.
2009-06-03 Ben LynnSlither Link solver fixes.
2009-06-02 Ben LynnImproved Slither Link solver.
2009-06-01 Ben LynnAllow computation on grid graphs larger than 11x11.
2009-06-01 Ben LynnAdded test finding simple cycles in grid graphs.
2009-06-01 Ben LynnSmoother drawings.
2009-06-01 Ben LynnSlight tweaks.
2009-06-01 Ben LynnSolves Slither Link.
...
heads
7 years ago master