"""Authored finite domains with binary not-equal constraints; AC-3 is not a complete solver."""
from collections import deque
import itertools,json

def solutions(domains,edges):
    names=sorted(domains)
    return [dict(zip(names,vals)) for vals in itertools.product(*(sorted(domains[u])for u in names)) if all(dict(zip(names,vals))[u]!=dict(zip(names,vals))[v]for u,v in edges)]

def ac3(domains,edges):
    d={u:set(v)for u,v in domains.items()};neighbors={u:set()for u in d}
    if any(not v for v in d.values()):raise ValueError('initial domain must be nonempty')
    for u,v in edges:
        if u==v or u not in d or v not in d:raise ValueError('known distinct endpoints')
        neighbors[u].add(v);neighbors[v].add(u)
    q=deque(sorted(((u,v)for u in d for v in neighbors[u]),reverse=True));queued=set(q);trace=[]
    while q:
        u,v=q.popleft();queued.remove((u,v));removed=sorted(x for x in d[u]if not any(x!=y for y in d[v]))
        d[u].difference_update(removed);added=[]
        if removed and d[u]:
            for k in sorted(neighbors[u]-{v}):
                if (k,u)not in queued:q.append((k,u));queued.add((k,u));added.append([k,u])
        trace.append({'arc':[u,v],'removed':removed,'tail_domain':sorted(d[u]),'requeued':added,'queue_after':[list(x)for x in q]})
        if not d[u]:return {'nonempty_domains':False,'domains':{u:sorted(x)for u,x in d.items()},'trace':trace,'arc_consistent':False}
    supports=all(any(x!=y for y in d[v])for u in d for v in neighbors[u]for x in d[u]);assert supports
    return {'nonempty_domains':True,'domains':{u:sorted(x)for u,x in d.items()},'trace':trace,'arc_consistent':supports}

def demo():
    chain={'A':['red'],'B':['red','blue'],'C':['red','blue']};edges=[('A','B'),('B','C')]
    r=ac3(chain,edges);before=solutions(chain,edges);after=solutions(r['domains'],edges)
    assert r['domains']=={'A':['red'],'B':['blue'],'C':['red']} and before==after
    assert any(x['requeued']==[['C','B']]for x in r['trace']) and len(before)==1
    triangle={u:['red','blue']for u in ['A','B','C']};te=edges+[('A','C')];t=ac3(triangle,te);ts=solutions(triangle,te)
    assert t['nonempty_domains']and t['arc_consistent']and not ts and all(not x['removed']for x in t['trace'])
    impossible=ac3({'A':['red'],'B':['red']},[('A','B')]);assert not impossible['nonempty_domains']
    return {'binary_constraint':'not equal only, both directed arcs per undirected edge','authored_chain':{'initial_domains':chain,'edges':edges,'ac3':r,'independent_solutions_before':before,'independent_solutions_after':after},'authored_two_color_triangle':{'initial_domains':triangle,'edges':te,'ac3':t,'all_eight_assignments_checked':8,'independent_solutions':ts},'empty_domain_counterexample':impossible,'production_scheduler_or_generic_constraint_library_executed':False}

if __name__=='__main__':print(json.dumps(demo(),indent=2))