2-sat
2SAT solver
npm install 2-sat
Want to see pretty graphs? Log in now!
16 | downloads in the last month |
Last Published By | |
---|---|
Version | 0.0.1 last updated 6 months ago |
License | MIT |
Keywords | 2SAT, 2, satisfiability, boolean, nl, complete |
Repository | git://github.com/mikolalysenko/2-sat.git (git) |
Bugs | https://github.com/mikolalysenko/2-sat/issues |
Dependencies | binary-search-bounds, strongly-connected-components |
Dependents | mikolalysenko-hoarders |
2-sat
2SAT is a restricted version of the boolean satisfiability problem where the number of variables per clause is at most 2. Works both in node.js and in the browser using browserify.
Example
var twoSat = require("2-sat")
//Solve problem:
//
// (x1 | !x2) & (x3 | x1) & (x3 | x2)
//
console.log(twoSat(3, [[1, -2], [3, 1], [3,2]]))
API
require("2-sat")(numVariables, clauses)
Finds a satisfying assignment for a 2SAT problem written in conjunctive normal form. If no assignment is possible returns false
.
numVariables
is the number of variablesclauses
is a list of binary clauses. Variables are indexed in clauses starting at1
and negative values indicate negation.
Returns A vector of assignments to the variables of the clause. If problem is not satisfiable, returns false
Credits
(c) 2013 Mikola Lysenko. MIT License