AI: A SAT solver

Write a solver for the problem behind chip verification and dependency resolution.

What to build

A program that decides whether a set of clauses can all be true, and if so finds the first such model.

Requirements

  • Each clause is a list of literals (a symbol, or ~ and a symbol) joined by "or". A model satisfies the set if every clause has at least one true literal.
  • Print satisfiable: A=F B=T … with the symbols in alphabetical order, choosing the first model when models are ordered with false before true for each symbol in turn; or print unsatisfiable.

Input

Line 1: c. Then c clauses, literals separated by spaces.

Output

One line.

Constraints

c ≤ 100; at most 20 symbols.

Example

Input:

3
A B
~A B
~B C

Output:

satisfiable: A=F B=T C=T

Why it works

Backtracking over symbols in order finds the first model, and unit propagation sets the values that every model below the current choice must have, so it prunes without skipping any model.

Examples

Example 1 · Input
3
A B
~A B
~B C
Expected output
satisfiable: A=F B=T C=T
Example 2 · Input
2
A
~A
Expected output
unsatisfiable

Prompts inside input() are ignored when checking, so input("n: ") is fine.

Hints

Hint 1

Branch on the symbols in alphabetical order, trying false before true, and simplify the clauses after each choice.

Hint 2

Unit propagation: a clause with one unassigned literal and all others false forces that literal; an all-false clause means back up.

Solution

Show one correct solution (try it yourself first)
clauses = [input().split() for _ in range(int(input()))]
names = sorted({lit.lstrip("~") for clause in clauses for lit in clause})


def value(lit, model):
    v = model.get(lit.lstrip("~"))
    return None if v is None else (not v if lit.startswith("~") else v)


def propagate(model):
    changed = True
    while changed:
        changed = False
        for clause in clauses:
            values = [value(lit, model) for lit in clause]
            if True in values:
                continue
            open_lits = [lit for lit, v in zip(clause, values) if v is None]
            if not open_lits:
                return False
            if len(open_lits) == 1:
                lit = open_lits[0]
                model[lit.lstrip("~")] = not lit.startswith("~")
                changed = True
    return True


def solve(model):
    model = dict(model)
    if not propagate(model):
        return None
    free = [n for n in names if n not in model]
    if not free:
        return model
    for choice in (False, True):
        found = solve({**model, free[0]: choice})
        if found:
            return found
    return None


model = solve({})
if model:
    print("satisfiable: " + " ".join(f"{n}={'T' if model[n] else 'F'}" for n in names))
else:
    print("unsatisfiable")

Lesson: Propositional logic →