Backtracking¶

class Contrainte:
    """ Modélisation d'une contrainte abstraite."""

    def __init__(self, variables):
        """
            :param list variables: les variables concernées par la contrainte.
        """

        self.variables = tuple(variables)

    def dimension(self):
        """
            :return: le nombre de variables concernées par la contrainte.
        """

        return len(self.variables)

    def est_valide(self):
        """ Teste si la contrainte est respectée par les valeurs actuelles.

            :return: ``True`` si la contrainte est valide.
        """

        return False

    def __repr__(self):
        return 'Contrainte: {}'.format(self.variables)

    def __eq__(self, that):
        return self.variables == that.variables

    def __hash__(self):
        return sum([v.__hash__ for v in self.variables])

class ContrainteUnaire(Contrainte):
    """ Contrainte imposant une restriction sur la valeur d'une variable.

        Exemples: ``x > 0``, ``y = 5``.
    """

    def __init__(self, var, op):
        """ Exemples d'op: ``lambda x: x > 5``, ``lambda x: x > 5 and x < 10``.

            :param var: variable concernée par la contrainte.
            :param op: fonction ou expression lambda permettant de vérifier la\
            contrainte.
        """

        Contrainte.__init__(self, (var,))
        self.op = op

    def est_valide(self, val):
        """ Teste si la contrainte est valide quand la variable ``var``\
            prend la valeur ``val``.

            La contrainte unaire est respectée si l'opérateur appliqué à\
            l'opérande ``val``  retourne ``True``.

            :return: ``True`` si la contrainte est valide.
        """
        return self.op(val)

class ContrainteBinaire(Contrainte):
    """ Contrainte imposant une restriction sur deux variables.

        Exemple: ``x > y``.
    """

    def __init__(self, var1, var2, op):
        """ Exemples d'op: ``lambda x,y: x != y``, ``lambda x,y: x < y``.

            :param var1: première variable concernée par la contrainte.
            :param var2: deuxième variable concernée par la contrainte.
            :param op: fonction ou expression lambda permettant de vérifier la\
            contrainte.
        """

        Contrainte.__init__(self, (var1, var2))
        self.op = op

    def est_valide(self, var, val):
        """ Teste si la contrainte est valide quand la variable ``var``\
            (soit ``var1``, soit ``var2``) prend la valeur ``val``.

            La contrainte unaire est respectée si l'opérateur appliqué aux\
            opérandes ``val, var2.val`` (lorsque ``var`` est ``var1``) ou\
            ``var1.val, val`` (lorsque ``var`` est ``var2``) retourne ``True``.

            :return: ``True`` si la contrainte est valide.
        """
        var1, var2 = self.variables

        if var1 == var:
            return self.op(val, var2.val)
        elif var2 == var:
            return self.op(var1.val, val)
        else:
            # var n'est pas une des variables de la contrainte.
            raise ValueError('Mauvaise variable: ' + var.nom + '. ' +
                             'On attendrait ' + var1 + ' ou ' + var2)

    def est_possible(self, var):
        """ Teste si le domaine de ``var`` contient au moins une valeur\
            satisfaisant la contrainte.

            :return: ``True`` s'il existe au moins une valeur satisfaisant\
            la contrainte.
        """
        if var not in self.variables:
            # var ne fait pas partie des variables de la contrainte
            var1, var2 = self.variables
            raise ValueError('Mauvaise variable: ' + var.nom + '. ' +
                             'On attendrait ' + var1 + ' ou ' + var2)

        for val in var.domaine:
            if self.est_valide(var, val):
                # Il suffit d'une valeur valide.
                return True

        # Aucune valeur val du domaine n'a retourné True pour
        # est_valide(var, val).
        return False

    def reviser(self):
        """ Algorithme de révision des domaines.

            Pour chaque variable, vérifie chaque valeur du domaine. Supprime\
            les valeurs qui empêchent la contrainte d'être satisfaite dans le\
            domaine.

            :return: ``True`` si un des domaines a été modifié.
        """
        domaines_modifies = False

        # reversed() retourne l'inverse d'une liste ou d'un tuple.
        # Les paires sont donc (var1, var2) et (var2, var1).
        # Les tuples ne sont pas identiques mais ils contiennent des références
        # sur les mêmes objets Variable (modifier var1 dans le premier tuple\
        # modifie var1 dans le second).
        for var1, var2 in (self.variables, reversed(self.variables)):
            ancienne_valeur = var1.val
            for val in var1.domaine[:]:
                var1.val = val

                if not self.est_possible(var2):
                    var1.domaine.remove(val)
                    domaines_modifies = True
            var1.val = ancienne_valeur

        return domaines_modifies

