Placement de reines sur un échiquier

Le placement de reines sur un échiquier sans qu'aucune d'entre elles ne soit en prise par une autre constitue un autre exemple de recherche arborescente. Là encore il faut parcourir l'ensemble des solutions possibles. Pour les valeurs successives de i, on place une reine sur la ligne i et sur une colonne j = pos[i] en vérifiant bien qu'elle n'est pas en prise. Le tableau pos que l'on remplit récursivement contient les positions des reines déjà placées. Tester si deux reines sont en conflit est relativement simple. Notons et leurs positions respectives (ligne et colonne) il y a conflit si (elles sont alors sur la même ligne), ou si (même colonne) ou si (même diagonale).

function Conflit (i1, j1, i2, j2: integer): boolean;
    begin
    Conflit := (i1 = i2) or (j1 = j2) 
            or (abs (i1 - i2) = abs (j1 - j2));
    end;

Celle-ci peut être appelée plusieurs fois pour tester si une reine en position i, j est compatible avec les reines précédemment placées sur les lignes :

function Compatible (i, j: integer): boolean;
    var k: integer;
        c: boolean;
    begin
        c := true;
        k := 1;
        while c and (k < i) do
            begin
            c := not Conflit (i, j, k, pos[k]);
            k := k + 1
            end;
        Compatible := c;
    end;

  
Figure: Huit reines sur un échiquier

La fonction récursive qui trouve une solution au problème des reines est alors la suivante:

procedure Reines (i: integer)
    begin
    if i > Nreines then
        Imprimer_Solution
    else
        begin
        for j:= 1 to Nreines do 
        if Compatible (i,j) then 
            begin
            pos[i] := j;
            Reines(i+1)
            end;
        end;
    end;

La boucle for à l'intérieur de la procédure permet de parcourir toutes les positions sur la ligne i compatibles avec les reines déjà placées. Les appels successifs de Reines(i) modifient la valeur de pos[i] déterminée par l'appel précédent. La procédure précédente affiche toutes les solutions possibles, il est assez facile de modifier les procédure en s'arrêtant dès que l'on a trouvé une solution ou pour simplement compter le nombre de solutions différentes. On trouve ainsi solutions pour un échiquier dont l'une d'elles est donnée figure .

• Remarque