An efficient, embeddable DPLL SAT solver in Haskell
Other Haskell Other
Latest commit 6f0349f Jul 2, 2015 @dbueno explained changes
Permalink
Failed to load latest commit information.
bench-results/2008-05-07.1732 used bm results May 8, 2008
bench
doc corrected hackage link Jun 27, 2010
etc Merge branch 'master' of github.com:dbueno/funsat Jul 1, 2015
src made more concise Jul 2, 2015
tests Used new QC api Jul 2, 2015
website License note. Jul 4, 2008
.gitignore ignore swap and build stuff Jul 2, 2015
CHANGES
LICENSE Change licenses to BSD3 Apr 6, 2009
Main.hs
README explained changes Jul 2, 2015
README.benchmark
Setup.hs Refactor to prepare for release onto Hackage. Jun 6, 2008
benchmark.sh cleanup Jun 26, 2010
funsat.cabal
test.sh Add hash-bang header Apr 17, 2009

README

-*- mode: outline -*-

* Funsat: A DPLL-style SAT solver in pure Haskell

Funsat is a native Haskell SAT solver that uses modern techniques for solving
SAT instances.  Current features include two-watched literals, conflict-directed
learning, non-chronological backtracking, a VSIDS-like dynamic variable
ordering, and restarts.  Our goal is to facilitate convenient embedding of a
reasonably fast SAT solver as a constraint solving backend in other
applications.

Currently along this theme we provide /unsatisfiable core/ generation, giving
(hopefully) small unsatisfiable sub-problems of unsatisfiable input problems
(see "Funsat.Resolution").


* Installation
Install using the typical Cabal procedure:

    $ cabal configure
    $ cabal build

This will produce a binary called funsat at ./dist/build/funsat/funsat and a
standalone library interface for the solver.  If you feel like profiling the
code, a profiling binary is automatically built in
./dist/build/funsat-prof/funsat-prof.

** Testing

All the problems in tests/problems should run through.

  uf20 and uf50 - satisfiable
  uuf50 - unsatisfiable

** Dependencies
All the dependences are cabal-ised and available from hackage, or in etc/.

*** parse-dimacs
A haskell CNF file parser.

http://hackage.haskell.org/cgi-bin/hackage-scripts/package/parse-dimacs

*** bitset
http://hackage.haskell.org/cgi-bin/hackage-scripts/package/bitset