I. Le cavalier hamiltonien : explication et mise en œuvre▲
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ées 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,255Nous 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, -2C'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ée 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 comprise 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 comprise 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
retLa 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 la 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'appelantLe 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'appelantDans 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 dhIl 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
retLe 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ée 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;
}II. Programme complet▲
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.
le nom proposé cavalier à la place de unit1 est important à cause de l'include cavalier.h dans le cpp.
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.
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 syntaxe 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++ continuera
si non (al=0 false), la boucle en while s'arrêtera */
Joue: call Cherche // recherche tous les coups possibles
test dh,dh // cul de sac?
jz Joue10 // oui cassos avec dh=0
Joue5: call Meilleur // non choisis le meilleur coup historisé
Joue10: ret // dh flag d'avance réalisée
//--------------
/* Cherche tous les coups possibles et mémorise dans l'historique
pour chacun d'eux off, x, y ainsi que le nombre de coups dont
nous disposerions si le coup associé était joué.
Renvoie dh indiquant s'il y a au moins un coup ou non, dh=1 oui, dh=0 non.
On commence par faire pointer pHisto sur le bon groupe historique
c'est-à-dire à l'adresse Histo+NbCoups*LigHisto et on écrit
le code fin à cette adresse */
Cherche: lea esi,Histo
xor eax,eax
mov al,NbCoups
mov cl,LigHisto
mul cl // eax=LigHisto*NbCoups
add esi,eax // esi pointe le bon groupe historique
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 calcule le nb de coups possibles
Cherche20: add edi,12 // direction suivante
dec cl // fin?
jnz Cherche10 // non refelemele
ret // renvoie dh flag de coup trouvé
//--------------
/* Recherche combien de coups nous aurions à notre disposition
si on choisissait cette case. L'offset testé est dans ebx sur 32 bits
ou bl sur 8 bits (ebx=bl)
On en profite pour mettre dh à 1 puisque si on est arrivé là, c'est
qu'on a trouvé au moins une destination possible */
Combien: push esi
push ecx
push edi
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
/* ici ch est égal au nombre de coups possibles pour l'offset testé,
on mémorise ces données dans l'historique. On recherche
d'abord le code fin 255 dans le groupe historique puis on écrit les données
et le code fin */
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
/* ici esi pointe dans l'historique la série d'après le code fin,
on écrase ce code fin en faveur de l'offset à mémoriser, on écrit x,y et
le nb de coups jouables et on réécrit à la suite la code fin */
mov [esi-1],ch // nombre de coups jouables
mov byte ptr [esi],255 // code fin pour la série suivante
pop edi // récupère la direction testée
mov al,[edi] // al=direction testée (LSB)
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
pop esi
ret
//--------------
/* Recherche du meilleur coup parmi les coups historisés
renvoie edi pointant ce meilleur coup dans le bon groupe historique
renvoie aussi dh à l'appelant pour indiquer si un coup a été
trouvé ou non, dh=1 oui, dh=0 non */
Meilleur: xor dh,dh // flag de coup trouvé
mov esi,pHisto // esi pointe le bon groupe historique
mov bl,255 // init du minimum au maxi
Meilleur10: mov al,[esi] // coup historisé
inc al // fin?
jz Meilleur30 // oui saute pour essayer d'enregistrer
dec al // coup effacé?
jz Meilleur20 // oui saute
/* ici un coup a été trouvé. On traite le cas particulier du dernier
coup pour lequel on accepte un cul-de-sac. D'ailleurs c'est forcément
un cul-de-sac, si NbCoups=62 (car NbCoups n'a pas encore été incrémenté,
63 étant le nombre de coups total du cavalier), cela suffit pour accepter
le coup historique trouvé d'où saut à Meilleur30 */
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
/* Ici cas général, on ne tolère pas le cul-de-sac */
Meilleur15: mov al,[esi+3] // nb de coups possibles
test al,al // cul de sac?
jz Meilleur20 // oui ignore cette série historique
/* ici on est certain de trouver un coup historisé donc dh=1 */
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 de l'historique
/* ici l'historique a été lu entièrement pour le coup en cours,
reste à savoir si on a trouvé un coup */
Meilleur30: test dh,dh // rien?
jz Meilleur50 // oui retour immédiat avec dh=0 (rien)
/* enregistre le meilleur coup pointé par edi dans Chemin.
On fait pointer esi à Chemin+NbCoups*2 (car il y a deux octets par coup)
puis on écrit x à esi et y à esi+1 . Comme edi pointe le coup historique
choisi, on ajoute ces directions mémorisées dans cette série
historique à la position du cavalier de manière
à ce que Chemin contienne les coordonnées réelles successives.
On termine en effaçant ce coup de l'historique pour qu'il ne soit pas rejoué */
Meilleur40: inc NbCoups // un coup de plus
xor ebx,ebx
mov bl,NbCoups
add bx,bx // ebx*2
lea esi,Chemin
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é
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é
mov byte ptr [edi],0 // coup effacé de l'historique
Meilleur50: ret // retour avec dh et edi si dh=1
//--------------
/* revoie al flag de continuation de recul
si ce S/P renvoie al=0 (false) on arrêtera la boucle en while dans le C++
c'est-à-dire qu'on arrêtera de reculer, car un coup a été trouvé dans
l'historique.
Si al<>0 (true), aucun coup n'a été trouvé dans l'historique donc
on continuera la boucle en while pour reculer à nouveau */
Recule: xor dh,dh // dh=0
call Ecritdh // libère la case de recul
dec NbCoups // un coup de moins
/* ici on calcule dans esi l'adresse du bon groupe historique
qui est égale à Histo+NbCoups*LigHisto (puisqu'il y a LigHisto
octets historiques par coup). Ce groupe historique correspond
au groupe précédent puisqu'on vient de décrémenter NbCoups */
lea esi,Histo
xor eax,eax
mov al,NbCoups
mov cl,LigHisto
mul cl
add esi,eax // esi sur le groupe histo
mov pHisto,esi // mémorisation du pointeur historique
Recule10: mov al,[esi] // offset historique
cmp al,255 // fin du groupe historique?
jz Recule40 // oui saute avec al=255<>0
test al,al // coup effacé?
jnz Recule20 // non saute
Recule15: add esi,4 // oui groupe suivant
jmp Recule10 // continue la recherche
Recule20: mov al,[esi+3] // nb de coups possibles
test al,al // cul-de-sac?
jz Recule15 // oui continue de chercher
xor al,al // non on a un coup, retour avc al=0
Recule40: ret // al = flag de continuation de recul
//--------------
/* Écrit dh dans la case correspondant au coup enregistré dans Chemin
dh est est égal à 1 pour occuper la case
dh est est égal à 0 pour libérer la case */
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
}
//---------------------------------------------------------------------------
void Dessine(TObject *S)
{
int i, Offset, Ligne;
char x,y;
/* Efface tout le bitmap, on redessine à partir de rien. La couleur
par défaut pour le remplissage est le blanc, donc on laisse tel quel
sinon il faudrait initialiser BM->Canvas->Brush->Color à la couleur voulue */
BM->Canvas->Brush->Style=bsSolid;
BM->Canvas->FillRect(Rect(0,0,BM->Width,BM->Height));
/* Couleur des traits dessinant l'échiquier */
BM->Canvas->Pen->Color=clAqua;
/* Traits horizontaux de l'échiquier */
Offset=CoinTop;
for(i=0;i<9;i++)
{
BM->Canvas->MoveTo(CoinLeft,Offset);
BM->Canvas->LineTo(CoinLeft+LarCase*8,Offset);
Offset+=LarCase;
}
/* Traits verticaux de l'échiquier */
Offset=CoinLeft;
for(i=0;i<9;i++)
{
BM->Canvas->MoveTo(Offset,CoinTop);
BM->Canvas->LineTo(Offset,CoinTop+LarCase*8);
Offset+=LarCase;
}
/* Coordonnées en noir */
BM->Canvas->Font->Color=clBlack;
/* On écrit les lettres de A à H */
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;
}
/* On écrit les chiffres de 1 à 8 */
Offset=CoinTop+LarCase*22/3;
Ligne=CoinLeft-15;
for(i=0;i<8;i++)
{
BM->Canvas->TextOutA(Ligne,Offset,char(49+i));
Offset-=LarCase;
}
/* Affiche le numéro des coups dans les cases en rouge */
BM->Canvas->Font->Color=clRed;
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));
}
/* appel du OnPaint de Form1 */
Form1->OnPaint(S);
}
//---------------------------------------------------------------------------
void __fastcall EN_AVANT(TObject* S)
{
/* Boucle générale d'avance
on avance jusqu'à cul-de-sac */
AvanceOK=true;
while(AvanceOK)
{
asm
{
call Joue // joue le meilleur coup s'il y a un coup
mov AvanceOK,dh // témoin de coup joué
}
/* Affiche le nouveau coup joué */
Dessine(S);
} // fin du while(AvanceOK)
/* Si le cavalier a joué 63 fois, c'est donc qu'on a trouvé une solution */
if(NbCoups==63)
{
AnsiString A;
A="Solution numéro "+IntToStr(++NbSol);
Application->MessageBox(A.c_str(),"Solution",MB_OK);
}
/* On n'acceptera de reculer que si l'on n'est pas arrivé
au nombre de solutions requis. Cette petite précaution
nous permettra de laisser affichée
une solution complète à l'écran à la fin du processus
puisque alors le recul n'aura pas lieu */
ReculeOK=(NbSol!=Solutions);
}
//---------------------------------------------------------------------------
void __fastcall EN_ARRIERE(TObject* S)
{
/* Sortie immédiate si recul refusé.
Ce refus n'arrive qu'à la fin de l'exécution quand on a affiché le nombre
correct de solutions (voir constante Solutions en en-tête). Ainsi, quand
le programme rendra la main à l'utilisateur, une solution entière restera
affichée du fait que ce recul est refusé. Si on ne prenait pas cette
petite précaution, le dernier affichage serait incomplet puisqu'un recul
de quelques coups aurait été exécuté. */
if(!ReculeOK) return;
/* Boucle générale de recul */
while(ReculeOK)
{
asm
{
call Recule // recule
mov ReculeOK,al // témoin de recul à continuer
}
/* Efface la case vide libérée */
Dessine(S);
} // fin du while ReculeOK
/* Ici on peut réavancer, on cherche un coup dans l'historique.
Il sera forcément différent du choix précédent au même stade
puisque les coups effectivement joués sont effacés de l'historique */
asm
{
call Joue5
}
/* Affiche le nouveau coup joué */
Dessine(S);
}
//---------------------------------------------------------------------------
void __fastcall InitCaval(AnsiString D, TObject* S)
{
/* recopie dans Départ de la case choisie par l'utilisateur */
strcpy(Depart,D.c_str());
/* Initialisation du calcul */
asm
{
/* Offset de la case de départ */
call CalOCD
}
/* Dessine dans le bitmap, on a déjà la case de départ */
Dessine(S);
}
//---------------------------------------------------------------------------
void __fastcall Cavalier(AnsiString D, TObject* S)
{
/* Initialisations */
InitCaval(D,S);
/* Boucle générale d'avancée et de recul */
do
{
EN_AVANT(S);
EN_ARRIERE(S);
}
while(NbSol!=Solutions);
};
//---------------------------------------------------------------------------
void __fastcall TForm1::FormActivate(TObject *Sender)
{
/* CasDep case de départ choisi par l'utilisateur */
AnsiString CasDep;
int Rep;
/* Saisie de la case de départ, au sortir de la boucle en while
Rep=1, rien n'est saisi on sort de l'application
Rep=2, une case correcte est entrée, on exécute le calcul */
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;
}
/* Fin de l'application si case de départ non saisie
sinon recherche des solutions */
if(Rep==1) Close(); else Cavalier(CasDep,Sender);
}
//---------------------------------------------------------------------------
void __fastcall TForm1::FormPaint(TObject *Sender)
{
/* Recopie le bitmap dessiné dans le canvas de Form1 */
Form1->Canvas->Draw(0,0,BM);
}
//---------------------------------------------------------------------------
void __fastcall TForm1::FormDestroy(TObject *Sender)
{
/* Restitue la mémoire utilisée pour le bitmap */
delete BM;
}
//---------------------------------------------------------------------------
//-------------- H A M I L T O N F I N ------------------------------------
//---------------------------------------------------------------------------Vous trouverez d'autres éléments sur le C++ et l'assembleur ici.