continue - Exercice

Les 8 dames .

Le problème

On veut placer 8 dames sur un échiquier 8 sur 8 de façon à ce qu'aucune dame ne puisse en prendre une autre.
On rappelle que deux dames ne sont pas en prise si elles ne sont pas sur une même rangée, c'est à dire si elles ne sont pas sur une même ligne, une même colonne ou une même diagonale.

Une représentation

On se propose d'obtenir les solutions sous la forme d'une chaîne de caractères telle que la suivante : '*15863724'.

Cette chaîne est à interpréter ainsi : la reine de la colonne 1 est en ligne 1, la reine de la colonne 2 est en ligne 5, la reine de la colonne 3 est en ligne 8...
L'étoile en début de chaîne ne sert qu'à numéroter plus "naturellement" les colonnes de 1 à 8 (plutôt que de commencer à l'indice 0).

On propose par ailleurs un affichage simple d'une telle solution :


def affiche(solu) :
	""" 
	Affichage d'une solution.
	La solution solu donnée en argument est sous la forme '*235...'
	"""
	print(' ',end=' ')
	for k in range(1,9) : print(k,end='|')
	print()
	for l in range(1,9) :
		print(l,end='|')
		for c in range(1,9) :
			if solu[c]==str(l) :
				print('R',end='|')
			else :
				print(' ',end='|')
		print()
		 
		
affiche('*15863724')

ce qui donne :

  1|2|3|4|5|6|7|8|
1|R| | | | | | | |
2| | | | | | |R| |
3| | | | |R| | | |
4| | | | | | | |R|
5| |R| | | | | | |
6| | | |R| | | | |
7| | | | | |R| | |
8| | |R| | | | | |

Un exemple de programme.


def ok(c) :
    """ c='*25456812' signifie 
    reine colonne 1, ligne 2;
    reine colonne 2, ligne 5; 
    reine colonne 3, ligne 4...
    Retourne True si reines non en prise."""
    
     
    for j in range(2,9) :
        for i in range(1,j) :
            if c[i]==c[j] : return False
            elif i+int(c[i])==j+int(c[j]) : return False
            elif i-int(c[i])==j-int(c[j]) : return False
    return True


def reine() :
    SOLUTIONS=[] # contiendra les solutions 
    L=['1','2','3','4','5','6','7','8'] # noms des colonnes
    for a1 in L :
        for a2 in L :
            for a3 in L :
                for a4 in L :
                    for a5 in L :
                        for a6 in L :
                            for a7 in L :
                                for a8 in L :
                                    sol='*'+a1+a2+a3+a4+a5+a6+a7+a8
                                    if ok(sol) : SOLUTIONS.append(sol)
    return SOLUTIONS
    
Liste=reine()
print("Nombre de solutions :", len(Liste))
affiche(Liste[0]) # grille correspondant à la première solution de la liste

On obtient :

Nombre de solutions : 92
  1|2|3|4|5|6|7|8|
1|R| | | | | | | |
2| | | | | | |R| |
3| | | | |R| | | |
4| | | | | | | |R|
5| |R| | | | | | |
6| | | |R| | | | |
7| | | | | |R| | |
8| | |R| | | | | |

Question

Après avoir réfléchi au fonctionnement du programme proposé, chercher à l'améliorer en utilisant continue. L'objectif est d'éviter un certain nombre de calculs inutiles.

A l'aide de compteurs, comparer le programme initial et votre proposition.

Résolution de l'exercice "les 8 dames".

Le principe de l'amélioration

L'idée est de tester à chaque niveau la validité d'une configuration. Il est en effet inutile de continuer la descente dans les boucles lorsque le début d'une configuration présente déjà des dames en conflit.

Proposition :


def ok(c) :
    """ c='*254' signifie 
    reine colonne 1, ligne 2;
    reine colonne 2, ligne 5; 
    reine colonne 3, ligne 4.
    Retourne True si reines non en prise.
    On teste seulement la dernière reine par rapport aux précédentes.
    """
    n=len(c)-1 # nb de reines
    rr=c[-1] # ligne de la reine à tester
    for i, r in enumerate(c) :
        if 0 < i < n :
            if r==rr : return False
            elif i+int(r)==n+int(rr) : return False
            elif i-int(r)==n-int(rr) : return False
    return True
 
def reineB() :
    SOLUTIONS=[] # contiendra les solutions 
    L=['1','2','3','4','5','6','7','8'] # noms des colonnes
    for a1 in L :
        sol='*'+a1
        for a2 in L :
            sol='*'+a1+a2
            if not(ok(sol)) : continue 
            for a3 in L :
                sol='*'+a1+a2+a3
                if not(ok(sol)) : continue 
                for a4 in L :
                    sol='*'+a1+a2+a3+a4
                    if not(ok(sol)) : continue 
                    for a5 in L :
                        sol='*'+a1+a2+a3+a4+a5
                        if not(ok(sol)) : continue 
                        for a6 in L :
                            sol='*'+a1+a2+a3+a4+a5+a6
                            if not(ok(sol)) : continue 
                            for a7 in L :
                                sol='*'+a1+a2+a3+a4+a5+a6+a7
                                if not(ok(sol)) : continue 
                                for a8 in L :
                                    sol='*'+a1+a2+a3+a4+a5+a6+a7+a8
                                    if not(ok(sol)) : continue 
                                    else : SOLUTIONS.append(sol)
    return SOLUTIONS

#################################################################

Liste=reineB()
print(len(Liste))

La comparaison des deux versions

Une première comparaison pourra consister à lancer les deux versions et à constater l'écart très net de temps d'exécution.

Avec des compteurs

Évaluons le nombre de positions testées :


def reineCompteur() :
    SOLUTIONS=[] # contiendra les solutions 
    L=['1','2','3','4','5','6','7','8'] # noms des colonnes
    cpt=0 # compteur de positions testées
    for a1 in L :
        for a2 in L :
            for a3 in L :
                for a4 in L :
                    for a5 in L :
                        for a6 in L :
                            for a7 in L :
                                for a8 in L :
                                    sol='*'+a1+a2+a3+a4+a5+a6+a7+a8
                                    cpt+=1
                                    if ok(sol) : SOLUTIONS.append(sol)
    return cpt
    
print(reineCompteur())

On obtient : 16 777 216.

Ce nombre peut s'évaluer directement : 8 boucles imbriquées, chacune parcourant 8 valeurs soit \( 8^8 = 16 777 216\) passages dans la boucle la plus profonde.

Avec la seconde version, comptons également le nombre d'appels à la fonction ok() :


def reineBCompteur() :
    SOLUTIONS=[] # contiendra les solutions 
    L=['1','2','3','4','5','6','7','8'] # noms des colonnes
    cpt=0 # compteur des positions testées, c'est à dire des appels à ok()
    for a1 in L :
        sol='*'+a1
        for a2 in L :
            sol='*'+a1+a2
            cpt+=1
            if not(ok(sol)) : continue 
            for a3 in L :
                sol='*'+a1+a2+a3
                cpt+=1
                if not(ok(sol)) : continue 
                for a4 in L :
                    sol='*'+a1+a2+a3+a4
                    cpt+=1
                    if not(ok(sol)) : continue 
                    for a5 in L :
                        sol='*'+a1+a2+a3+a4+a5
                        cpt+=1
                        if not(ok(sol)) : continue 
                        for a6 in L :
                            sol='*'+a1+a2+a3+a4+a5+a6
                            cpt+=1
                            if not(ok(sol)) : continue 
                            for a7 in L :
                                sol='*'+a1+a2+a3+a4+a5+a6+a7
                                cpt+=1
                                if not(ok(sol)) : continue 
                                for a8 in L :
                                    sol='*'+a1+a2+a3+a4+a5+a6+a7+a8
                                    cpt+=1
                                    if not(ok(sol)) : continue 
                                    else : SOLUTIONS.append(sol)
    return cpt

print(reineBCompteur())

On obtient 15 712 appels à la fonction ok()...

Backtrack

Le principe utilisé pour l'amélioration est le principe du backtrack. Une recherche sur un moteur de recherche vous renverra de nombreuses pages pour approfondir le sujet.