Normalement, l'HP-15C se programme pour réaliser facilement des calculs répétitifs, trouver les racines d'une équation, approximer une intégrale, calculer un sinus ou un cosinus, faire quelques statistiques, etc...
Elle n'a pas de fonction ou de disposition particulière pour mémoriser facilement tout l'échiquier, un affichage numérique sept segments numériques limité, pas de mémoire de masse , pas de système de fichier ou même de tableau et un seul registre permettant l'indexation de ces quelques registres,...
Mais toutes ces limitations n'ont pas arrêté notre ami qui a su passer outre , un par un, avec un grand courage, un peu d'organisation et beaucoup d'acharnement, il a sut proposer un code qui fonctionne selon l'algorithme de Wansdorff, qui contient une bonne dose d'astuces beaucoup d'organisation et de méthode.
Là ou d'autres, dont moi qui dès le début de ce MPO, ont renoncé à implémenter cet algorithme ne croyant pas qu'il permettrait sur une HP-15C d'obtenir une résolution en moins d'une heure ! J'ai préféré utiliser la puissance de l'HP-15C pour mémoriser une solution particulière afin de proposer un code court et rapide qui répond bien au problème du MPO mais ne réalise pas une VRAIE résolution. Juste l'exploitation astucieuse d'un parcourt particulier astucieusement mémorisé et dont une propriété particulière permet de proposer une solution complète quelque soit le point de départ.
La solution que propose Marge utilise plusieurs astuces et dispositifs pour mener à bien l'opération. A ma grande surprise, il ne faut qu'un tout petit plus d'une heure pour résoudre et parcourir l'échiquier, là où je croyait qu'une HP-15C mettrait plusieurs heures.
Une des astuces consiste à mémoriser tout l'échiquier sur uniquement 8 registres qui chacun vont porter l'information pour une ligne (ou une colonne) entière ce qui laisse un seul chiffre par case. C'est normalement suffisant, car par chance l'information à coder ne contient que 8 niveaux (degrés de liberté entre 1 et auquel on doit ajouter une valeur pour marquer les cases déjà parcourues (Marge a choisi la valeur zéro pour cela). Mais c'est suffisant, j'ai même en réserve un programme qui n'initialise pas l'échiquier, où la valeur zéro indique les cases encore indéterminées et où j'utilise la valeur 9 comme jeton pour marquer les cases déjà parcourues. Ca marche, c'est bien plus lent et long, mais cela marche bien.
Une autre difficulté pour implémenter ce type d'algorithme sur une calculatrice et que contrairement aux Pockets, l'accès à l'information pertinente est ralentie car il faut aller chercher un chiffre au milieu d'un nombre dans le registre qui code la ligne (ou la colonne). C'est la tache qui est répétée le plus dans le déroulement de la résolution(*). Il faut donc trouver un moyen suffisamment efficace pour ne pas ralentir les opérations, mais qui soit aussi suffisamment fiable pour ne pas créer d'erreurs d'arrondi.
L'idée géniale de Marge et de découper le nombre contenu dans le registre en trois afin d'accéder à la valeur cible et de garder sous le coude les deux parties afin de les regrouper facilement lorsque l'on aura modifié (soit incrément/décrément pour mettre à jour l'évolution de l'algorithme - soit annuler pour poser un jeton) la valeur. En plus, le même sous-programme (utilisé deux fois consécutivement) permet de recoller les trois parties.
Quel géni !
Une autre astuce que je trouve ingénieuse et l'utilisation de trois drapeaux pour générer la suite des saut du cavalier. C'est important , l'algorithme du Compte de Wansdorf ne fonctionne pas si l'on n'effectue la recherche en tournant dans le même sens tout au long de la résolution.
L'idée d'utiliser trois drapeaux me parait raisonnable, il y a autour du cavalier huit cases à atteindre; utiliser trois drapeaux binaires doit permettre de les énumérer toutes. La motivation étant de pouvoir énumérer dans l'ordre qu'impose la rotation les huit cases sans utiliser l'unique registre d'indexation.
Cette idée d'utiliser des drapeaux me plait bien. Mais malheureusement, la solution proposée par Marge nécessite, pour modifier les drapeaux afin de faire les sauts dans l'ordre rotatif imposé par l'algorithme de Wansdorff d'utiliser justement l'unique registre d'indexation.Marge a écrit : ↑29 août 2020 15:02
Une fois la ligne modifiée et enregistrée (pas 67), les drapeaux sont initialisés, opération nécessaire au début du programme et à chaque tour de la boucle B ; les drapeaux 0 et 3 représentent l'avers et le revers de la même médaille car l'armement de l'un exige le désarmement de l'autre, ils permettent de choisir avec quel registre sera effectuée l'opération :
Les drapeaux 1 et 2 permettent le choix de l'addition ou de la soustraction des entiers 1 et 2 nécessaires pour le déplacement du cavalier. Cette manière de procéder nécessite un changement rigoureux des états des drapeaux qui est géré par le registre I qui envoie le curseur aux étiquettes successives 7 à 1, le huitième ((2^3)-ième) état étant l'actuel (partie jaune du code).Code : Tout sélectionner
(R9 ou R10) (+ ou -) 1 ---> R11 ou R12 └─────────┘└─────────┘ └─────────┘ F0&F3 F1 F0&F3 (R10 ou R9) (+ ou -) 2 ---> R12 ou R11 └─────────┘└─────────┘ └─────────┘ F0&F3 F2 F0&F3
Au cours de l'opération, les tests de sortie de l'échiquier sont effectués (pas 82, 86, 99 et 103) et envoient si nécessaire à la case (dont il faut tester la valeur) suivante au moyen d'un saut pour le même label 0.
Afin, d'éviter cet écueil, j'ai imaginé d'utiliser les trois drapeaux pour compter les sauts en binaire, mais de ne pas utiliser un comptage binaire standard, mais un comptage binaire réflexif (Code de Gray) afin qu'entre deux sauts, un seul bit ne soit modifié, c'est à dire qu'il ne soit nécessaire de ne modifier qu'un seul drapeau.
Ainsi, l'ordre des sauts est respecté en minimisant le nombre d'instructions pour gérer les drapeaux et tout en s'affranchissant complètement d'un compteur ou tout autre registre. Le sous-programme suivant LBL 3 réalise les sauts en initialisant convenablement à chaque fois un seul drapeau avant de donner la main au sous-programme LBL D réalisant la détermination de la position et effectuant l'évaluation/modification :
Code : Tout sélectionner
LBL 3
CF 1 GSB D SF 3 GSB D SF 2 GSB D CF 3 GSB D
SF 1 GSB D SF 3 GSB D CF 2 GSB D CF 3 GTO D
Evidemment, juste en voyant ce code, il est difficile de deviner le codage, qui devient bien plus évident dans le tableau suivant:
Code : Tout sélectionner
n° LBL 3 F1 F2 F3 dir(A~H) dir(1~8) dir
1 CF1 (0) 0 0 +2 +1 +2,1 . . . . . .
2 SF3 0 0 (1) +1 +2 +1,2 7 . 3 . 2 . .
3 SF2 0 (1) 1 -1 +2 -0,8 6 4 . . . 1 .
4 CF3 0 1 (0) -2 +1 -1.9 5 . . x . . .
5 SF1 (1) 1 0 -2 -1 -2.1 4 5 . . . 8 .
6 SF3 1 1 (1) -1 -2 -1.2 3 . 6 . 7 . .
7 CF2 1 (0) 1 +1 -2 +0.8 . . . . . .
8 CF3 1 0 (0) +2 -1 +1.9 B C D E F
En fait, cela se programme très facilement à l'aide de quelques instructions CHS et X<>Y afin de placer les amplitudes dans le bon ordre et avec les bons signes pour faire le calcul du saut.
Code : Tout sélectionner
LBL D
1 ENTER 2
FS? 3 X<>Y
FS? 2 CHS
X<>Y
FS? 1 CHS
...
C'est une méthode que j'utilise très souvent avec les tableaux sur les pockets BASIC qui permettent de définir un échiquier avec une instruction du genre DIM E(8,8); il peut alors être commode et rapide d'utiliser deux variables I et J pour manipuler les éléments d'un tel échiquier 2D.
Mais, l'HP-15C n'ayant pas de réel tableau et ses registres sont indexés linéairement par l'unique registre I dont seule la partie entière agit pour l'indexation. Volonté des concepteurs, la partie fractionnaire est indépendante et peut donc être utilisée pour mémoriser la seconde coordonnée. Dans notre cas, les dixièmes dans I peuvent servir à indexer la case dans la ligne (ou la colonne ) désignée par la partie entière.
Ainsi, dans le tableau précèdent, le x placé en D5 peut être repéré par une valeur unique décimale I = 4.5 (ou dans l'autre sens 5.4 mais je préfère l'ordre plus proche de la notation classique D.5 ) Ce qui pour moi, signifie que le registre R4 contient en fait les cases de la colonne D de l'échiquier et les chiffres du nombre placés dans ce registre représentent les valeurs des cases placées sur chaque ligne.
D'où la colonne du tableau notée dir qui donne l'incrément qu'il faut ajouter à la position I = 4.5 pour énumérer dans l'ordre de rotation les cases voisines.
Utiliser ainsi un registre unique ne me parait avoir que des avantages :
Pour l'affichage du coup, il suffit de faire SCI 1 RCL I RCL 0 10^x * R/S
Pour récupérer le contenu d'une colonne: RCL(i)
Pour préparer un contenu au découpage en trois morceaux : RCL I FRAC 10 * INT 10^X RCL*(i) ce qui placera la virgule juste là où il faut , il n'y aura plus qu'à découper selon les pointillés ...
Et donc me voilà parti pour revoir en profondeur le code de notre ami et maitre.
je vais reprendre les très bonnes idées et astuce de son code en y appliquant quelques uns de mes procédés et préférences.
P.S. : J'arrive ce soir à parcourir l'échiquier en moins d'une heure, record battu sur une HP-15C non véloce comme une Limited-Edition. Malheureusement, le code capable de ce record de vitesse n'utilise pas l'astuce du Code Gray des trois drapeaux. Mais une implémentation plus rapide mémorisant les quatre directions 0.8 1.9 2.1 et 1.2 dans quatre registres dédiés (l'HP-15C n'en manque pas) et n'utilisant qu'un drapeau pour le sens (Sud ou Nord) des saut puisque la même séquence se répète avec des directions positives puis négatives.
EDIT:
(*) Hors la vérification des sauts aboutissant en dehors de l'échiquier, qui, comme expliqué plus loin dans le fil est véritablement l'opération la plus répétée de cet algorithme.