from collections import deque


def ac3(csp):
    queue = deque(csp.arcs())  # all (Xi, Xj) pairs with a constraint
    while queue:
        xi, xj = queue.popleft()
        if revise(csp, xi, xj):
            if not csp.domains[xi]:
                return False  # domain wiped out: no solution
            for xk in csp.neighbors(xi) - {xj}:
                queue.append((xk, xi))
    return True


def revise(csp, xi, xj):
    revised = False
    for x in set(csp.domains[xi]):
        if not any(
            csp.satisfies(xi, x, xj, y) for y in csp.domains[xj]
        ):
            csp.domains[xi].remove(x)
            revised = True
    return revised
