# Path: simpleai/search/arc.py
# def all_arcs(constraints):
#     """
#     For each constraint ((X, Y), const) adds:
#         ((X, Y), const)
#         ((Y, X), const)
#     """
#     arcs = set()
# 
#     for neighbors, constraint in constraints:
#         if len(neighbors) == 2:
#             x, y = neighbors
#             list(map(arcs.add, ((x, y), (y, x))))
# 
#     return arcs
# 
# def revise(domains, arc, constraints):
#     """
#     Given the arc X, Y (variables), removes the values from X's domain that
#     do not meet the constraint between X and Y.
# 
#     That is, given x1 in X's domain, x1 will be removed from the domain, if
#     there is no value y in Y's domain that makes constraint(X,Y) True, for
#     those constraints affecting X and Y.
#     """
#     x, y = arc
#     related_constraints = [(neighbors, constraint)
#                            for neighbors, constraint in constraints
#                            if set(arc) == set(neighbors)]
# 
#     modified = False
# 
#     for neighbors, constraint in related_constraints:
#         for x_value in domains[x]:
#             constraint_results = (_call_constraint({x: x_value, y: y_value},
#                                                    neighbors, constraint)
#                                   for y_value in domains[y])
# 
#             if not any(constraint_results):
#                 domains[x].remove(x_value)
#                 modified = True
# 
#     return modified
# 
# def arc_consistency_3(domains, constraints):
#     """
#     Makes a CSP problem arc consistent.
# 
#     Ignores any constraint that is not binary.
#     """
#     arcs = list(all_arcs(constraints))
#     pending_arcs = set(arcs)
# 
#     while pending_arcs:
#         x, y = pending_arcs.pop()
#         if revise(domains, (x, y), constraints):
#             if len(domains[x]) == 0:
#                 return False
#             pending_arcs = pending_arcs.union((x2, y2) for x2, y2 in arcs
#                                               if y2 == x)
#     return True


import unittest
from operator import itemgetter
from simpleai.search.arc import all_arcs, revise, arc_consistency_3
        return arc_consistency_3(domains, constraints), domains

    def test_values_available_for_all_returns_true(self):
        result, domains = self.ac3([1, 2, 3], [1, 4, 9])
        self.assertTrue(result)

    def test_if_variable_has_no_domain_left_returns_false(self):
        result, domains = self.ac3([1, 2, 3], [2, 3, 6])
        self.assertFalse(result)

    def test_chained_revise_calls_remove_non_obvious_problems(self):
        # if A, B, C must be all different, with domains [1, 1], [1, 2], [2, 2] you
        # can't find a solution, but it requires several chained calls to
        # revise:
        # revise(A, B) -> ok!                      [1, 1] [1, 2] [2, 2]
        # revise(A, C) -> ok!                      [1, 1] [1, 2] [2, 2]
        # revise(B, C) -> fail, remove 2 from B    [1, 1] [1] [2, 2]
        #    and re-revise A, B and C, B
        # revise(A, B) -> fail, remove 1 from A    [] [1] [2, 2]
        #    and re-revise ...
        # here A has no more values, ac3 returns a failure

        domains = {'A': [1, 1],
                   'B': [1, 2],
                   'C': [2, 2]}
        different = lambda variables, values: len(set(values)) == len(variables)
        constraints = [(('A', 'B'), different),
                       (('A', 'C'), different),
                       (('B', 'C'), different)]


# Path: simpleai/search/arc.py
# def all_arcs(constraints):
#     """
#     For each constraint ((X, Y), const) adds:
#         ((X, Y), const)
#         ((Y, X), const)
#     """
#     arcs = set()
# 
#     for neighbors, constraint in constraints:
#         if len(neighbors) == 2:
#             x, y = neighbors
#             list(map(arcs.add, ((x, y), (y, x))))
# 
#     return arcs
# 
# def revise(domains, arc, constraints):
#     """
#     Given the arc X, Y (variables), removes the values from X's domain that
#     do not meet the constraint between X and Y.
# 
#     That is, given x1 in X's domain, x1 will be removed from the domain, if
#     there is no value y in Y's domain that makes constraint(X,Y) True, for
#     those constraints affecting X and Y.
#     """
#     x, y = arc
#     related_constraints = [(neighbors, constraint)
#                            for neighbors, constraint in constraints
#                            if set(arc) == set(neighbors)]
# 
#     modified = False
# 
#     for neighbors, constraint in related_constraints:
#         for x_value in domains[x]:
#             constraint_results = (_call_constraint({x: x_value, y: y_value},
#                                                    neighbors, constraint)
#                                   for y_value in domains[y])
# 
#             if not any(constraint_results):
#                 domains[x].remove(x_value)
#                 modified = True
# 
#     return modified
# 
# def arc_consistency_3(domains, constraints):
#     """
#     Makes a CSP problem arc consistent.
# 
#     Ignores any constraint that is not binary.
#     """
#     arcs = list(all_arcs(constraints))
#     pending_arcs = set(arcs)
# 
#     while pending_arcs:
#         x, y = pending_arcs.pop()
#         if revise(domains, (x, y), constraints):
#             if len(domains[x]) == 0:
#                 return False
#             pending_arcs = pending_arcs.union((x2, y2) for x2, y2 in arcs
#                                               if y2 == x)
#     return True


# Path: tests/search/test_arc_concistency.py
import unittest
from operator import itemgetter
from simpleai.search.arc import all_arcs, revise, arc_consistency_3

        return arc_consistency_3(domains, constraints), domains

    def test_values_available_for_all_returns_true(self):
        result, domains = self.ac3([1, 2, 3], [1, 4, 9])
        self.assertTrue(result)

    def test_if_variable_has_no_domain_left_returns_false(self):
        result, domains = self.ac3([1, 2, 3], [2, 3, 6])
        self.assertFalse(result)

    def test_chained_revise_calls_remove_non_obvious_problems(self):
        # if A, B, C must be all different, with domains [1, 1], [1, 2], [2, 2] you
        # can't find a solution, but it requires several chained calls to
        # revise:
        # revise(A, B) -> ok!                      [1, 1] [1, 2] [2, 2]
        # revise(A, C) -> ok!                      [1, 1] [1, 2] [2, 2]
        # revise(B, C) -> fail, remove 2 from B    [1, 1] [1] [2, 2]
        #    and re-revise A, B and C, B
        # revise(A, B) -> fail, remove 1 from A    [] [1] [2, 2]
        #    and re-revise ...
        # here A has no more values, ac3 returns a failure

        domains = {'A': [1, 1],
                   'B': [1, 2],
                   'C': [2, 2]}
        different = lambda variables, values: len(set(values)) == len(variables)
        constraints = [(('A', 'B'), different),
                       (('A', 'C'), different),
                       (('B', 'C'), different)]


        result = arc_consistency_3(domains, constraints)