Le retour arrière est une approche algorithmique qui permet de résoudre efficacement un grand

nombre de problèmes combinatoires.

On va utiliser cette méthode pour résoudre le problème des n reines : étant donné un échiquier de

n x n cases, comment placer n reines sur cet échiquier de façon qu'aucune de ces reines ne soit prise

par les autres reines?

Ceci signifie, étant donné les règles de déplacement d'une reine aux échecs, que deux reines ne

pourront se retrouver ni sur une même ligne, ni sur une même colonne, ni sur une même diagonale.

Il n'existe pas de solutions pour , pour il en existe 2 et pour 8 reines, on trouve 92

solutions différentes.

Exemple: voici une solution possible pour

Cette solution est représentable par le tableau , la i -ème composante

donnant le numéro de la colonne de la dame située en i -ème ligne sur l'échiquier.

L'idée informelle du retour arrière consiste à placer les reines les unes après les autres, en

commençant par la première ligne jusqu'à la n -ième, et en considérant chaque colonne

l'une après l'autre.

Avant le placement de chaque reine, on vérifie que cette nouvelle reine n'est prise par aucune

des reines placées précédemment sur l'échiquier.

Si la nouvelle reine n'est pas prise par l'une des précédentes, on la place à la position considérée

et on avance à la ligne suivante. Si la reine qu'on vient de placer est la n -ième, on a obtenu une

solution au problème.

Si la nouvelle reine est prise par l'une des précédentes, on passe à la case suivante immédiatement

à droite sur la même ligne. S'il n'y a plus de position possible sur la ligne courante, ça signifie qu'il

n'existe aucune solution possible étant donné le placement des reines précédentes.

On doit remettre en cause la position des reines précédentes, ce qui est réalisé par le retour arrière.

Il s'agit de revenir à la ligne précédente et de trouver une nouvelle position pour la reine à partir

de celle qu'elle occupait précédemment. Si on trouve une nouvelle position, l'algorithme reprend

sa progression vers la ligne suivante, sinon on revient une nouvelle fois en arrière sur la ligne précédente.

Si on revient ainsi jusqu'à la première ligne et qu'il n'y a plus de position possible sur cette ligne, alors

c'est qu'il n'y a pas de solution au problème des n reines.

Pour mettre en oeuvre cet algorithme dans le cas général, on utilisera les variables globales

suivantes:

i : valeur de la ligne de la position courante.

j : valeur de la colonne de la position courante.

(on considérera que lorsque i et j deviennent nuls, l'algorithme s'arrête)

c : tableau de dimension permettant de représenter la disposition des n dames sur l'échiquier.

La valeur c [0] de ce tableau n'est utilisée par le programme que lorsque i et j deviennent nuls (test d'arrêt)

La valeur c [ k ] pour représente le numéro de la colonne de la dame située en k -ième ligne.

solutions : séquence contenant les différents tableaux représentant les solutions et mise à jour au cours

du programme.

1° Ecrire la procédure init( n :: posint) qui initialise les variables globales i , j , c , solutions :

est la position courante de départ.

toutes les composantes du tableau c sont mises à 0.

solutions est initialisée en une séquence vide.

2° Ecrire la procédure est_prise( l ::posint , c ::posint) retournant la valeur booléenne true ou false

suivant que la dame en position courante (ligne i , colonne j ) est prise ou non par la dame située en

ligne l , colonne c .

3° Ecrire la procédure est_OK() retournant la valeur booléenne true si i ) n'est

prise par aucune des dames précédemment placées (lignes 1 à ) et false dans le cas contraire.

4° Ecrire la procédure case_suivante() qui met à jour la colonne j de la position courante.

(on rappelle que la case suivante est située immédiatement à droite sur la même ligne)

5° Ecrire la procédure ligne_suivante() qui valide la position de la dame courante dans le tableau

c, c'est à dire c [ i ]= j , et qui fait passer à la première colonne de la ligne suivante.

6° Ecrire la procédure existe_alternative(n::posint) retournant la valeur booléenne true s'il

existe une alternative à l'étape courante et false dans le cas contraire.

(il existe encore une alternative à l'étape courante si la colonne de la position courante ne

dépasse pas n )

7° Ecrire la procédure retour_arriere(n::posint) qui consiste à remettre en cause le choix de

l'étape précédente: tant qu'il n'existe pas d'alternative, décrémenter la valeur i de la ligne courante

de 1, récupérer la valeur de position de cette ligne précédente( soit j = c [ i ] ). Puis passer à la

case suivante.

