Example implementation of AC3 and Path Consistency algorithm to solve for CSP

csp.py

arcs = {
    "a": {
        "b": lambda x, y: x != y,
        #"c": lambda x, y: x != y,
    },
    "b": {
        "a": lambda x, y: x != y,
        "c": lambda x, y: x != y,
    },
    "c": {
        #"a": lambda x, y: x != y,
        "b": lambda x, y: x != y,
    }
}

values = {
    "a": [1, 2],
    "b": [1, 2],
    "c": [1, 2],
}

queue = [
        ("a", "b"),
        ("b", "a"), ("b", "c"),
        ("c", "b"),
]
#queue = [
#        ("a", "b"), ("a", "c"),
#        ("b", "a"), ("b", "c"),
#        ("c", "a"), ("c", "b"),
#]

print(f"Initial values: {values}")


def ac3(queue):
    new_queue = []
    for arc in queue:
        for x in values[arc[0]]:
            at_least_one = False
            for y in values[arc[1]]:
                if arcs[arc[0]][arc[1]](x, y):
                    at_least_one = True

            if not at_least_one:
                print(f"removing {x} from {arc[0]}")
                values[arc[0]].remove(x)
                for ff in arcs[arc[0]]:
                    new_queue.append((ff, arc[0]))

    return list(set(new_queue))


def path_consistency(queue):
    def bind_values(ff, tt, third):
        at_least_one = False
        for x in values[ff]:
            for y in values[tt]:
                if not arcs[ff][tt](x, y):
                    continue
                for val in values[third]:
                    p1 = arcs[ff][third](x, val) if third in arcs[ff] else True
                    p2 = arcs[tt][third](y, val) if third in arcs[tt] else True
                    at_least_one |= p1 and p2
        return at_least_one

    for arc in queue:
        for third in arcs[arc[0]] | arcs[arc[1]]:
            if third == arc[0] or third == arc[1]:
                continue
            if not bind_values(arc[0], arc[1], third):
                return False
    return True


while len(queue) > 0:
    queue = ac3(queue)

queue = [
        ("a", "b"),
        ("b", "a"), ("b", "c"),
        ("c", "b"),
]
if path_consistency(queue):
    print(values)
else:
    print("Not solvable")