class PSC:
    def __init__(self, variables, contraintes):
        """
            :param list variables: les variables du problème.
            :param list contraintes: les contraintes du problème.
        """

        self.variables = variables
        self.contraintes = contraintes

        self.iterations = 0
        self.solutions = []

    def consistance_noeuds(self):
        """ Applique la consistance des noeuds sur les contraintes unaires du\
            problème.

            L'algorithme consiste à enlever des domaines de définition toutes\
            les valeurs qui violent les contraintes unaires.
        """
        for contrainte in self.contraintes:
            if contrainte.dimension() == 1:
                # Nous créons un nouveau domaine en ne gardant que les
                # valeurs valides.
                # Le plus simple est d'utiliser la `list comprehension' avec
                # une condition.
                contrainte.variables[0].domaine = [var for var in contrainte.variables[0].domaine if contrainte.est_valide(var)]

    def consistance_arcs(self):
        """ Applique la consistance d'arcs sur les contraintes binaires du\
            problème.
        """
        refaire = False
        for contrainte in self.contraintes:
            if contrainte.dimension() == 2 and contrainte.reviser():
                refaire = True

        if refaire:
            self.consistance_arcs()

    def consistance_avec_vars_precedentes(self, k):
        """ Vérifie si toutes les contraintes concernant les variables déjà\
            instanciées sont satisfaites.
        """
        for contrainte in self.contraintes:
            # Si la variables courante est concernée.
            if self.variables[k] in contrainte.variables:
                for i in range(k):
                    # Si n'importe laquelle des variables précédentes est concernée.
                    if self.variables[i] in contrainte.variables:
                        if contrainte.est_valide(self.variables[k], self.variables[k].val):
                            break
                        else:
                            return False
        # Toutes les contraintes sont valides.
        return True

    def backtracking(self, k=0, une_seule_solution=False):
        """ Algorithme de Backtracking simple.

            Tente d'assigner une valeur à chaque variable. Lors de chaque\
            assignation, vérifie que toutes les contraintes des variables\
            instanciées sont satisfaites. Sinon, revient en arrière pour essayer\
            une autre valeur.

            :param k: la profondeur de la recherche.
            :param une_seule_solution: indique à l'algorithme s'il faut\
            s'arrêter après avoir trouvé la première solution.
        """
        if len(self.solutions) == 1 and une_seule_solution:
            return

        self.iterations += 1
        # On est parvenu à une solution.
        if k >= len(self.variables):
            sol = {}
            for var in self.variables:
                sol[var.nom] = var.val
            if len(self.solutions) == 0 or not une_seule_solution:
                self.solutions.append(sol)
        else:
            var = self.variables[k]
            for val in var.domaine:
                var.val = val
                if self.consistance_avec_vars_precedentes(k):
                    # On continue l'algorithme sur la variable k+1.
                    self.backtracking(k=k+1, une_seule_solution=une_seule_solution)
            var.val = None

    def affiche_solutions(self):
        """ Méthode pour afficher les solutions découvertes par l'algorithme."""

        print('Recherche terminée en {} itérations'.format(self.iterations))

        if len(self.solutions) == 0:
            print('Aucune solution trouvée')
            return

        for sol in self.solutions:
            print('Solution')
            print('========')
            for (nom, var) in sorted(sol.items()):
                print('\tVariable {}: {}'.format(nom, var))