8° Ecrire la procédure est_au_debut() retournant la valeur booléenne true si i et j sont nuls et

false dans le cas contraire.

9° Ecrire la procédure solution_possible(n::posint) retournant la valeur booléenne true s'il existe

encore une solution possible et false dans le cas contraire.

position à considérer sur la ligne 1)

10° Ecrire la procédure est_solution(n::posint) retournant la valeur booléenne true si la

configuration courante est une solution au problème, et false dans le cas contraire.

(puisque chaque reine est ajoutée uniquement à une position correcte, la configuration courante

est une solution si i dépasse n avec )

11° Ecrire la procédure ajoute_solution(n::posint) qui ajoute à la séquence solutions la solution

que l'on vient de trouver.

12° Ecrire la procédure reines(n::posint) qui rend pour résultat la liste [ solutions ] de toutes les

solutions possibles au problème des n reines.

On utilisera les procédures écrites précédemment selon l'algorithme suivant:

procedure reines ( n )

initialiser les variables globales

tant que il existe une solution possible et on n'est pas au début faire

si la position est OK alors

passer à la ligne suivante

autrement

si il existe une alternative alors

passer à la case suivante

autrement

si il y a une solution possible, faire retour arrière fin(si)

fin(si)

fin(si)

si on a une solution alors l'ajouter fin(si)
fin(faire)

résultat [solutions]

fin(procedure)

13° Donner les solutions pour . Combien existe-t-il de solutions si ?

On se propose dans la suite de l'exercice de représenter les échiquiers solutions.

14° Ecrire la procédure grille(n::posint) qui représente un échiquier de n x n cases.

Exemple:

> plot(grille(6));

15° Ecrire la procédure dessin_reine(ligne::posint,colonne::posint,n::posint) qui représente une reine

dans la case ( ligne , colonne ) de l'échiquier n x n .

Exemple:

> dessin_reine(2,3,8);

16° Ecrire la procédure affiche_solutions(k::posint , n::posint) qui représente la k -ième solution

du problème des n reines.

Exemple:

> reines(8):affiche_solutions(1,8);

17° Représenter tous les échiquiers solutions du problème des 6 reines.

(d'après un T.P en langage Java donné à l'Université de Bretagne Sud.
L'énoncé d'origine a été pour l'essentiel conservé, certains passages ont été
modifiés pour une adaptation à Maple )

> restart;

> init:=proc(n::posint)
        global c,i,j,solutions;
        local k;
        i:=1;j:=1;
        solutions:=NULL;
        c:=array(0..n);
        for k from 0 to n do c[k]:=0 end do;
    end proc;

> est_prise:=proc(l::posint,c::posint)
        global i,j;
        evalb( l=i or c=j or (i-l=j-c) or (l-i=j-c) )
    end proc;

> est_OK:=proc()
        global c,i;
        local k;
        k:=1;
        while k<i do
            if est_prise(k,c[k]) then RETURN(false) end if;
            k:=k+1;
        end do;
        true
    end proc;

> case_suivante:=proc()
        global j;
        j:=j+1;
    end proc;

> ligne_suivante:=proc()
        global c,i,j;
        c[i]:=j;
        i:=i+1;j:=1;
    end proc;

> existe_alternative:=proc(n::posint)
        global j;
        evalb(j<n)
    end proc;

> retour_arriere:=proc(n::posint)
        global c,i,j;
        while not existe_alternative(n) do
            i:=i-1;
            j:=c[i];
        end do;
        case_suivante();
    end proc;

> est_au_debut:=proc()
        global i,j;
        evalb(i=0 and j=0)
    end proc;

> solution_possible:=proc(n::posint)
        global i,j;
        evalb(i>1 or (i=1 and j<=n))
    end proc;

> est_solution:=proc(n::posint)
        global i,j;
        evalb(i>n and j=1);
    end proc;

> ajoute_solution:=proc(n::posint)
        global solutions;
        local k;
        solutions:=solutions,[seq(c[k],k=1..n)];
    end proc;

> reines:=proc(n::posint)
        init(n);
        while solution_possible(n) and not est_au_debut() do
            if est_OK() then
                ligne_suivante()
            else
                if existe_alternative(n) then case_suivante() else
                    if solution_possible(n) then retour_arriere(n) end if;
                end if
            end if;
            if est_solution(n) then ajoute_solution(n) end if;
        end do;
        [solutions]
    end proc;

> reines(4);

> reines(6);

> reines(8);

> nops(%);

Donc 92 solutions possibles si .

haut de cette page