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 printunsatisfiable.
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
3 A B ~A B ~B C
satisfiable: A=F B=T C=T
2 A ~A
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")