AI: The AC-3 algorithm

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 B with OP one of <, >, =, !=. Run AC-3 until no arc can remove anything.
  • Print NAME: values for each variable in the order given (values sorted), or only inconsistent if 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")

Lesson: Constraint propagation and AC-3 →