Tutoriel pour
C++ Builder
C++ pour tout ce qui est
graphique, assembleur pour le calcul pur
Le cavalier hamiltonien
par Gilles
Louise
On appelle chemin hamiltonien, du nom du grand mathématicien
Hamilton, un chemin particulier qui dans une avancée couvre l’ensemble
des points en présence sans repasser par une position visitée. Ce
sera le cas du cavalier qui chevauche l'ensemble de l'échiquier
sans passer deux fois par la même case.
L'algorithme est très simple : il suffit de
choisir à chaque fois le coup qui offre le plus petit nombre de
possibilités différent de zéro (car zéro correspond au cul-de-sac).
Ce principe est tellement puissant que le cavalier trouve tout de
suite une première solution sans avoir à faire marche arrière, donc
sans se tromper, quelle que soit la case de départ choisie (à quelques
rares exceptions près e.g. la case A3 où la première solution n'est
pas immédiate mais très rapide quand même). Ceci peut se comprendre
intuitivement. Il faut attirer le cavalier vers les coins. En effet,
à partir de la case A1 par exemple, il n'y a que deux possibilités,
la case C2 et la case B3. Si donc le cavalier arrive par exemple
en C2, il faut absolument qu'il choisisse A1, il ressortira alors
en B3 alors que si, de C2 le cavalier opte pour une autre direction,
la case A1 risque de passer définitivement aux oubliettes. Ainsi
le cavalier a tendance à tourner autour de l'échiquier en privilégiant
le choix des coins. Ayant trouvé une solution, le cavalier recule
et essaie les autres chemins historisés qu'il n'a pas pris. Mais
comme toute la structure de base est correcte puisque ce principe
est adopté à chaque coup, le cavalier avance à nouveau facilement
et trouve bien d'autres solutions.
L'échiquier est une zone de 120 octets, 12x10. Les
cases de l'échiquier sont entourés de deux couches de 0xff (255
en décimal) qui est le code hors échiquier. Deux couches sont nécessaires
à cause précisément du cavalier, en cas de sortie de l'échiquier,
il pointe nécessairement une case dont le contenu est 255. Cela
évite tout simplement de faire les quatre tests concernant x et
y, x>=1 et x<=8 et y>=1 et y<=8. En un seul test, on
sait si le cavalier est hors échiquier ou non. Cela dit, dans le
cadre de ce programme, on testera seulement 0 ou non, 0 signifiera
case libre et non 0 signifiera case non accessible (soit parce qu'elle
est hors échiquier, soit parce qu'elle est déjà utilisée).
Echiquier db
255,255,255,255,255,255,255,255,255,255
db 255,255,255,255,255,255,255,255,255,255
db 255,
0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 ,255
db 255,
0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 ,255
db 255,
0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 ,255
db 255,
0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 ,255
db 255,
0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 ,255
db 255,
0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 ,255
db 255,
0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 ,255
db 255,
0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 ,255
db 255,255,255,255,255,255,255,255,255,255
db 255,255,255,255,255,255,255,255,255,255
Nous décidons que la case A1 se trouve à l'adresse
Echiquier+21, soit la première case nulle à partir de l'adresse
Echiquier. Si esi pointe une case de l'échiquier, ajouter 10 nous
fait avancer d'une case verticalement (rangée), soustraire 10 nous
fait reculer d'une case verticalement, ajouter 1 nous fait avancer
d'une case horizontalement (colonne), soustraire 1 nous fait reculer
d'une case horizontalement. On déclare comme suit les huit directions
du cavalier.
DirC dd 8, -2, 1
dd 12, 2, 1
dd 19,
-1, 2
dd 21, 1, 2
dd -8, 2,
-1
dd -12, -2,
-1
dd -19, 1,
-2
dd -21, -1,
-2
C'est un double tableau, chaque direction tient sur
trois nombres de 32 bits (donc 12 octets pour une direction). Le
premier nombre indique l'offset du point de vue de l'échiquier,
les deux autres nombres correspondent aux offsets en x et y et seront
utilisés pour les calculs. Ces deux notations se rejoignent puisque
10 fois le troisième nombre plus le deuxième donne le premier, c'est
pour éviter d'avoir à recalculer sans cesse la même chose que nous
mettons ces valeurs à notre disposition. Ainsi, si esi pointe l'échiquier,
on testera le contenu de esi+valeur1 (offset d’échiquier) pour une
direction donnée. On déclare une zone de 128 octets qui contiendra
le chemin emprunté par le cavalier, c'est une suite de 64 couples
(x,y).
char
Chemin[128];
Du fait qu'on utilisera cette zone dans le code C++
par une syntaxe du type Chemin[i] pour écrire dans le bitmap hors
écran le numéro des coups dans les cases graphiques, cette déclaration
se fait en C++ et non en assembleur. Chaque couple contiendra les
coordonnées (x,y) de la case, x et y étant compris entre 0 et 7.
Ainsi (0,0) correspondra à la case A1 et (7,7) à la case H8. Le
premier nombre désigne le nombre de colonnes à ajouter horizontalement
et le second le nombre de cases à ajouter verticalement. Ce choix
est arbitraire, nous respectons simplement la notation algébrique
des cases. Le premier couple contiendra la case de départ (x,y).
Quand un coup sera choisi, il correspondra obligatoirement à une
des huit directions possibles. Comme chaque direction donne les
offsets en x et y, on ajoutera tout simplement ces offsets pour
obtenir la nouvelle position du cavalier. Par exemple, imaginons
que le cavalier soit sur la case D2 soit (3,1) et que le coup choisi
corresponde à la direction -8, on voit que les offsets correspondant
à -8 sont 2 et -1 (car –1*10+2=-8), donc pour obtenir la case qui
sera écrite dans la zone Chemin, on ajoutera les offsets respectifs
en x et y à la position courante soit 3+2=5 et 1-1=0, la case est
donc (5,0) soit F1. Ensuite, on écrira un 1 dans la zone Echiquier
correspondant à cette case. Comme NbCoups est égal au nombre de
coups présents dans Chemin, on calculera d’abord l’adresse Chemin+NbCoups*2
qui contient sur deux octets consécutifs la case où se trouve pour
l’instant le cavalier. On lira le contenu à adresse suivante qui
contient l'offset en y, on multipliera par 10, on ajoutera le contenu
de la case précédente qui contient l'offset en x. Ce calcul équivaut
à 10y+x. On obtient ainsi l’offset absolu à ajouter à Echiquier+21
pour obtenir la case de l’échiquier correspondante, on y écrira
un 1. Au moment d’un recul, on procédera au même calcul à cela près
qu’on écrira 0 dans la case de l’échiquier, ce qui aura pour effet
de libérer la case. On déclare une zone historique constitué de
63 fois LigHisto octets.
Histo db LigHisto*63
dup(?)
LigHisto (ligne d'historique) est une constante égale
à 33. Pour chaque coup, il y aura donc une zone historique de LigHisto
soit 33 octets soit au maximum, huit fois une série de quatre octets
plus un code fin 255 (8*4+1=33). Le premier octet de chaque série
sera l'offset calculé comme possible, les deux suivants les offsets
en x et y pour nous éviter d'avoir à en faire la recherche et le
dernier octet de ces séries de quatre sera le nombre de coups possibles
disponibles si le coup de cette série était joué. La méthode est
donc simple. À partir de la case de départ, on cherche tous les
coups possibles et on les historise ainsi. Ensuite, on cherche dans
l'historique le coup associé à un nombre (le quatrième nombre de
chaque série de quatre octets) minimum non nul, on joue ce coup
considéré comme le meilleur et on le supprime de l'historique pour
qu'il ne soit pas rejoué si le pointeur historique retombe à ce
niveau-là. Pour supprimer un coup de l'historique, il suffit de
mettre son offset à 0 c'est-à-dire le premier octet de la série
à annuler. On continue ainsi. Quand on arrive à un cul-de-sac (ou
à une solution qui est un cul-de-sac particulier), on recule en
cherchant dans l'historique s'il y a d'autres possibilités. Si non,
on recule encore jusqu'à en trouver. Si on en trouve, on est certain
que le coup choisi sera différent étant donné que les coups joués
sont effacés de l'historique. Le cavalier avance donc à nouveau
avec un nouveau coup non encore essayé jusqu'à nouvelle solution
ou cul-de-sac. Par cette méthode, on épuise toutes les combinaisons
possibles.
Le dialogue entre le C++ (graphique) et l’assembleur
(calcul) se fait via les variables déclarées en C++. Quand une variable
est déclarée en C++, elle est accessible à l’assembleur mais la
réciproque est plus difficile voire fausse, les zones déclarées
en assembleur ne sont accessibles qu’au seul assembleur (ou alors
il faudrait user de syntaxes ou de techniques inhabituelles en C++
et inutiles). C’est pourquoi nous avons déclaré trois zones mémoire
en assembleur, l’échiquier, les directions du cavalier et l’historique
car ces zones n’ont pas besoin d’être accédées par le code C++.
En revanche, le chemin choisi par le cavalier est déclaré par une
déclaration C++ de type char[] car le C++ a besoin de lire cette
zone pour convertir les coordonnées (x,y) de passage du cavalier
en coordonnées graphiques d’affichage. Dans les variables générales
(situées après les "include" et avant la toute première fonction
qui est par défaut le constructeur TForm1::TForm1), on a déclaré
successivement le pointeur de TForm1 (en fait c’est C++Builder qui
a écrit lui-même cette ligne dans la partie créée automatiquement),
le pointeur de bitmap BM, la zone Chemin, une zone de trois caractères
(deux caractères et un code fin) qui contiendra la case de départ,
le nombre de coups, le nombre de solutions et un pointeur sur l’historique.
TForm1 *Form1;
Graphics::TBitmap *BM;
char Chemin[128];
char Depart[3];
char NbCoups;
int NbSol;
char *pHisto;
L’affichage est d’abord créé dans un bitmap donc
en hors écran. Ce bitmap est créé par new dans le constructeur de
TForm1, on utilise généralement ce constructeur pour initialiser
l’application. On initialise ses dimensions à celles de l’écran
avec Screen->Width/Height.
BM=new Graphics::TBitmap();
BM->PixelFormat=pf4bit;
BM->Width=Screen->Width;
BM->Height=Screen->Height;
C’est un bon principe de dimensionner au maximum
un bitmap hors écran, cela évite d’avoir à modifier ses dimensions
en cas de resize de la fenêtre. On n’utilise qu’un bitmap à quatre
bits par pixel (pf4bit), ce qui est suffisant pour notre problème,
l’affichage n'en sera que plus rapide. C’est dans la méthode OnActivate
de Form1 que le programme va réellement se dérouler. On commence
par demander à l’utilisateur d’entrer la case de départ.
Rep=0;
while(!Rep)
{
/* entrée de la case de départ */
CasDep = InputBox(Msg[0],Msg[1],"");
/* si rien, Rep=1 */
if (!CasDep.Length()) Rep=1;
/* si quelque chose, test de la validité de la saisie
*/
if ( CasDep.Length()==2
&& CasDep[1]>='A'
&& CasDep[1]<='H'
&& CasDep[2]>='1'
&& CasDep[2]<='8') Rep=2;
}
La variable CasDep est un AnsiString local à la méthode
OnActivate. On boucle jusqu’à ce que l’utilisateur ait entré quelque
chose de correct, soit rien auquel cas Rep=1 soit quelque chose
de correct, une lettre entre A et H et un chiffre entre 1 et 8 auquel
cas Rep=2. Sinon, si Rep est toujours à zéro après cette tentative,
la saisie n’est pas correcte et la boucle en while continue, on
redemande donc à l’utilisateur une entrée correcte. Au sortir de
cette boucle en while, de deux choses l’une, ou bien Rep=1 auquel
cas l’utilisateur n’a rien saisi et l’on sort simplement de l’application
sinon Rep=2 et le calcul va commencer.
if(Rep==1) Close();
else Cavalier(CasDep,Sender);
La fonction Cavalier reçoit en argument l’AnsiString
qui contient la case de départ et le Sender nécessaire car il faudra
appeler la méthode OnPaint de Form1, cette méthode a besoin de connaître
le Sender. Comme CasDep a maintenant deux caractères corrects, on
recopie cet AnsiString dans la variable générale Depart.
strcpy(Depart,CasDep.c_str());
À noter la méthode très utile c_str() qui convertit un AnsiString en char* à zéro terminal.
Dans ces conditions, Depart[0] sera la lettre compris entre A et
H et Depart[1] sera le chiffre compris entre 1 et 8. On appelle
le sous-programme assembleur CalOCD qui calcule les offsets en x
et en y de la case de départ et les enregistre au début de la zone
Chemin. On lit dans le registre 8 bits al la première case Depart[0]
(mov al,Depart), on soustrait 65 qui est
le code ascii de la lettre A (sub al,65), al contient alors une valeur entre 0 et
7, 0 pour A, 1 pour B etc. puis enfin on écrit le résultat dans
la toute première case de la zone Chemin (mov Chemin,al). Puis on lit dans al le chiffre Depart[1]
(mov al,Depart+1), on soustrait
49 qui est le code ascii du chiffre 1 (sub al,49), al contient donc une valeur compris entre
0 et 7, 0 pour 1, 1 pour 2 etc. puis on enregistre le résultat al
dans la deuxième case de la zone Chemin (mov Chemin+1,al). On termine par ret (return) comme tout sous-programme, on retourne ainsi
à l’appelant. Donc, après exécution de ce sous-programme, Chemin
contient au début la case choisie par l’utilisateur entre (0,0)
et (7,7).
CalOCD: mov al,Depart
sub
al,65
mov
Chemin,al
mov
al,Depart+1
sub
al,49
mov
Chemin+1,al
ret
La case de départ étant maintenant renseignée dans
Chemin, on peut afficher l’état de l’échiquier qui contiendra le
chiffre 1 dans cette case, on dessine donc le bitmap
Dessine(S);
où S est le Sender de type TObject* nécessaire car
cette fonction va appeler le OnPaint de Form1 (fenêtre principale)
dès que le bitmap aura été dessiné. La suite de la fonction Cavalier
se constitue d’une boucle générale contenant deux moments, l’avance
en boucle et le recul en boucle. Le schéma algorithmique général
de cette boucle est
do
{
avance jusqu’à cul-de-sac
recule jusqu’à réavance possible
}
while(NbSol !=Solutions) ;
où Solutions est une constante déclarée en début
de programme. Nous l’avons positionnée à 10 donc le programme affichera
les dix premières solutions. On voit donc que la boucle générale
inclut elle-même deux sous-boucles, une sous-boucle d’avance et
une sous-boucle de recul. La sous-boucle d’avance se constitue de
deux parties, la première en assembleur qui cherche et joue le meilleur
coup et la deuxième qui dessine et affiche le coup.
do
{
asm
{
call Joue
mov AvanceOK,dh
}
Dessine(S);
}
while(AvanceOK) ;
Le sous-programme Joue renvoie dans dh une indication,
c’est une sorte de flag. La position de ce flag est copiée dans
la variable AvanceOK et le while de la boucle décidera s’il faut
continuer à avancer ou non. Si dh<>0 (true) on continuera,
si dh=0 (false) on arrêtera la boucle en while et ce, parce qu’on
est tombé sur un cul-de-sac ou une solution. Après cette avancée
maximale, on interroge la variable NbCoups. Si NbCoups est égal
à 63, cela signifie qu’une solution a été trouvée, on affiche simplement
un MessageBox, ce qui nous laissera le temps de consulter la solution
à l’écran.
if(NbCoups==63)
{
AnsiString A;
A="Solution numéro "+IntToStr(++NbSol);
Application->MessageBox(A.c_str(),"Solution",MB_OK);
}
Ensuite, on positionne la variable booléenne ReculeOK
en fonction du fait qu’on a atteint le nombre de solutions demandées
ou non.
ReculeOK=(NbSol != Solutions)
ReculeOK sera vrai si on n’a pas atteint le nombre
de solutions à afficher, la variable autorisera alors le recul.
Cette méthode permet d’avoir une solution complète à l’écran au
moment où le programme s’arrêtera, si on ne prenait pas cette petite
précaution, nous n’aurions qu’une solution partielle affichée à
la fin de l’exécution de la méthode OnAvtivate. Nous nous arrêtons
après avoir affiché un nombre arbitraire de solutions car il y a
probablement des milliards de solutions pour une case de départ
donnée, le programme ne s'arrêterait jamais. Dans ces conditions,
le recul se passe comme suit :
while(ReculeOK)
{
asm
{
call Recule
mov ReculeOK,al
}
Dessine(S);
}
On utilise une structure en while car il se peut
que nous ne reculions pas. C’est ce qui se produit quand la dernière
solution est trouvée (car on n'affiche qu'un petit nombre de solutions,
voir constante Solutions en en-tête du cpp), on empêche ce recul
de manière à avoir une solution complète d’affichée (alors que pour
l’avance nous avons utilisé une structure en do car nous étions
sûrs d'avoir à avancer au moins une fois). De la même façon que
pour l’avance, le sous-programme assembleur Recule renvoie une indication
mais dans al qui dira s’il faut continuer le recul ou non. Si al<>0
(true), on continuera le recul parce qu’aucun coup n’a été trouvé
dans le groupe historique correspondant au numéro de coup traité
NbCoups. Si al=0 (false), l’historique pour ce coup n’est pas vide,
il existe donc au moins un coup à jouer, on cesse donc de reculer
pour jouer un coup résiduel de l’historique. À chaque fois, on appelle
la fonction Dessine, ce qui aura pour effet de vider la case libérée
par le recul. En effet, bien que les coups joués restent dans la
zone Chemin (ils ne sont pas effacés de cette zone suite à un recul),
la seule décrémentation de NbCoups suffit à faire reculer graphiquement
le cavalier puisque le graphique se redessine chaque fois à partir
de rien. On sait qu’il y a à tout moment NbCoups+1 coordonnées dans
la zone Chemin. Le graphique consiste à écrire les nombres allant
de 1 à NbCoups+1 dans les cases visées. Si NbCoups est décrémenté,
le dernier nombre n’apparaît plus, cela donne donc l’impression
d’un recul du cavalier.
Voici comment nous recherchons les coups possibles
dans une position donnée. Deux variables sont importantes, NbCoups
et la zone Chemin. En effet, à l’adresse Chemin+NbCoups*2 se trouve
la position du cavalier et l’on va enregistrer les coups dans l’historique
à partir de l’adresse Histo+NbCoups*LigHisto, c’est l’adresse de
la première case du groupe de LigHisto cases correspondant au coup
numéro NbCoups. Première chose, on calcule cette adresse, on fait
pointer esi à l’adresse Histo (lea esi,Histo),
c’est l’adresse du tout premier groupe historique. Ensuite on charge
dans eax NbCoups, comme NbCoups est sur 8 bits, on met d’abord eax
à 0 (xor eax,eax) puis on charge dans al NbCoups
(mov al,NbCoups), dans ces
conditions eax=NbCoups sur 32 bits. Ensuite on multiplie al par
LigHisto, pour ce faire on charge LigHisto dans cl (mov cl,LigHisto) puis on multiplie al par cl (mul cl), à ce stade ax=LigHisto*NbCoups
(résultat sur 16 bits) mais comme eax a été remis à 0 au début,
on a eax=LigHisto*NbCoups. On ajoute alors eax à esi (add esi,eax), comme esi pointait Histo, esi pointe
bien maintenant Histo+NbCoups*LigHisto c’est-à-dire le bon groupe
historique où l’on va stocker les coups possibles. On sauvegarde
esi dans la variable pHisto (mov pHisto,esi) pour ne pas avoir à la recalculer en
fonction de NbCoups. On écrit le code fin 255 dans l’historique
(mov byte ptr [esi],255). La
précision byte ptr (pointeur d’octet) est nécessaire pour une
valeur numérique car il faut préciser s’il s’agit de 255 sur 8 bits
(byte ptr), sur 16 bits (word ptr) ou sur 32 bits
(dword ptr). En revanche quand on écrit ou lit un registre,
on ne fait pas cette précision car le compilateur sait bien que
al est sur 8 bits, ax sur 16 bits et eax sur 32 bits et
idem pour tout autre registre e.g. bl, bx, ebx etc. Ensuite on va
écrire un 1 dans la case pointée par le cavalier de manière à ce
que durant l’analyse on puisse savoir que cette case est inaccessible
et on va en profiter pour renvoyer dans esi l’adresse correspondante
dans l’échiquier. On met donc dh à 1 (mov dh,1)
et on écrit dh dans la bonne case (call Ecritdh), Ecritdh étant une petite routine qui
se charge de ce travail. À ce stade, esi pointe la case où se trouve
le cavalier (calculé par Ecritdh), cette case contient un 1. Notre
sous-programme Cherche va renvoyer dh à l’appelant. Si dh<>0,
cela signifie qu’un coup au moins est jouable, si dh=0 cela signifie
qu’aucun coup n’a pu être historisé à ce stade. On initialise donc
le flag ou le témoin dh à 0 (xor dh,dh).
Ensuite on fait pointer edi sur les différentes directions que le
cavalier peut prendre (lea edi,DirC) et on met le compteur cl à 8 car cette
table contient 8 directions à tester (mov cl,8). La boucle de recherche peut commencer. On
lit dans ebx la direction à tester (mov ebx,[edi]). N’oubliez pas que les 3 valeurs pour
chaque direction sont sur 32 bits, c’est une petite astuce pour
faciliter la lecture, ebx est une valeur signée sur 32 bits. Comme
esi pointe la case du cavalier et que ebx contient l’offset d’une
direction parmi les huit possibles, esi+ebx représente une des cases
possibles où le cavalier peut se rendre, donc on lit le contenu
de cette case dans al (mov al,[esi+ebx])
puis on regarde si ce contenu est nul ou non (test al,al), test étant un ET logique non destructif
en l’occurrence ici un ET logique du registre al avec lui-même.
Ici si ZF=1 alors al=0 (la case est vide), si ZF=0 alors al<>0
et la case n’est pas vide. Notez que si ZF=0, on ne sait pas si
cette case est hors échiquier (code 255) ou bien si cette case a
déjà été piétinée par le cavalier (code 1) mais cela ne nous importe
peu, ce qu’on sait si ZF=0, c’est que cette case n’est pas possible
et cela nous suffit. Si la case n’est pas vide (ZF=0), on saute
à l'adresse Cherche20 pour continuer à scruter les directions (jnz Cherche20), instruction qui signifie "saute à l’adresse
Cherche20 si ZF=0", jnz=jump si non Z ou ce qui revient au même
"jmp si ZF=0". Si ce saut n’a pas lieu, alors la case testée est
vide, on va donc se poser la question de savoir combien de cases
nous aurions à notre disposition si on jouait ce coup, on appelle
pour ce faire le sous-programme Combien qui fait ce calcul (call Combien). Ce sous-programme enregistre dans l’historique
le coup possible et lui associe un nombre qui sera le nombre de
coups qu’on aurait si on jouait ce coup. Ce sous-programme met aussi
dh à 1 pour signifier à l’appelant Cherche qu’on a trouvé au moins
un coup. À chaque appel de Combien, le groupe historique visé s'enrichit
d'une nouvelle possibilité. À ce stade, que la case ait été possible
ou non, on a testé la direction pointée par edi, on pointe alors
la direction suivante (add edi,12).
On a vu que chaque direction est constituée de trois mots de 32
bits soit 12 octets, il faut donc ajouter 12 à edi pour qu’il pointe
la direction suivante. On décrémente le compteur cl (dec cl), si cl=0 après cette décrémentation on aura
ZF=1 et cela signifiera qu’on a testé toutes les directions, si
cl<>0 on aura ZF=0, il reste alors des directions à tester.
Si donc ZF=0, on doit continuer (jnz Cherche10), saute à l'adresse Cherche10 s’il reste
des directions à tester, comme edi pointe la direction, cette instruction
signifie "saute pour tester maintenant la direction pointée par
edi". Sinon, si ZF=1, le saut n’aura pas lieu, toutes les directions
ont été testées, on retourne à l’appelant (ret). On retourne avec dh qui dira si oui ou non on a trouvé
un coup, dh a été initialisé à 0 avant la boucle qui scrute les
directions, si le sous-programme Combien n’est jamais appelé, dh
restera à 0, le retour se fera donc avec dh=0 et l’appelant conclura
qu’il n’y a pas de coup. Si le sous-programme Combien est appelé
au moins une fois, on aura dh=1 car Combien se charge de mettre
dh à 1, le retour se fera donc avec dh=1 et l’appelant conclura
qu’il existe au moins un coup jouable dans l’historique.
Cherche: lea esi,Histo //
esi sur historique
xor eax,eax //
eax=0
mov al,NbCoups //
eax=NbCoups
mov cl,LigHisto //
cl=nb d’octets par ligne histo
mul cl //
eax=NbCoups*LigCoups
add esi,eax //
esi sur bon groupe histo
mov pHisto,esi //
mémorisé dans pHisto
mov byte
ptr [esi],255 // code fin au début de ce groupe
mov dh,1 //
on va écrire 1 dans la case
call Ecritdh //
la case est occupée
xor dh,dh //
dh=0 flag de coup trouvé
lea edi,DirC //
table des directions
mov cl,8 //
8 directions possibles
Cherche10: mov ebx,[edi] //
ebx = une des directions
mov al,[esi+ebx] //
al=contenu de cette case
test
al,al //
case vide?
jnz Cherche20 //
non on passe à la suivante
call
Combien //
oui coups possibles
Cherche20: add edi,12 //
direction suivante
dec cl //
fin?
jnz Cherche10 //
non refelemele
ret //
renvoie dh flag de coup trouvé
Voyons maintenant ce que va faire le sous-programme
Combien. Il est appelé parce qu'une direction est reconnue comme
possible et ce, parce que le contenu de la case esi+ebx est nul,
esi étant la position du cavalier et ebx la direction testée parmi
les huit possibles. Combien va faire comme si le cavalier se trouvait
à la position esi+ebx et va calculer le nombre de directions qu'il
aurait à sa disposition si ce coup était joué. Puis, il va enregistrer
d'une part la direction testée soit bl sur huit bits, le nombre
de coups disponibles calculé dans la boucle mais aussi les offsets
x et y correspondant à la direction bl situés aux adresses edi+4
et edi+8 (on ne lit que le LSB des valeurs, cela nous suffit). Notons
que même si le nombre de coups possibles est zéro, on enregistre
quand même cette information. La raison en est que l'avant-dernier
sera tel que le coup suivant sera un cul-de-sac, le nombre enregistré
associé sera donc zéro mais ce coup nous est utile. C'est bien entendu
un choix algorithmique, on pourrait faire en sorte de ne pas enregistrer
ce genre de coup mais dans ce cas il faudrait tester NbCoups, l'algorithme
serait quelque peu différent. En arrivant à Combien, il existe trois
éléments à ne pas perdre qui sont esi qui pointe la position du
cavalier sur l'échiquier, cl qui sert de compteur de directions
dans Cherche et edi qui pointe la direction testée dans le tableau
de directions DirC. Quant à ebx, il contient le direction testée
mais cet élément n'est pas sauvegardé, l'appelant n'en ayant plus
besoin. On commence donc par sauvegarder la position du cavalier
(push esi), le compteur de directions
(push ecx) et le pointeur
de directions (push edi).
On sauvegarde edi en dernier car avant le retour il faudra lire
les offsets x et y pour les écrire dans l'historique et donc pouvoir
dépiler par l'instruction pop le registre edi pour le refaire pointer
sur la direction testée. Chaque groupe historique se constitue comme
nous l'avons dit de quatre octets, l'offset d'échiquier, l'offset
en x, l'offset en y et le nombre de coups possibles associé à ce
coup. La sauvegarde des offsets x et y n'a qu'une seule vocation,
éviter d'avoir à les rechercher dans DirC (ce qui serait possible
car à tout bl de DirC correspond un couple unique x et y). Ensuite
on fait aller le cavalier sur la case à tester, pour ce faire on
ajoute ebx à esi (add esi,ebx) car ebx contient la direction
testée. On fait pointer edi sur les huit directions possibles à
tester (lea edi,DirC), on charge dans cl le nombre de directions
(mov cl,8), on met ch à 0
(xor ch,ch), ch va compter
le nombre de coups possibles à partir de la nouvelle position du
cavalier que pointe esi. La boucle de recherche peut maintenant
commencer. On charge dans ebx la direction à tester (mov ebx,[edi]), on lit dans al le contenu de la case
esi+ebx (mov al,[esi+ebx])
puis on regarde si ce contenu est nul ou non (test al,al). Si al n'est pas nul, il s'agit soit d'une
case hors échiquier soit d'une case déjà visitée, dans ce cas, la
direction testée n'est pas jouable, on saute à Combien20 (jnz Combien20). Si ce saut n'a pas eu
lieu, c'est que ZF=1 et donc que al=0, la case est alors vide, on
pourrait y aller, donc on incrémente le compteur ch de coups acceptables
(inc ch). On voit que le
test d'une direction n'a qu'un seul but, incrémenter ou non ch.
Que ch ait été ou non incrémenté, on fait pointer edi à la direction
suivante, on se souvient que chaque direction est codifiée sur 12
octets (add edi,12), on décrémente le compteur
de directions (dec cl). Si
après cette décrémentation ZF=0, alors cl n'est pas encore nul en
conséquence de quoi il reste des directions à tester, on se branche
donc à Combien10 pour tester la direction suivante (jnz Combien10). Si ce saut n'a pas lieu, alors cl=0,
on a alors passé en revue toutes les directions possibles et ch
contient le nombre de directions acceptées. Nous allons donc maintenant
enregistrer ces données dans l'historique. On fait pointer esi au
bon groupe historique, il suffit de lire le pointeur pHisto (mov esi,pHisto). En effet, dans Cherche
nous avons mémorisé cette adresse pour l'avoir à disposition et
éviter de la recalculer, esi pointe donc le bon groupe historique.
On se souvient que chaque série du groupe est de quatre octets et
que le code fin est 255. On cherche donc à pointer le premier octet
d'une série égal à 255, cela signifiera que cette série est libre
pour y contenir un nouvel enregistrement historique. On lit donc
dans al le premier octet d'une série (mov al,[esi]),
puis on pointe la série suivante (add esi,4), on teste maintenant le contenu de al pour
savoir s'il est égal à 255, on ne fait que l'incrémenter (inc al), c'est plus simple que de comparer
avec 255. Si al n'est pas nul après cette incrémentation (car 255+1=0
sur 8 bits), alors al n'était pas égal à 255, donc esi ne pointait
pas avant d'avancer la première série libre donc on continue le
test en bouclant à Combien30 (jnz Combien30). Si ce saut n'a pas lieu, alors ZF=1,
donc al=0 donc al était égal à 255 donc esi pointait avant d'avancer
la première série libre. Comme esi pointe la série suivante, on
sait qu'il faut écrire dans la série précédente qui est libre, esi-4
est l'adresse du premier octet de la série qui devra contenir la
direction testée, esi-3 l'offset en x, esi-2 l'offset en y et esi-1
le nombre de coups autorisés. On écrit le nombre de coups trouvés
jouables, ce nombre est le compteur ch (mov [esi-1],ch)
et comme esi pointe la série suivante, on y écrit le code fin (mov byte ptr [esi],255), ce qui signifiera
plus tard que cette série est libre pour enregistrer d'autres coups
ou encore qu'on est arrivé à la dernière série pour ce groupe historique.
Maintenant on récupère edi que nous avions sauvegardé en dernier
(pop edi), edi pointe la
direction testée dans Cherche, nous allons sauvegarder dans l'historique
l'offset d'échiquier ainsi que les offsets en x et y correspondant
à la direction. On lit dans al l'offset d'échiquier testé (mov al,[edi]), on ne lit que le LSB (l'octet
le moins significatif, last significant byte) qui seul est informatif,
les autres octets sont soit à 0 si la direction est positive soit
à 255 si la direction est négative, on sauvegarde cet offset dans
l'historique dans la première case de la série libre (mov [esi-4],al). On lit maintenant l'offset
en x (mov al,[edi+4]) et
on sauvegarde cet offset dans l'historique (mov [esi-3],al), enfin on lit l'offset en y (mov al,[edi+8]) et on le sauvegarde dans
l'historique (mov [esi-2],al). Le sous-programme est terminé, il
ne reste qu'à restituer le compteur ecx (pop ecx) et le pointeur esi (pop esi) qui contient l'adresse où se trouve le cavalier
puis on rend la main à l'appelant (ret) à savoir à Cherche qui va pouvoir continuer sa boucle
dans de bonnes conditions puisque edi est l'adresse de la direction
qui vient d'être testée, esi l'adresse du cavalier et cl le compteur
dans Cherche qui contrôle qu'on ne teste que 8 directions.
Combien: push esi //
position du cavalier en pile
push
ecx //
compteur de directions en pile
push
edi //
pointeur de directions en pile
mov dh,1 //
on a trouvé un coup
add esi,ebx //
esi sur cette case
lea edi,DirC //
table des directions
mov cl,8 //
8 directions
xor ch,ch //
ch=0 compteur de coups acceptés
Combien10: mov ebx,[edi] //
ebx = une des directions
mov al,[esi+ebx] //
al=contenu de cette case
test
al,al //
case libre?
jnz Combien20 //
non saute
inc ch //
oui compteur+1 de coups possibles
Combien20: add edi,12 //
direction suivante
dec cl //
fin?
jnz Combien10 //
non refelemele
mov esi,pHisto //
pHisto pointe déjà le bon groupe
Combien30: mov al,[esi] //
direction historique
add esi,4 //
avance toujours
inc al //
code fin?
jnz Combien30 //
non continue jusqu'au code fin
mov [esi-1],ch //
nombre de coups jouables
mov byte
ptr [esi],255 // code fin de la série historique
suivante
pop edi //
récupère la direction testée
mov al,[edi] //
al=direction testée
mov [esi-4],al //
dans l'historique
mov al,[edi+4] //
al=offset en x
mov [esi-3],al //
dans l'historique
mov al,[edi+8] //
al=offset en y
mov [esi-2],al //
dans l'historique
pop ecx //
récupère le compteur
pop esi //
récupère la position du cavalier
ret //
retour à l’appelant
Le sous-programme Meilleur recherche dans le groupe
historique correspondant au coup à traiter le meilleur coup c’est-à-dire
selon notre algorithme le coup associé à un nombre minimal de possibilités
futures. On se souvient que chaque série d’un groupe historique
se constitue de quatre octets : offset, x, y, nombre. À tout
offset correspond donc un nombre qui est le nombre de coups qu’aurait
à sa disposition le cavalier si cet offset était joué. Meilleur
cherche donc l’offset dont le nombre associé est le plus petit possible.
Meilleur renvoie aussi le registre 8 bits dh à titre de flag qui
indique s’il y a ou non un coup disponible dans le groupe historique
concerné car il se peut que tous les coups aient été déjà joués,
en conséquence de quoi le groupe historique est vide. Si dh<>0
(true), cela signifie qu’un coup a été trouvé dans l’historique
et qu’il a été joué. Si dh=0 (false), Meilleur n’a trouvé aucun
coup dans l’historique, le cavalier n’a donc pas bougé, on est dans
un cul-de-sac. Notons le cas particulier du dernier coup. Si un
coup est trouvé et si NbCoups=62 (62 correspond au dernier coup
car NbCoups n'a pas encore été incrémenté, il le sera juste après
dans le programme si un coup a été trouvé), alors on joue le coup,
on sait qu'il est obligatoirement unique, on ne fait donc pas de
recherche de minimum et on renverra quand même dh=0 bien qu'un coup
à savoir le dernier a été joué. Cette petite astuce fera croire
à l'appelant qu'on est arrivé à un cul-de-sac (ce qui est vrai,
une solution étant un cul-de-sac particulier), en conséquence de
quoi la boucle en while s'arrêtera. On évite ainsi d'avancer encore
quand une solution a été trouvée. Le programme fonctionnerait quand
même si on renvoyait dh=1, simplement il chercherait à avancer,
ne trouverait rien et finirait par reculer. En renvoyant dh=0 pour
le dernier coup, on simplifie la tâche au programme, la boucle en
while s'arrêtera et on reculera pour trouver d'autres solutions.
Meilleur commence donc par initialiser ce flag dh en le mettant
à 0 (xor dh,dh). Ensuite on fait pointer esi dans le bon
groupe historique (mov esi,pHisto). Ne confondez pas lea (load effective
adresse) et mov. Quand l'adresse est connue, on utilise lea, par
exemple pour pointer la case A1 on écrit "lea Echiquier+21".
Mais quand on lit une adresse en mémoire, on utilise mov, par exemple
ici "mov esi,pHisto", esi ne pointe pas pHisto, il contient
l'adresse située à l'adresse pHisto (le désassemblage donne mov
dans les deux cas mais avec les crochets pour [pHisto], cela montre
clairement qu'on lit un pointeur en mémoire). Ensuite on initialise
le minimum à un grand nombre (mov bl,255).
En réalité, comme le nombre maximum de coups de sera 8 (8 la première
fois et 7 pour tous les autres coups), n'importe quel nombre supérieur
à 8 conviendrait pour cette initialisation. Si on trouve un coup,
on comparera ce minimum au nombre situé dans la série historique.
La première fois, ce nombre sera nécessairement inférieur à bl puisqu'on
a initialisé le minimum au maximum mais pour les autres fois, cela
dépendra des valeurs en présence. La boucle commence donc, on lit
dans al l'octet pointé par esi à savoir l'offset de la série (mov al,[esi]). On incrémente ce nombre pour savoir
s'il était égal à 255 qui est le code fin du groupe historique (inc al). Si ZF=1, cela signifie qu'on
est à la fin du groupe historique, on l'a donc parcouru entièrement
et l'on saute à l'adresse Meilleur30 (jz Meilleur30). Si ce saut n'a pas lieu, al n'était
pas égal à 255, donc esi ne pointe pas la fin de l'historique. On
décrémente al qui reprend donc sa valeur d'origine pour savoir s'il
est nul (dec al). Si ZF=1
alors al=0, cela signifie que l'offset lu a été effacé, c'est un
ancien coup qui a été joué et effacé pour éviter de le rejouer.
Si ZF=1, on saute à l'adresse Meilleur20 (jz Meilleur20). Si le saut n'a pas lieu, cela signifie
que al n'est ni égal à 255 (code fin) ni égal à 0 (coup effacé),
donc esi pointe une série historique contenant un coup jouable.
À ce stade, on cherche à savoir si NbCoups est égal à 62 (cmp NbCoups,62). Si ZF=0, cela signifie
que NbCoups n'est pas égal à 62 c'est-à-dire qu'on n'est pas en
train de chercher le tout dernier coup, on saute alors à l'adresse
Meilleur15 qui est le cas général (jnz Meilleur15). Si ce saut n'a pas lieu, alors NbCoups=62,
on sauvegarde dans edi l'adresse de la série historique correspondant
au coup à jouer (mov edi,esi) puis l'on saute à Meilleur40 pour jouer
ce coup (jmp Meilleur40).
Notez que dh=0 dans ce cas, ainsi que nous l'avons déjà dit, cela
provoquera l'arrêt de la boucle en while dans le C++. On se retrouve
à l'adresse Meilleur15 dans le cas général à savoir un coup trouvé
avec NbCoups différent de 62. On charge dans al le nombre de coups
mémorisés dans cette série historique (mov al,[esi+3]), il s'agit bien de l'adresse esi+3
puisque esi+0=esi=adresse de l'offset, esi+1=adresse où il y a x,
esi+2=adresse où il y a y et esi+3=adresse où il y a le nombre de
coups possibles pour ce coup mémorisé. On regarde si ce nombre de
coups est nul ou non (test al,al).
Si oui, ZF=1 et l'on saute l'adresse Meilleur20 (jz Meilleur20) car ce coup ne nous intéresse pas puisqu'il
représente un cul-de-sac. En effet, nous cherchons le minimum certes
mais un minimum non nul. Si le saut n'a pas lieu, on tient là un
vrai coup. On commence par mettre dh à 1 (mov dh,1), cela indiquera à l'appelant qu'on va jouer
un coup puisqu'on est certain dans ce cas de pouvoir jouer. Ensuite,
on cherche à savoir si al est inférieur à bl (cmp al,bl). Si CF=0, cela signifie que al n'est pas
inférieur à bl (en effet la soustraction virtuelle al-bl ne provoque
pas de dépassement de capacité, ce qui revient à dire que al-bl>=0
donc al>=bl qui est bien la négation de al<bl, d'une manière
générale une syntaxe du type cmp x,y répond à la question de
savoir si x<y, CF=1 oui, CF=0 non). Le coup pointé
ne nous intéresse pas car on veut un minimum, donc si CF=0, on saute
à l'adresse Meilleur20 (jnc Meilleur20).
Si ce saut n'a pas lieu, on a alors CF=1, donc al est strictement
inférieur à bl, cela signifie qu'on tient ici un minimum plus petit
que le minimum courant que contient bl. Donc on sauvegarde dans
bl ce nouveau minimum (mov bl,al)
et on mémorise l'adresse de la série historique dans edi (mov edi,esi). Cela signifie que si l'analyse en restait
là, on jouerait le coup pointé par edi car le nombre associé à l'offset
est le minimum non nul du groupe historique. Arrivé à Meilleur20,
on passe à la série historique suivante, il suffit pour cela d'ajouter
4 à esi puisque chaque série se constitue de 4 octets (add esi,4). Puis on boucle en sautant
à l'adresse Meilleur10 (jmp Meilleur10) où l'on va traiter cette nouvelle série
du groupe historique considéré. Arrivé à Meilleur30, on teste dh
qui indique si oui ou non on a trouvé un coup dans l'historique
(test dh,dh). Si ZF=1, cela signifie qu'après
lecture de tout l'historique on a dh=0 c'est-à-dire qu'on n'a pas
trouvé de coup, dans ce cas on saute à l'adresse Meilleur50 pour
sortir immédiatement de la fonction (jz Meilleur50). Comme on sort dans ce cas avec dh=0,
la boucle en while conclura qu'on n'a pas pu jouer, la boucle s'arrêtera
et on reculera. Si ce saut n'a pas lieu, alors il existe un vrai
coup car dh n'est pas nul, le meilleur coup est pointé par edi.
Comme on va jouer ce coup, on incrémente NbCoups (inc NbCoups). Puis on va faire pointer esi dans la
zone Chemin à l'endroit où l'on doit enregistrer le coup adopté
à savoir à l'adresse Chemin+NbCoups*2. On commence ce petit calcul
en mettant ebx à 0 (xor ebx,ebx),
puis on charge dans bl le nombre de coups (mov bl,NbCoups), donc ebx sur 32 bits est égal à NbCoups.
On ajoute bx à lui-même (add bx,bx) ce qui multiplie bx par 2, donc ebx=NbCoups*2.
On fait pointer esi à l'adresse Chemin (lea esi,Chemin). Dans ces conditions,
on doit écrire l'offset en x du coup joué à l'adresse esi+ebx et
l'offset en y à l'adresse esi+ebx+1. Mais edi ne pointe que les
offsets à jouer et non pas la case en coordonnées, ces coordonnées
sont à calculer en fonction de la position du cavalier disponible
en lecture dans la zone Chemin. On va donc lire aux adresses esi+ebx-2
et esi+ebx-1, ces deux valeurs correspondant à la position du cavalier
pour l'instant, il s'agit d'ajouter à cette position (x,y) courante
les offsets à jouer lesquels sont aux adresses edi+1 et edi+2 c'est-à-dire
aux deuxième et troisième cases de la série historique jouée. On
charge donc dans al la position en x du cavalier (mov al,[esi+ebx-2]), on charge dans dl l'offset en
x de l'historique (mov dl,[edi+1]),
on ajoute cet offset à al (add al,dl), al est donc maintenant égal à la nouvelle
position en x du cavalier, on écrit cette valeur à l'adresse esi+ebx
(mov [esi+ebx],al) ce qui
correspond à l'enregistrement dans la zone Chemin. On procède au
même calcul en y en chargeant dans la zone Chemin la position en
y du cavalier (mov al,[esi+ebx-1]).
On lit dans dl l'offset en y de la série historique (mov dl,[edi+2]). On ajoute dl à al (add al,dl), al est donc égal à la nouvelle
position en y du cavalier, position que l'on enregistre dans la
zone Chemin (mov [esi+ebx+1],al).
Il ne reste plus qu'à effacer le coup de la série historique (mov byte ptr [edi],0), on n'efface
que l'offset c'est-à-dire la première case de la série, si donc
le cavalier se retrouve dans cette même configuration, un autre
coup que celui-ci sera nécessairement joué si toutefois il reste
un coup possible dans ce groupe historique. La fonction est terminée,
on rend la main à l'appelant (ret).
Meilleur: xor dh,dh //
flag de coup trouvé
mov esi,pHisto //
esi pointe l’historique
mov bl,255 //
init du minimum au maxi
Meilleur10: mov al,[esi] //
coup historisé
inc al //
fin?
jz Meilleur30 //
oui saute, fin d’historique
dec al //
coup effacé?
jz Meilleur20 //
oui saute
cmp NbCoups,62 //
dernier coup?
jnz Meilleur15 //
non cas général
mov edi,esi //
oui adresse du coup unique
jmp Meilleur40 //
saute pour l'enregistrer
Meilleur15: mov al,[esi+3] //
nb de coups possibles
test
al,al //
cul de sac?
jz Meilleur20 //
oui ignore
mov dh,1 //
non on a trouvé un vrai coup
cmp al,bl //
minimum plus petit encore?
jnc Meilleur20 //
non continue la recherche
mov bl,al //
oui nouveau minimum
mov edi,esi //
mémorise l'adresse du minimum
Meilleur20: add esi,4 //
série historique suivante
jmp Meilleur10 //
continue jusqu'à la fin
Meilleur30: test dh,dh //
rien?
jz Meilleur50 //
oui retour avec dh=0 (rien)
Meilleur40: inc NbCoups //
un coup de plus
xor ebx,ebx //
ebx=0
mov bl,NbCoups //
ebx=NbCOups
add bx,bx //
ebx*2 donc ebx=NbCoups*2
lea esi,Chemin //
on va enregistrer à esi+ebx
mov al,[esi+ebx-2] //
al=x d'où l'on vient
mov dl,[edi+1] //
dl=offset en x choisi
add al,dl //
al=x où l'on va
mov [esi+ebx],al //
enregistré dans Chemin
mov al,[esi+ebx-1] //
al=y d'où l'on vient
mov dl,[edi+2] //
dl=offset en y choisi
add al,dl //
al=y où l'on va
mov [esi+ebx+1],al //
enregistré dans Chemin
mov byte
ptr [edi],0 // coup effacé de l'historique
Meilleur50: ret //
retour à l’appelant
Dans ces conditions le sous-programme Joue est très court. On commence
par rechercher et enregistrer dans le bon groupe historique tous
les coups possibles (call Cherche). Cette fonction, comme nous l’avons vu,
renvoie dh. Bien que dh soit un registre 8 bits, on le considère
ici comme un flag. Si dh<>0, alors il y a au moins un coup
d’enregistré dans le groupe historique concerné. Si dh=0, rien n’a
été trouvé donc rien n’a été enregistré dans l’historique, on est
dans un cul-de-sac, il faudra reculer. On teste donc la valeur de
dh pour savoir si dh est nul ou non (test dh,dh). Si ZF=1, alors dh=0 et donc on n’a rien
trouvé, on saute à l’adresse Joue10 pour retourner à l'appelant
(jz Joue10). Si ce saut n’a pas lieu,
il existe alors au moins un coup dans le groupe historique, on cherche
et on joue le meilleur de ces coups historisés (call Meilleur), il s’agit, comme nous l’avons dit,
du coup associé à un nombre de possibilités futures minimum et non
nul (quatrième octet de chaque série historique). À noter qu’après
avoir reculé et qu’après avoir testé pour un groupe historique précédent
la présence d’un coup possible (coup donc non encore joué), le C++
nous branche à cette adresse à savoir Joue5. En effet, il faut surtout
ne pas recalculer via Cherche tous les coups possibles et donc ne
pas se brancher à Joue sinon le programme bouclerait et trouverait
sans cesse les mêmes solutions. Il faut se brancher à Joue5 de manière
à choisir un autre coup présent dans l’historique parmi ceux qui
n’ont pas encore été effacés. C’est ce procédé qui nous assure de
trouver chaque fois un chemin différent et qui épuise toutes les
solutions possibles. Meilleur renvoie dh pour indiquer si on est
autorisé à avancer encore. Si dh<>0 (true), on a joué un coup
et on est autorisé à essayer d’avancer encore. Si dh=0, on est dans
un cul-de-sac, soit un cul-de-sac en plein milieu de recherche,
soit un cul-de-sac qui est une solution. Dans ce cas, la boucle
d’avance s’arrêtera dans le programme maître. Le sous-programme
Joue est terminé, on retourne à l’appelant (ret).
Joue: call Cherche //
recherche tous les coups
test
dh,dh //
cul de sac ou solution?
jz Joue10 //
oui cassos avec dh=0
Joue5: call Meilleur //
non choisis le meilleur coup
Joue10: ret //
retour avec dh
Il ne nous reste qu’un seul petit sous-programme
à écrire, c’est Ecritdh qui écrit le contenu du registre dh dans
la case visée par le cavalier. Si dh=1, cela signifiera que le cavalier
passe par cette case, si dh=0 cela signifiera qu’on libère la case
mais le sous-programme ne s’occupe pas de la valeur de dh, il se
contente de calculer le bon offset et d’y écrire dh. De quelle case
s’agit-il ? Il s’agit de la case située à la fin de la zone
Chemin, case à laquelle on accède (cas où dh=1) ou qu'on quitte
(cas où dh=0). Comme il y a NbCoups joués, l’adresse de lecture
dans Chemin est Chemin+NbCoups*2. À cette adresse on lira l’offset
en x et à l’adresse suivante l’offset en y. Ces deux offsets compris
entre 0 et 7 ayant été lus, on calcule 10*y+x, ce nombre correspond
à ce qu’il faut ajouter à Echiquier+21 (case A1) pour pointer la
bonne case. Une fois pointée, on y écrit dh. On commence donc par
pointer au début de la zone Chemin (lea esi,Chemin). On va calculer dans
ebx la valeur NbCoups*2, on commence par annuler ebx de manière
à ce que les 24 bits de poids fort soient nuls (xor ebx,ebx), on charge NbCoups dans bl (mov bl,NbCoups). Ainsi bl=NbCoups mais
comme les 24 bits de poids fort sont nuls, on a aussi ebx=NbCoups.
Pourquoi devons-nous procéder ainsi ? Simplement parce qu’une
syntaxe du type esi+bl n’existe pas, esi est sur 32 bits, il faut
que les opérandes soient de même format, donc la syntaxe est esi+ebx,
c’est pourquoi pour lire une valeur 8 bits, on commence toujours
par mettre le registre 32 bits à 0, on lit les 8 bits, tout le registre
contient alors sur 32 bits la valeur 8 bits, ce qui nous permet
d’utiliser la syntaxe esi+ebx. Donc ici on a ebx=NbCoups. On multiplie
par deux (add bx,bx), donc ebx=NbCoups*2. On lit
dans la zone Chemin l’octet d’adresse esi+ebx+1 (mov al,[esi+ebx+1]), al est alors égal à la position
en y du cavalier. On va multiplier par 10 cette valeur. Pour ce
faire, on écrit 10 dans le registre 8 bits cl (mov cl,10) puis on multiplie al par cl (mul cl), le résultat se trouve dans ax
sur 16 bits. Cela dit, comme le chiffre maximal est 7, le résultat
maximal sera 70, cela tient sur 8 bits, donc al contient seul cette
valeur et ah=0. Ceci nous permet d'utiliser ah sans perte d'information,
ce que nous faisons puisque nous lisons dans ah la position en x
du cavalier (mov ah,[esi+ebx]).
On ajoute maintenant ah à al (add al,ah), donc al=10*y+x, la valeur maximale est
77 (7*10+7). On écrit ce résultat dans bl (mov bl,al). Comme ebx a été remis à 0, ebx=10*y+x à
savoir l’offset qu’il faut ajouter à Echiquier+21 (case A1) pour
pointer la bonne case de l’échiquier. Donc on fait pointer esi à
la case A1 (lea esi,Echiquier+21),
la case correspondante est donc esi+ebx, on y écrit dh (mov [esi+ebx],dh). Nous ne savons pas à quoi est égal
dh et cela ne nous importe peu. On sait seulement qu’on appelle
Ecritdh avec dh=0 ou dh=1 et que si dh=1 cela interdira l’utilisation
future de cette case car le cavalier ne peut visiter que les cases
libres et si dh=0 cela libérera la case pour une possibilité d’utilisation
future. C’est fini, dh a été écrit sur la bonne case de notre échiquier,
on retourne à l’appelant (ret).
Ecritdh: lea esi,Chemin
xor ebx,ebx
mov bl,NbCoups //
ebx nb de coups déjà joués
add bx,bx //
ebx*2
mov al,[esi+ebx+1] //
al = offset en y
mov cl,10
mul cl //
al=10y
mov ah,[esi+ebx] //
ah = x
add al,ah //
al=10y+x
mov bl,al //
ebx=10y+x
lea esi,Echiquier+21 //
esi sur A1
add esi,ebx //
+ offset=case où l'on est
mov [esi],dh //
écrit dh dans la case
ret
Le reste du programme concerne le graphique et est
écrit en C++. La fonction Dessine dessine dans le bitmap la position
correspondant à la zone Chemin, ce dessin se créant à partir d’un
bitmap vide. Pour chaque couple (x,y) de la zone Chemin, on calcule
les coordonnées graphiques correspondantes et on y affiche le numéro
du coup associé. Ainsi, chaque fois qu’un coup est ajouté dans Chemin,
un numéro supplémentaire apparaît dans une case, ce qui simule l’avancée
du cavalier. Après un recul, NbCoups a été décrémenté, un couple
(x,y) de moins sera visité, la case ignorée à la fin de la zone
Chemin reste alors vide (car on redessine à partir d’un bitmap effacé)
ce qui donne l’impression que le cavalier recule. On commence par
effacer le bitmap :
BM->Canvas->Brush->Style=bsSolid;
BM->Canvas->FillRect(Rect(0,0,BM->Width,BM->Height));
La précision bsSolid est nécessaire, tout le bitmap
se remplit avec la couleur BM->Canvas->Brush->Color, cette
couleur est initialisée à blanc au moment de la création du bitmap
par new (blanc est la couleur par défaut de Brush), on la laisse
donc telle quelle. Nous allons maintenant dessiner les lignes correspondant
à l’échiquier, on va les dessiner avec en bleu clair :
BM->Canvas->Pen->Color=clAqua;
On commence par les 9 traits horizontaux de l’échiquier.
On initialise une variable Offset avec CoinTop. À chaque ligne,
on pose le crayon sur le point (CoinLeft,Offset) puis on trace un
trait horizontal jusqu’à CoinLeft+LarCase*8, Offset). Comme chaque
case à une largeur de LarCase pixels, LarCase*8 correspond à la
longueur de l’échiquier. Puis on ajoute LarCase à Offset pour la
prochaine ligne horizontale.
Offset=CoinTop;
for(i=0;i<9;i++)
{
BM->Canvas->MoveTo(CoinLeft,Offset);
BM->Canvas->LineTo(CoinLeft+LarCase*8,Offset);
Offset+=LarCase;
}
Puis on trace les 9 lignes verticales, on obtient
ainsi une grille de 8x8. Le principe est le même que précédemment
mais la variable Offset va évoluer en x et non en y.
Offset=CoinLeft;
for(i=0;i<9;i++)
{
BM->Canvas->MoveTo(Offset,CoinTop);
BM->Canvas->LineTo(Offset,CoinTop+LarCase*8);
Offset+=LarCase;
}
Ensuite, nous allons écrire les lettres et les chiffres
au bord de l’échiquier, nous allons les écrire en noir.
BM->Canvas->Font->Color=clBlack;
On commence par écrire les lettres allant de A à
H horizontalement en bas de l’échiquier. On prend comme coordonnées
en y CoinTop+LarCase*8+10, on se situe donc à 10 pixels en dessous
de la première ligne horizontale en partant du bas. On initialise
la variable Offset à CoinLeft+Larcase/3 ce qui nous positionne au
premier tiers de la case. On entre dans une boucle en i, pour chaque
occurrence on écrit le caractère correspondant au code ascii 65+i,
on affichera donc A pour i=0, B pour i=1 etc. Après chaque affichage,
on avance le pointeur graphique en x c’est-à-dire qu’on ajoute LarCase
à Offset.
Offset=CoinLeft+LarCase/3;
Ligne=CoinTop+LarCase*8+10;
for(i=0;i<8;i++)
{
BM->Canvas->TextOutA(Offset,Ligne,char(65+i));
Offset+=LarCase;
}
Principe similaire pour écrire les huit chiffres
verticalement. On initialise la variable Offset avec CoinTop+Larcase*22/3.
Comme 22/3 est égal à 7+1/3, on pointe le premier tiers en y, là
où l’on va écrire le 1. Pour les x, on choisit CointLeft-15, on
se trouve alors à 15 pixels de la première ligne verticale. À chaque
occurrence de la boucle en i, on affiche le code ascii 49+i, donc
1 pour i=0, 2 pour i=1 etc. Puis on soustrait LarCase à notre Offset,
on remonte ainsi notre coordonnée en y, là où doit s’écrire le chiffre
suivant.
Offset=CoinTop+LarCase*22/3;
Ligne=CoinLeft-15;
for(i=0;i<8;i++)
{
BM->Canvas->TextOutA(Ligne,Offset,char(49+i));
Offset-=LarCase;
}
Nous allons maintenant visiter la zone Chemin et
écrire dans les cases de l’échiquier le numéro des coups, nous allons
écrire ces numéros en rouge.
BM->Canvas->Font->Color=clRed;
Pour chaque couple (x,y) de la zone Chemin, on lit
x puis y. L’offset d’affichage en x sera CoinLeft+x*LarCase+10,
on se trouve à 10 pixels à l’intérieur de la case. L’offset en y
sera CoinTop+(8-y)*LarCase-20 soit à 20 pixels à l’intérieur de
la case. Ces coordonnées étant calculées, on affiche le numéro du
coup soit i+1 dans la boucle en i.
for(i=0;i<NbCoups+1;i++)
{
x=Chemin[i*2];
y=Chemin[i*2+1];
Offset=CoinLeft+x*LarCase+10;
Ligne=CoinTop+(8-y)*LarCase-20;
BM->Canvas->TextOutA(Offset,Ligne,IntToStr(i+1));
}
À ce stade, la totalité du bitmap a été dessiné hors
écran, il faut maintenant forcer un paint. La fonction Dessine reçoit
à cet effet le Sender (TObject*) nécessaire à la fonction OnPaint.
Il suffit, pour forcer un paint d’appeler la méthode OnPaint de
Form1, donc :
Form1->OnPaint(S);
où S est le Sender reçu en argument dans la fonction.
Cet OnPaint n’est appelé qu’une seule fois directement par notre
programme car il faut mettre à jour l’écran après que le bitmap
a été redessiné. Tous les autres OnPaint seront appelés par le système
en cas de nécessité sans que nous nous en occupions. À chaque fois,
le processus sera le même, recopier via draw le bitmap dans le canvas
de Form1.
void __fastcall
TForm1::FormPaint(TObject *Sender)
{
Form1->Canvas->Draw(0,0,BM);
}
Le seul objet qui a été instancié par new est notre
bitmap, il convient de restituer la mémoire allouée au moment du
OnDestroy de Form1.
void __fastcall
TForm1::FormDestroy(TObject *Sender)
{
delete BM;
}
PROGRAMME COMPLET
C++/Assembleur
Pour faire fonctionner immédiatement ce programme :
1) Entrez dans C++ Builder
2) Faites Fichier|Enregistrer le projet sous
3) À la place de unit1 choisissez
cavalier
4) À la place de Project1 choisissez Hamilton
5) Double-cliquez sur les événements OnActivate, OnDestroy
et OnPaint
de Form1 dans l'inspecteur d'objets.
Cette petite manipulation nous
a créé
les trois méthodes FormActivate,
FormDestroy et FormPaint
dans la classe TForm1 maintenant disponibles
dans l'en-tête cavalier.h :
class
TForm1 : public TForm
{
__published: // Composants
gérés par l'EDI
void
__fastcall FormActivate(TObject *Sender);
void
__fastcall FormDestroy(TObject *Sender);
void
__fastcall FormPaint(TObject *Sender);
private: //
Déclarations utilisateur
public: //
Déclarations utilisateur
__fastcall
TForm1(TComponent* Owner);
};
6) Effacer tout ce qui se trouve dans cavalier.cpp
créé par C++ Builder.
7) Copiez-collez dans cavalier.cpp maintenant vide le source
ci-dessous.
8) Sauvagardez tout (cliquez sur les disquettes en cascade)
9) Faites F9 pour compiler et exécuter
le programme.
Remarque 1 : le nom proposé cavalier à la
place de unit1 est important à cause de l'include cavalier.h
dans le cpp.
Remarque 2 : en créant les trois méthodes
d'événements, vous créez aussi leur prototype en temps réel dans
le cpp mais cela n'a aucune importance puisque l'étape 6 efface
précisément le contenu de ce cpp pour le remplacer par le source
ci-dessous. Ce qui importe, c'est que ces trois méthodes aient été
déclarées dans cavalier.h et que ces liens existent dans
l'inspecteur d'objets.
Remarque 3 : vous ne pouvez faire fonctionner
ce tutoriel que si vous avez l'assembleur c'est-à-dire l'exécutable
tasm32.exe dans votre répertoire bin. Quand bcc32.exe (le
compilateur C++) rencontre la directive asm, il appelle l'assembleur
à savoir tasm32.exe. Au début du source ci-dessous, il y
a la directive #pragma inline, c'est cette directive
qui indique au C++ (bcc32) qu'il va y avoir de l'assembleur (tasm32)
par la suite.
//---------------------------------------------------------------------------
//-------------- H A M I L T O N D E B U T --------------------------------
//---------------------------------------------------------------------------
#include <vcl.h>
#pragma hdrstop
#pragma inline
#include "cavalier.h"
#pragma package(smart_init)
#pragma resource "*.dfm"
//---------------------------------------------------------------------------
/* Les messages */
const char Msg[][100]=
{"Case de départ", //0
"Donnez la case de départ (par exemple E4)" //1
};
/* Coordonnées d'affichage
largeur des cases de l'échiquier
longueur d'une ligne d'historique soit
7 fois "off, x, y, n" et code fin = 33 octets
Solutions = nb de solutions à afficher */
const int CoinLeft = 50,
CoinTop =
30,
LarCase =
30,
LigHisto =
33,
Solutions
= 10;
//---------------------------------------------------------------------------
/* Pointeur de la fenêtre principale */
TForm1 *Form1;
/* Pointeur pour un bitmap hors écran */
Graphics::TBitmap *BM;
/* Chemin emprunté par le cavalier, série d'offsets x y
Zone déclarée en C++ car utilisée par le C++ pour afficher
le numéro des coups dans les cases par une syntaxes du type Chemin[i]
*/
char Chemin[128];
/* Case de départ + zéro de fin de chaîne */
char Depart[3];
/* Nombre de coups joués */
char NbCoups;
/* Nb de solutions trouvées */
int NbSol;
/* flags d'avance et de recul autorisés */
bool AvanceOK, ReculeOK;
/* pointeur dans l'historique */
char *pHisto;
//---------------------------------------------------------------------------
asm
{
/* Échiquier entouré de codes 255 hors écran (A1=Échiquier+21) */
Echiquier db 255,255,255,255,255,255,255,255,255,255
db 255,255,255,255,255,255,255,255,255,255
db 255,
0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 ,255
db 255,
0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 ,255
db 255,
0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 ,255
db 255,
0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 ,255
db 255,
0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 ,255
db 255,
0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 ,255
db 255,
0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 ,255
db 255,
0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 ,255
db 255,255,255,255,255,255,255,255,255,255
db 255,255,255,255,255,255,255,255,255,255
/* Les huit directions du cavalier en termes d'offsets d'adresse
et (x,y) */
DirC dd 8, -2, 1
dd 12, 2, 1
dd 19, -1, 2
dd 21, 1, 2
dd -8, 2,
-1
dd -12, -2,
-1
dd -19, 1,
-2
dd -21, -1,
-2
/* Historique
Chaque groupe de LigHisto octets se constitue de 8 coups maxi de
4 octets
et d'un code fin (255) d'où LigHisto=33 (ligne d'historique)
case possible (offset d'adresse), Offx, Offy,
nb de coups qui seraient acceptés pour cette case */
Histo db LigHisto*63 dup(?)
}
//---------------------------------------------------------------------------
__fastcall TForm1::TForm1(TComponent* Owner)
:
TForm(Owner)
{
/* ni coup ni solution */
NbCoups=0;
NbSol=0;
/* Création du bitmap aux dimensions de l'écran (surdimension) en
quatre bits par pixel */
BM = new Graphics::TBitmap();
BM->PixelFormat=pf4bit;
BM->Width=Screen->Width;
BM->Height=Screen->Height;
/* Quelques propriétés de la fenêtre principale (application) */
Form1->Width=380;
Form1->Height=380;
Form1->Top=90;
Form1->Left=30;
}
//---------------------------------------------------------------------------
asm
{
/* calcul des offsets x et y de la case de départ
par rapport à la case A1 située à l'adresse Echiquier+21
et écriture dans le premier couple (x,y) de Chemin de cette case
*/
CalOCD: mov al,Depart //
case de départ (lettre)
sub
al,65 //
entre 0 et 7
mov
Chemin,al //
enregistré
mov
al,Depart+1 //
case de départ (chiffre)
sub
al,49 //
entre 0 et 7
mov
Chemin+1,al //
enregistré
ret //
fin
/* Cherche tous les coups et joue le meilleur s'il y a au moins
un coup
renvoie al qui indique si un coup a été joué ou non
si oui (al<>0 true), la boucle en while du C++ contin
