Bug 59: Who Watches The Watcher?
- This is a rudimentary Boolean satisfiability (SAT) solver that watches one literal per clause.
- The algorithm is nearly the same as Algorithm 188.8.131.52B from The Art of Computer Programming.
- A Boolean formula is provided in conjunctive normal form. Its variables are numbered 0, 1, ..., nvar-1.
- Literals are integers: The least-significant bit encodes the polarity; higher bits encode the variable.
- A literal with polarity bit 1 is negated. Such a literal is true if and only if its variable is false.
- Clauses are numbered 0, 1, ..., len(locs)-2. Each clause has one or more consecutive literals in lits.
- The first literal of clause i is lits[locs[i]] and the last literal of clause i is lits[locs[i+1]-1].
- The solver backtracks through partial assignments, rejecting any assignment that falsifies a clause.
- A satisfying assignment is returned as a slice of nvar integers, each integer 0 (false) or 1 (true).
- A nil slice is returned if and only if the formula is unsatisfiable.
Fix The Tiny Bug In This Go Code: