150p4

# -*- coding: utf-8 -*-
__author__ = 'Please write your names, separated by commas.'
__email__ = 'Please write your email addresses, separated by commas.'

from collections import deque


def ac3(csp, arcs=None):
    """Executes the AC3 or the MAC (p.218 of the textbook) algorithms.

    If the parameter 'arcs' is None, then this method executes AC3 - that is, it will check the arc consistency
    for all arcs in the CSP.  Otherwise, this method starts with only the arcs present in the 'arcs' parameter
    in the queue.

    Note that the current domain of each variable can be retrieved by 'variable.domains'.

    This method returns True if the arc consistency check succeeds, and False otherwise."""

    queue_arcs = deque(arcs if arcs is not None else csp.constraints.arcs())

    while not queue_arcs:
        (xi, xj) = queue_arcs.pop()
        print xi
        print xj
        if revise(csp, xi, xj):
            if len(xi.domain) == 0:
                return False
            for xk in csp.constraints[xi]:
                if xk != xj:
                    queue_arcs.append(xk, xi)
    return True


def revise(csp, xi, xj):
    # You may additionally want to implement the 'revise' method.
    revised = False
    for x in xi.domain:
        for y in xj.domain:
            if not xi.is_satisfied(x, y):
                xi.domain.remove(x)
                revised = True
    return revised