Simple SAT Solver written in Go
Switch branches/tags
Nothing to show
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Failed to load latest commit information.

go-sat: Simple Go SAT Solver

A simple SAT solver that can either use a recursive or an iterative algorithm. The algorithm uses a watchlist to keep track of all the assignments (see Knuth's SAT0W program).

Much of the code is based on the Python implementation by sahands, which can be downloaded here. He also wrote a nice explanatory article that can be viewed here.


No additional packages are required. Get this package as follows:

go get

Input syntax:

$ go run main.go -h
        Output all possible solutions (default true)                  
        Only output variables assigned true                           
  -i string                                                           
        Read from given file instead of stdin                         
        Use recursive algorithm instead of iterative                
  -starting_with string                                               
        Only output variables with names starting with the given string
        Verbose output (default true)              

The syntax for specifying a SAT problem is in Conjunctive Normal Forms (CNF). Each line represents a conjunct and consists of a sequence of literals separated by a space representing a disjunction of literals. Example:

a b c

Stands for (a OR b OR c) AND (NOT b) AND (NOT c), which has a single satisfying model, namely a=1, b=0, c=0.