Un autre problème bien connu est le parcours du cavalier : comment faut-il faire jouer un cavalier sur un echiquier de façon à ce qu'il passe par toutes les cases de l'échiquier ?
On distingue 2 types de parcours pour le cavalier :
1) les parcours constituant un cycle fermé (c'est à dire que le cavalier, après avoir parcouru toutes les cases de l'échiquier se retrouve à la même position qu'au départ)
2) les parcours constituant un cycle ouvert (le cavalier part d'une case quelconque et après avoir parcouru les 63 cases restantes il se retrouve sur une autre position que celle de départ.
Le problème du cavalier, par rapport à celui du fou ou des reines, est qu'il demande un temps considérable pour être résolu, cela à cause du grand nombre de combinaisons possibles.
Nous allons voir deux manières de résoudre ce
problème.
Première solution
On considère l'échiquier comme un tableau en deux dimensions, représenté par la variable suivante : t : array[1..8,1..8] of byte.
Pour représenter les 8 directions, on s'aide de deux tableaux "t_x" et "t_y".
Quand le cavalier a sauté sur une case, alors la case est initialisée à 1, sinon à 0.
Un cavalier peut sauter dans 8 directions, mais le saut n'est pas toujours possible, notamment si le cavalier se trouve sur les bords de l'échiquier.
Pour chaque position du cavalier, on essaie les 8 directions; pour chaque direction possible, on met la case à 1 (simulation du saut), on sauvegarde la position dans un tableau et on fait un appel récursif; ensuite, une fois revenu, il faut annuler le coup, donc on remet la case à 0.
Voici le programme :
const t_x: array[1..8] of integer = (1, 2, 2, 1, -1, -2, -2, -1);
t_y: array[1..8] of integer = (-2, -1, 1, 2, 2, 1, -1, -2);
var t: array[1..8, 1..8] of byte; //--- l'échiquier
p: array[1..65] of integer; //--- mémorise les sauts consécutifs
s: string; //--- variable auxiliaire d'affichage
procedure remplir;
begin
fillchar(t, sizeof(t), 0);
end;
function on_peut_jouer(y, x, nr: byte): boolean;
begin
on_peut_jouer := false; inc(x, t_x[nr]); inc(y, t_y[nr]);if (x in [1..8]) and (y in [1..8]) then //--- si le cavalier est dans l'échiquier
on_peut_jouer := t[y, x] = 0; //--- et si la case n'est pas occupée
end;
procedure récursive(y, x, cpt: byte);
var a: byte;
begin
if cpt = 64 then
begins := '';
for a := 1 to 64 do s := s + inttostr(p[a]) + ';';
inc(nb);form1.edit1.text := 'solution numéro : ' + inttostr(nb) + ' : ' + s;
end elsefor a := 1 to 8 do
if on_peut_jouer(y, x, a) then begint[y + t_y[a], x + t_x[a]] := 1;
p[cpt] := x * 10 + y;
récursive(y + t_y[a], x + t_x[a], cpt + 1);
form1.edit2.text := inttostr(y + t_y[a]);t[y + t_y[a], x + t_x[a]] := 0;
end;
end;
procedure debut;
var ligne, colonne: byte;
begin
remplir;ligne := 1;
colonne := 1;
t[ligne, colonne] := 1;
récursive(ligne, colonne, 1);
t[ligne, colonne] := 0;
end;
procedure TForm1.Button1Click(Sender: TObject);
begin
debut;end;
Le problème de cette solution est qu'elle est extrêmement lente : le cavalier ne parcourt que 250.000 cases par minute.
Deuxième solution
Voici maintenant une deuxième solution beaucoup plus efficace :
on ne considère plus le parcours de l'échiquier comme un ensemble de cases devant être initialisées à 1 quand le cheval est passé dessus (et remise à 0 quand le cheval revient d'une descente récursive) mais comme un ensemble de liens; on numérote les cases de 1 à 64. Ainsi quand le cavalier saute de la case 1 à la case 11, on initialise le lien "1->11" avec la valeur 1, ensuite on initialise tous les liens arrivant en 11 avec la valeur 1 (ce sont "5->11","17->11","21->11","26->11","28->11"); ainsi, quand l'ordinateur arrivera sur l'une de ces cases, il ne prendra aucun de ces chemins. Le fait de couper à chaque mouvement les sauts possibles pour une case donnée fait que le nombre de possibilités est réduit (malgré cela, il est encore très grand) et le programme trouve des solutions beaucoup plus rapidement. A titre indicatif, la première solution est trouvée en quatre minutes sur un K6-350, au bout de 17 millions de sauts du cavalier. Dans cette version du programme, le cavalier parcourt 4,4 millions de cases par minute. Le gain de temps est énorme. Nous avons laissé tourner le PC pendant deux jours (ensuite nous l'avons arrêté); il a exploré 12 milliards de coups et a trouvé environ 9000 solutions.
Voici une représentation de l'échiquier utilisé dans cette version:
01 02 03 04 05 06 07
08
09 10 11 12 13 14 15 16
17 18 19 20 21 22 23
24
25 26 27 28 29 30 31
32
33 34 35 36 37 38 39
40
41 42 43 44 45 46 47
48
49 50 51 52 53 54 55
56
57 58 59 60 61 62 63 64
Si on saute de 1 en 11 alors les liens "05->11, 17->11, 21->11,26->11, 28->11" sont coupés; il faut les mémoriser avant le saut, pour les restaurer après, pendant la remontée des niveaux récursifs
Les autres structures de données nécessaires sont le tableau "nb_sauts", qui indique le nombre de sauts possibles pour chaque case de l'échiquier :
nb_sauts: array[1..64] of integer =
(2, 3, 4, 4, 4, 4, 3, 2,
3, 4, 6, 6, 6, 6, 4, 3,
4, 6, 8, 8, 8, 8, 6, 4,
4, 6, 8, 8, 8, 8, 6, 4,
4, 6, 8, 8, 8, 8, 6, 4,
4, 6, 8, 8, 8, 8, 6, 4,
3, 4, 6, 6, 6, 6, 4, 3,
2, 3, 4, 4, 4, 4, 3, 2);
pos_saut: array[1..64] of integer = // pour savoir à quelle position on doit
(1, 3, 6, 10, 14, 18, 22, 25, // chercher la case suivante lors d'un
27, 30, 34, 40, 46, 52, 58, 62, // saut;
65, 69, 75, 83, 91, 99, 107, 113, // on recherche la case suivante dans le
117, 121, 127, 135, 143, 151, 159, 165, // tableau "liens"
169, 173, 179, 187, 195, 203, 211, 217,
221, 225, 231, 239, 247, 255, 263, 269,
273, 276, 280, 286, 292, 298, 304, 308,
311, 313, 316, 320, 324, 328, 332, 335);
liens: array[1..336] of integer =
(11, 18, //----- liens "1->11", "1->18"
12, 17, 19, //----- liens "2->12", "2->17", "2->19"
9, 13, 18, 20,
10, 14, 19, 21,
...
On a un total de 336 sauts pour 64 cases, soit une moyenne de 5,25 sauts par case.
Et comme on a 64 cases à parcourir, alors le nombre total de possibilités est de 5,25 élevé à la puissance 64, soit 1,23*1046.
On utilise aussi des tableaux auxiliaires, comme "occupe" qui est un tableau de 336 booléens indiquant si un lien a déjà été visité ou pas. Pour chaque lien occupé (1->11) on occupe les liens allant vers 11. Mais une fois remonté, on les restaure; on a donc besoin de tableaux mémorisant les liens qu'on va occuper à chaque saut. Cette mémorisation s'effectue de la façon suivante :
por := 0;
for j := 1 to 336 do // on occupe les liens
if liens[j] = new_x then begin inc(por);po[por] := j;
oc[por] := occupe[j]; occupe[j] := true; end;
et la restauration des liens après le remontée récursive s'effectue de la manière suivante :
for j := 1 to por do occupe[po[j]] := oc[j];
procedure TForm1.Button4Click(Sender: TObject);
var num_saut, posit: integer;
procedure remplir1; beginfillchar(occupe, sizeof(occupe), #0);
end; procedure sauter(x, numero_saut: integer);var po: array[1..8] of integer;
oc: array[1..8] of boolean;
i, ii, j, k, m, por, new_x, c: integer; s1: string; begin inc(num_saut);if numero_saut > 63 then
begin memo1.lines.clear;memo1.lines.add('saut=' + inttostr(num_saut));
memo1.lines.add(soluce); memo1.refresh; exit; end;for i := 1 to nb_sauts[x] do
if not occupe[pos_saut[x] + i - 1] then
begin
c := pos_saut[x] + i - 1;
occupe[c] := true; // si x=1, "occupe[1]:=true" indique : lien "1->11" occupé
new_x := liens[c]; // new_x:=11,18
//--------- on occupe les liens
por := 0;
for j := 1 to 336 do
if liens[j] = new_x then begin inc(por);po[por] := j;
oc[por] := occupe[j]; occupe[j] := true;end;
//--------- appel récursif
s1 := inttostr(new_x) + ';';
soluce := soluce + s1;sauter(new_x, numero_saut + 1);
delete(soluce, length(soluce) - length(s1) + 1, length(s1));
//--------- restauration des liens occupées
for j := 1 to por do occupe[po[j]] := oc[j];
occupe[c] := false;
end;
end;begin // chercher solution
remplir1;
soluce := ''; num_saut := 1;
occupe[2] := true; // on interdit le saut "1->18" car symétrie avec "1->11"
posit := 1;
sauter(posit, 1);
end;
Télécharger le code source Delphi