Problème des n reines

Bien !

Changer le solveur

En effet on peut changer la fonction qui retourne la variable de branchement en ne prenant juste la première variable libre.

    def choose_var(self):
        for y in self.var:
            if self.assign[y] is None:
                return y
        return None

Et s’assurer que les valeurs du domaine de la variable de branchement sont pris dans l’orde.

        for u in sorted(self.var[x]):

Puis afficher la solution dans le format demandé.

sol = P.solve()
for i in N:
    print("%02i" % sol[i], end='')
print()

Recherche dichotomique

Une autre approche fait plusieurs appels au solveur, alors utilisé comme une boîte noire, et qui n’a pas à être modifié. Tout simplement on cherche pour la première variable quelle est la plus petite valeur qu’il peut avoir dans une solution. Pour cela divisez son domaine en deux et faites un test sur le domaine. Continuez avec le bon parmi les deux domaines.

def lexicographically_smallest_sol(C):
    L = sorted(x for x in C.var)   # les variables pris dans l'ordre
    for x in L:
        while len(C.var[x]) > 1:   # variable pas encore fixée
            k = len(C.var[x]) // 2
            D = sorted(C.var[x])   # les valeurs pris dans l'ordre
            D1 = D[:k]             # partitionner le domaine en deux
            D2 = D[k:]
            C.var[x] = D1
            if C.solve() is None:
                C.var[x] = D2      # garder le plus petit domaine 
    return C.solve()

suite