Le problème des 8 reines

Il est souvent utile de bien analyser un problème avant de commencer la programmation de sa solution. Par exemple celui des 8 reines : il s'agit de positionner sur un échiquier (8 X 8 donc) 8 reines afin qu'elles ne se menacent pas l'une l'autre.

Aux échecs, la reine est la pièce la plus mobile. Elle peut se déplacer vers toute case de la ligne où elle se trouve, comme toute case de sa colonne ou des 2 diagonales se croisant sur son emplacement.

Si l'on considère que la première reine peut se trouver sur une case parmi 64, la seconde une sur 63, etc. on se rend compte que le nombre total de combinaisons, ainsi que celui des tests à effectuer, peut être énorme. L'idée de départ est donc d'éviter au maximum l'explosion combinatoire. Pour cela on énumère des règles pour la résolution du problème :

- Chaque reine sera seule sur sa ligne. Toute ligne sera occupée.

- Chaque reine sera seule sur sa colonne. Toute colonne sera occupée.

- Les lignes et colonnes seront numérotées de 1 à 8 pour le traitement (les colonnes sont normalement codées de A à H). Si X1,Y1 et X2,Y2 sont les coordonnées sur l'échiquier de 2 reines, elles seront sur la même diagonale si (X1 - X2) = (Y1 - Y2) ou (X1 - X2) = -(Y1 - Y2). Toute combinaison où cette condition est vérifiée pour 2 reines quelconques sera invalidée.

La solution choisie est d'employer un tableau de 8 chiffres, donnant les numéros des colonnes restant valables après les tests réalisés jusque là. Successivement pour chaque ligne de 1 à 8, on cherchera les colonnes utilisables (d'après les reines déjà placées) et chaque fois que l'une d'elles sera trouvée, elle sera notée dans un tableau résultat temporaire et enlevée du tableau des colonnes qui sera passé à l'appel suivant (récursif) de la procédure qui cherche les solutions. C'est en dépassant la ligne 8 (par 9 appels imbriqués) qu'une solution complète sera trouvée. Du fait qu'il y a un appel différent pour chaque ligne et que les numéros des colonnes occupées sont progressivement supprimés du tableau des possibilités restantes, le seul test nécessaire est celui des 2 diagonales. L'élimination progressive des colonnes minimalise le nombre total de tests.

J'ai écrit le programme en Turbo Pascal il y a quelques années. La recherche des 92 solutions au problème durait 5 secondes sur un PC de base (8088 à 4,77 MHz), les solutions étant stockées dans un tableau pour éviter les entrées-sorties.

{----------------------------------------------
      Résolution du problème des 8 reines
      Turbo Pascal
 ----------------------------------------------}

program Reines;

type    Colonnes        = array[1..8] of byte;

var     Resul,
        Combinaison     : Colonnes;
        Solutions       : array[1..100] of Colonnes;
        NbSolu          : integer;

procedure Initialisation;

var     i               : integer;

begin
NbSolu := 0;
for i := 1 to 8 do
    Combinaison[i] := i;
end;

procedure Chercher(var Possib : Colonnes; Ligne : integer);

var     NbResul,Nombre,
        i,j             : integer;
        Delta1,Delta2   : integer;
        Ok              : boolean;
        Trav            : Colonnes;

begin
if Ligne < 9 then
    begin
    Nombre := 9 - Ligne;
    NbResul := Ligne - 1;
    for i := 1 to Nombre do
        begin
        Ok := true;
        j := 1;
        while Ok and (j <= NbResul) do
            begin
            Delta1 := Ligne - j;
            Delta2 := Possib[i] - Resul[j];
            if (Delta1 = Delta2) or (Delta1 = -Delta2) then
                Ok := false;
            j := j+1;
            end;
        if Ok then
            begin
            Resul[NbResul + 1] := Possib[i];
            Trav := Possib;
            for j := i+1 to Nombre do
                Trav[j-1] := Trav[j];
            Chercher(Trav,Ligne + 1);
            end;
        end;
    end
else
    begin
    NbSolu := NbSolu + 1;
    Solutions[NbSolu] := Resul;
    end;
end;

function Verification : boolean;

var     i,j,k,NbCorres  : integer;
        Ok              : boolean;

begin
Ok := true;
for i := 1 to NbSolu-1 do
    begin
    for j := i+1 to NbSolu do
        begin
        NbCorres := 0;
        for k := 1 to 8 do
            begin
            if Solutions[i,k] = Solutions[j,k] then
                NbCorres := NbCorres + 1;
            end;
        if NbCorres = 8 then
            Ok := false;           { Ne doit jamais arriver }
        end;
    end;

Verification := Ok;
end;

procedure EcrireSolutions;

var     Sortie          : text;
        i,j             : integer;

procedure Graphique;

const   Separ           = '---+---+---+---+---+---+---+---+';

type    Echiquier       = array[1..8,1..8] of char;

var     Init,Trav       : Echiquier;
        i,j,k           : integer;

begin
for i := 1 to 8 do
    begin
    for j := 1 to 8 do
        Init[i,j] := ' ';
    end;

writeln(Sortie);
for i := 1 to NbSolu do
    begin
    Trav := Init;
    for j := 1 to 8 do
        Trav[j,Solutions[i,j]] := '@';
    writeln(Sortie,Separ);
    for j := 8 downto 1 do
        begin
        for k := 1 to 8 do
            write(Sortie,' ',Trav[j,k],' !');
        writeln(Sortie);
        writeln(Sortie,Separ);
        end;
    writeln(Sortie);
    end;
end;

begin
assign(Sortie,'Reines.txt');
rewrite(Sortie);

writeln(Sortie,NbSolu,' solutions trouvees');
writeln(Sortie);

for i := 1 to NbSolu do
    begin
    for j := 1 to 8 do
        write(Sortie,chr(ord('A') + Solutions[i,j] - 1),j,' ');
    writeln(Sortie);
    end;

{  Graphique;  }

close(Sortie);
end;

begin
Initialisation;
Chercher(Combinaison,1);
if Verification then
    EcrireSolutions
else
    writeln('Anomalie detectee : 2 solutions identiques');
end.