Run constraint propagation to a fixed point.
What to build
A program that makes a set of constraints arc consistent with AC-3.
Requirements
- Constraints have the form
A OP Bwith OP one of<,>,=,!=. Run AC-3 until no arc can remove anything. - Print
NAME: valuesfor each variable in the order given (values sorted), or onlyinconsistentif a domain becomes empty.
Input
Line 1: v. Then v lines NAME values…. Then c and c lines A OP B.
Output
The domains, or inconsistent.
Constraints
v ≤ 10, c ≤ 30, at most 20 values per domain.
Example
Input:
3
A 1 2 3
B 1 2 3
C 1 2 3
2
A < B
B < C
Output:
A: 1
B: 2
C: 3
Why it works
Every removal can take away the only support of values in neighbouring variables, so arcs are re-checked until nothing changes.
Examples
Example 1 · Input
3 A 1 2 3 B 1 2 3 C 1 2 3 2 A < B B < C
Expected output
A: 1 B: 2 C: 3
Example 2 · Input
3 A 1 2 B 1 2 C 1 2 3 A != B B != C A != C
Expected output
A: 1 2 B: 1 2 C: 1 2
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
Make two arcs for each constraint; for (Y, X) flip the relation (< becomes >).
Hint 2
When revising (X, Y) removes values, add back every arc (Z, X) with Z ≠ Y that is not already queued.
Solution
Show one correct solution (try it yourself first)
from collections import deque
order, domains = [], {}
for _ in range(int(input())):
name, *values = input().split()
order.append(name)
domains[name] = set(map(int, values))
TESTS = {"<": lambda a, b: a < b, ">": lambda a, b: a > b, "=": lambda a, b: a == b, "!=": lambda a, b: a != b}
FLIP = {"<": ">", ">": "<", "=": "=", "!=": "!="}
arcs = {}
for _ in range(int(input())):
a, op, b = input().split()
arcs.setdefault((a, b), []).append(TESTS[op])
arcs.setdefault((b, a), []).append(TESTS[FLIP[op]])
def revise(x, y):
removed = {vx for vx in domains[x] if not any(all(t(vx, vy) for t in arcs[(x, y)]) for vy in domains[y])}
domains[x] -= removed
return bool(removed)
queue = deque(arcs)
ok = True
while queue and ok:
x, y = queue.popleft()
if revise(x, y):
if not domains[x]:
ok = False
for z, w in arcs:
if w == x and z != y and (z, w) not in queue:
queue.append((z, w))
if ok:
for name in order:
print(f"{name}: {' '.join(map(str, sorted(domains[name])))}")
else:
print("inconsistent")