Safe Haskell	Safe-Inferred
Language	Haskell2010

TwoSat

Description

2-satisfiability

Solves the 2-sat problem, which assigns boolean values to variables (a, b, c...) such that it satisfies a boolean expression which is a conjunction of clauses, where each clause is a disjunction of two variables. For example, (a || b) && (a || not c) && (not b || not c). The solution is obtained from the strongly connected components of the implication graph constructed from the clauses.

Sources:

Synopsis

data Var
- = Id !Int
- | Not !Int
solve2Sat :: (Int, Int) -> [(Var, Var)] -> Maybe [Bool]

Documentation

data Var Source #

Constructors

Id !Int
Not !Int

Instances

Instances details

Show Var Source #
Instance details Defined in TwoSat Methods showsPrec :: Int -> Var -> ShowS # show :: Var -> String # showList :: [Var] -> ShowS #
NFData Var Source #
Instance details Defined in TwoSat Methods rnf :: Var -> () #

solve2Sat :: (Int, Int) -> [(Var, Var)] -> Maybe [Bool] Source #

Solves the 2-sat problem where each variable is represented by an Int in the range (l, r). Returns a list of assignments for the variables l to r, in order. O(n + m) where n = r - l + 1 and m = length xys.