Misez p'tit Optimisez n°91 : balade du cavalier

[C.Ret]

C'est fou quand même ce qu'à réussi à faire notre ami Marge; faire résoudre à une HP-15C le problème du parcours du cavalier par la méthode de Wansdorf sur une machine qui n'a pas réellement était conçue pour ce type de problème.

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.

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 :

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  

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).

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.

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.

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

Autre avantage, à la fin de son déroulé, les drapeaux sont à nouveau placés dans l'état adéquat pour lancer une nouvelle utilisation, plus besoin d'un sous-programme d'initialisation (sauf peut-être un CF 2 etun CF 3 en début de programme pour convenablement initialiser).

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     

On se rend compte alors que F1 et F2 donnent respectivement les signes de dir(1~2) et dir(A~H) et que le drapeau F3 indique lorsqu'il faut intervertir les amplitudes des déplacements horizontaux ou et verticaux 2←→1 ou 1←→2 .
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
  ...

D'ailleurs, le calcul du saut me permet de parler d'un point faible du code proposé par Marge qui utilise beaucoup de registres car il manipule indépendamment les abscisses et ordonnés; ce qui ne manque pas de multiplier le nombre de registres utilisés dans les deux séries de variables.
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.

MPO91 - Chronometrage Varification HP-15C simplification code de Maitre Marge.gif (50.29 Kio) Vu 6487 fois

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.

[Marge]

Bravo ! Je reviendrai là-dessus un peu plus tard...
Et je rougis de confusion devant les qualificatifs au sujet de mon petit mais long travail : je crois n'avoir fait preuve que d'intuition et d'abnégation ; le génie, c'est toi !

[C.Ret]

Héhé, j'y avais pas pensé lors de la première version du raffinement du programme de Marge, mais simplement en remettant les Sous-programmes dans le bon ordre, le gain de temps réalisé lors de la recherche des labels des GTO et GSB permet de passer de 44'53"2 à 35'14"6 pour résoudre à partir de B3 !
j'arrive donc à une détermination moyenne de 33" par coup, c'est pas les 9" de l'algorithme par dé-mnémonisation-polaire-rectangle mais c'est pas mal pour du Wansdorf' !!

C'est bien cette lenteur chronique de la HP-15C, c'est pédagogique, ça démontre qu'il faut non seulement optimiser mais aussi organiser !

[C.Ret]

En perfectionnant encore un petit peu notre code pour HP-15C et en le profilant ( c'est à dire en comptant le nombre de fois que chaque partie est exécutée ) je me suis rendu compte que la grande majorité du temps de calcul était consommée dans les tests des sauts à vérifier qu'il n'y avait pas de débordement de l'échiquier. tests assez complexes selon les implémentations et qui étaient souvent effectués pour rien car dès la fin de la plupart de ces tests, l'algorithme se rend compte sur le tard que l'aboutissement du saut (enfin dans l'échiquier) abouti le plus souvent sur un jeton déjà en place !

C'est flagrant surtout sur les HP-15Cet HP-41C. J'ai donc réfléchit à un algorithme diffèrent, comme pour la recherche des nombres premiers, je cherche un moyen de n'avoir qu'un seul test par case à chaque étape de l'algorithme.

J'ai trouvé le moyen de réduire à un seul test par boucle l'algorithme du Compte de Wansdorff en utilisant l'arithmétique binaire.

Malheureusement, les résultats du MPO n°96 étant très décevants (et cela malgré l'intérêt qu'il a suscité ce Week-End et les nombreux aimables et compétents participants), il me faut toujours deux jeux de registres,

• le premier mémorisant, dans l'ordre de rotation imposé par l'algorithme de WansDorff, les cases voisines toujours actives (ce qui se fait en mettant à un les bits indiquant les sauts dans la direction des cases encore actives),
• le second permettant de compter le nombre de bits à un pour ces mêmes cases afin de sélectionner, pour le saut suivant, la case ayant le plus petit degré de liberté comme le stipule l'algorithme du Compte. (je me serai bien passé de ce second jeu, si quelque aimable esprit génial avait su nous indiquer une méthode simple et efficace...

Je me retrouve donc avec une implémentation bancale qui utilise le double de l'espace mémoire souhaité, mais qui fort heureusement tire profit de cette espace pour très fortement accélérer le déroulement de chaque résolution.

En fait, mon SHARP-PC1360 met pour imprimer le résultat de la résolution de tout l'échiquier le même temps que mon HP-15C pour déterminer en moyenne une seule position suivante.

Peut-être devrais-je chercher un moyen d'implémenter ce nouvel algorithme sur une HP-16C, seule machine ayant l'instruction g #B permettant, sans ajout de mémoire ou de code de déterminer le d.d.l. à partir des bits directionnels encore à un !


Je donne ci-dessous une version de ce nouvel algorithme, les plus curieux pourront chercher à l'adapter à leur pocket préféré:

Code : Tout sélectionner

1 DATA 6,15,17,10,-6,-15,-17,-10
10 DATA  &C,2, &E,3, &F,4, &F,4, &F,4, &F,4, &7,3, &3,2   11 DATA &1C,3,&1E,4,&9F,6,&9F,6,&9F,6,&9F,6,&87,4,&83,3
12 DATA &3C,4,&7E,6,&FF,8,&FF,8,&FF,8,&FF,8,&E7,6,&C3,4   13 DATA &3C,4,&7E,6,&FF,8,&FF,8,&FF,8,&FF,8,&E7,6,&C3,4
14 DATA &3C,4,&7E,6,&FF,8,&FF,8,&FF,8,&FF,8,&E7,6,&C3,4   15 DATA &3C,4,&7E,6,&FF,8,&FF,8,&FF,8,&FF,8,&E7,6,&C3,4
16 DATA &38,3,&78,4,&F9,6,&F9,6,&F9,6,&F9,6,&E1,4,&C1,3   17 DATA &30,2,&70,3,&F0,4,&F0,4,&F0,4,&F0,4,&E0,3,&C0,2
20 INPUT "PRINT ?";B$: PRINT = LPRINT
30 DIM D(7),P(7),S(64),F(64) :I=1: FOR W=0 TO 7: READ D(W): P(W)=I,I=2*I: NEXT W
40 FOR I=0 TO 63: READ F(I),S(I): NEXT I: S(64)=9: WAIT 0
50 BEEP 1: INPUT "Initial POS ";B$ : B= ASC LEFT$ (B$,1)-73+8* VAL RIGHT$ (B$,1): IF B<0 OR B>63 GOTO 110
60 FOR N=1 TO 64:C=B,B=64,S(C)=-N: PRINT USING "###.&&";N; CHR$ (65+C AND 7)+ CHR$(49+C/8);: FOR W=0 TO 7
70 IF F(C) AND P(W) LET I=C+D(W),F(I)=F(I) AND NOT P((W+4) AND 7),S(I)=S(I)-1: IF S(I)<S(B) LET B=I
80 NEXT W: NEXT N: END

Code : Tout sélectionner

0'03"66 to Prompt for "Initial POS _"
1'44"25 to display only all 64 successive positions  (Press directly ENTER when prompt for PRINT ?)
1'51"25 to PRINT them  (Enter 'Y' when prompt for PRINT ?)

Evidemment, j'ai sous le coude une version moins lourde en octets dépourvue (ou presque) de DATA qui construit les vecteurs F() et S() à l'aide de quelque boucle et astuces. Mais le déroulement de l'initialisation est bien plus long; Et c'est bien plus rigolo de saisir sans erreur les 128 valeurs des DATAs. D'autant plus que cela vous permettra d'observer quelques symétries qui vous donneront les indices nécessaires à l'optimisation de ce code.

Quelque soit la méthode d'initialisation, la célérité du code provient du fait que la boucle interne FOR W=0 TO 7 (W comme Wansdorff) n'a qu'un test « IF F(C) AND P(W) LET... » qui conduit à la mise à jour de l'échiquier en deux affectations (personne n'ayant résolu convenablement le MPO 96 je n'ai pas trouvé mieux) et la détection du meilleurs coup ( « IF S(I)<S(B) LET B=I » )
Evidemment, ce code est plus lourds que les versions précédentes de ce fil, mais tellement plus efficace...

MPO91 - Speed print Full board from B3 (CE-126P + SHARP PC-1360).gif (132.72 Kio) Vu 6416 fois

Ce qui est sûr est que si les prochains minipockéticaires organisent une compétions de Speed Knight's Tour Chess Boarding, je ne viendrai pas avec du camembert moyeux mais avec ce code et mon set-up:

[Marge]

Toutes mes félicitations, C.Ret, pour tes travaux remarquables : il est très judicieux d'accélérer le rythme des calculs et ta clairvoyance, cette faculté à lire dans le code, est vraiment impressionnante. Je pourrais invoquer l'inutilité de cette accélération pour la 15C Limited Edition, mais ce serait franchement de la roublardise.

Je te remercie pour ton conseil en privé sur l'utilisation exclusive dans mon code initial du registre I pour l'incrémentation et son opposée alors que ce type d'opérations est également transposable aux autres registres de la 15C - il s'agit encore une fois de ma vieille habitude de la 29C où seul le registre 0 permet l'adressage indirect que j'ai décidément bien du mal à changer...
Grâce à cette remarque qui permet d'éviter les va-et-vient entre le registre 0 et le registre I, on gagne 4 pas dans le code. Je n'ai rien modifié de plus, je te laisse les lauriers bien mérités pour tous tes efforts supplémentaires.

Voici le nouveau code ; les temps ne semblent pas beaucoup changer, à la louche la 15C Limited Edition parcourt tout l'échiquier en 21 ou 22 secondes.

Balade du cavalier.png (201.61 Kio) Vu 6341 fois

Une remarque sur le calcul du nombre d'octets total : selon le manuel d'utilisation de la 15C (p. 218), certaines instructions sont codées sur deux octets (voir la liste ci-dessous) ; j'ai un doute en ce qui concerne le GSB .1, non mentionné, alors que le GTO . l'est ; de plus, je ne sais ce qu'il faut compter pour l'instruction STO+(i) : deux octets ou davantage ? Dans le doute, je n'ai rien compté de plus et je ferai le calcul plus tard en vidant le programme de ma vieille 15C (nouveau décompte, voir plus bas !).

2-byte.jpeg (60.3 Kio) Vu 6387 fois

Edith :"GSB.1 compte autant d'octets que GTO.1 ; STO+(i) pas davantage que STO(i)."

Le nombre total d'octets du programme est de 354, donnée corrigée suite à l'échange privé avec C.Ret - vous n'imaginez pas tout ce qui se dit dans le dark ouèbe silicien ! Je compte les 213 instructions, les 29 instructions codées sur deux octets et enfin dix-huit registres moins les registres zéro et un qui, au même titre que ceux de la pile ou que les registres I et Last x, ne sont pas modifiables en pas de programme.

[C.Ret]

Il y a un moyen très simple pour déterminer la taille d'une instruction sur l'HP-15C.
Il suffit d'utiliser la fonction non programmable (g) MEM qui donne la configuration de la mémoire.

En ce moment, la configuration de mon HP-15C, que je peux lire en maintenant en pressant la touche (g) MEM est 19 20 26-6

Effectivement, j'ai laissé les registres I, R0, R1 , R2 , ... R18 et R19 accessibles (ce qui est la configuration par défaut en fait). Le dernier registre R19 est accessible en effectuant STO.9 ou RCL.9 . Mon code utilise tous les registres jusqu'à R17 inclus.

Au delà des 21 registres (I,R0,R1 à 19) que j'ai réservé à mon usage, il reste donc 46 registres disponibles pour le "pool" et pour le "programme".

Le pool contient les 20 registres qui seront automatiquement utilisés si je fais des calculs en nombres complexe, initialise une matrice, utilise le solver ou l'intégrateur numérique ou ajoute des pas de programme.

Mon programme utilise 25 registres(*) et un byte, il fait donc 176 bytes. C'est la version allégée du code de Marge, il fait le même boulot deux fois plus vite et avec moins de la moitié des pas !

Le "-6" indique qu'il reste exactement 6 bytes disponibles dans le dernier registre utilisé par le programme. C'est la fin du 26ième registre (compté depuis la fin de la zone mémoire) dont le début est déjà engagé dans le programme.
Si j'ajoute une instruction à mon programme, celle-ci sera mémorisée à l'aide de ce petit bout restant.

Ainsi, si je veux savoir combien de bytes fait GSB.2, il me suffit de l'ajouter à la fin de mon programme et de voir de combien bouge la configuration (g)MEM.
Pour cela, il suffit de faire (g)RTN (g)P/R (g)BST GSB.2 (g)P/R je vois alors que (g)MEM affiche 19 20 26-4
Donc, GSB.2 prend deux bytes dans la mémoire d'une HP-15C.

Pour la retirer, je fais simplement (g)P/R (←) (g)P/R et je vérifie que j'ai retrouvé exactement la configuration initiale (g)MEM affiche à nouveau 19 20 26-6.

(*)EDIT 2020/10/02:
Je corrige une épouvantable erreur que je n'aurais certainement jamais vue sans le message privé de Marge qui donne un décompte rigoureux des octets.

Attention, mon post initial contenanait un épouvantable étourderie.
Si (g)MEM affiche 26-6 cela signifie que le 26ième registre est à la frontière entre la zone libre du 'pool' et mon code.
Donc, le code fait seulement 25 registres complets de 7 bits et un seul bit pris sur le 26ième dernier registre.
Le calcul est donc 25*7+1 = 176 (et non pas 26*7+1 comme je l'avais fait initialement).
Le calcul le plus simple est donc de faire 26 * 7 - 6 = 176 bytes

Merci Marge
Heureusement qu'il y en a qui suive, combien ont lu sans voir mon erreur ??

[Marge]

Ainsi, si je veux savoir combien de bytes fait GSB.2, il me suffit de l'ajouter à la fin de mon programme et de voir de combien bouge la configuration (g)MEM.

C'est ainsi qu'Edith a procédé.

J'ai modifié le décompte suite à notre échange.

[Marge]

Bonjour,

à toutes fins utiles, je signale ce programme pour ZX-81 paru dans un vieux magazine familier :



Il faut noter que la détermination du parcours du cavalier se fait au hasard ; il doit donc être possible de parcourir les 64 cases en respectant les règles initiales.

[C.Ret]

Bonjour,
[...]
Il faut noter que la détermination du parcours du cavalier se fait au hasard ; il doit donc être possible de parcourir les 64 cases en respectant les règles initiales.

Cela peut arriver en théorie, en pratique je ne suis pas sûr qu'une seule vie soit suffisante pour l'observer.

Je crois que la plupart du temps, le cavalier fou va se coincer quelque part bien avant de parcourir les 64 cases de l'échiquier.

Les pièces d'échec sont connues pour aller facilement se mettent à des endroits incongrus où elles finissent bloquées puis prises par l'adversaire.

Cela me rappelle l'histoire du cavalier d'échec de Daniël Karssen qui reste bloqué sur un échiquier de taille infinie !


P.S.: Il n'y a pas que le cavalier d'échec qui est fou dans cet article, il y aussi l'utilisation à outrance de CODE "#" pour économiser quelque octet ainsi que l'utilisation de PI. Le Sinclair ZX81 aurait-il un souci de représentation des nombres entiers d'un seul chiffre pour que de telles séquences de touches soient plus économiques (en octets consommés) que de saisir simplement et directement des entiers d'un ou deux chiffres ??

Je trouve cela fort peu lisible.

J'ai donc retranscrit ci-dessous le "code en clair" c'est à dire en consommant quelques octets de plus expliciter les calculs:

Code : Tout sélectionner

 10 LET S=1
 20 LET A$="56653223"
 15 LET B$="653223"+A$+"56"
 17 LET A$=A$+A$
 25 FOR I=1 TO 8
 30    FOR J=5 TO 8
 35      PRINT AT I+I,3*J;"."
 40    NEXT J
 45 NEXT I
 50 INPUT I, J
 66 PRINT AT I+I,3*J;S
140    LET Z=INT (8*RND+1)
145    FOR Z=Z TO 8+Z
146         LET A=I+VAL A$(Z)-4
147         LET B=J+VAL B$(Z)-4
148      IF A<1 OR B<1 OR A>8 OR B>8 THEN NEXT Z
150      PRINT AT A+A,3*B;
160      IF PEEK (PEEK 16398+256*PEEK 16399)=CODE "." THEN GOTO 200
170    NEXT Z
180    PRINT AT 20,0;S;U ■ 
200    LET I=A
210    LET J=B
220    LET S=S+1
230 GOTO 66

(N'oubliez pas l'instruction d'arrêt à la fin de ligne 180 qui sur le listing de l'OP est bien trop discrète)
EDIT: Il s'agit en fait d'afficher une variable qui n'a pas était initialisée, le déroulement du programme s'arrête donc sur une erreur. J'ai mi un petit carré pour marquer l'endroit.

[Marge]

Merci pour ces éclaircissements, mais j'ai un peu du mal avec le BASIC du Sinclair : à la ligne 150, on termine sur un point virgule, vraiment ? c'est visiblement le cas à la ligne 150 du programme original, mais ça me semble bizarre, dans mon BASIC du Sharp PC-1403, le point virgule sert à apposer des caractères aux chiffres de l'écran...

Sinon il semble y avoir un petit problème de numérotation de lignes au début, mais c'est vraiment pour montrer que je connais le BASIC.

[C.Ret]

Sur les 8bits, le PRINT finit par un point-virgule pour laisser le "curseur" au bout du texte (ou du nombre). L'instruction PRINT suivante continuera à cet endroit sans qu'il y ai de retour de ligne. Sur certaines versions, on peut aussi finir avec une virgule ce qui sépare les données de quelques espaces afin d'aligner les données affichées sur les colonnes multiples de 8 ou 10 caractères.

Dans le cas de la ligne 150, l'affichage est positionné (instruction AT ligne,colonne mais rien n'est affiché, ce qui laisse le "curseur d'affichage" virtuel à cette position afin de lire le contenu de l'affichage à l'aide de l'instructions PEEK de la ligne suivante qui lit l'octet "sous" le "curseur d'affichage". Si le code renvoyé par cette instruction PEEK est justement le CODE de "." cela signifie qu'il n'y a pas de nombre à cet endroit de l'affichage et donc on se branche sur la ligne 200 qui déplace le cavalier (I,J) sur les coordonnées (A,B) et affiche le numéro du jeton S (ligne 66 PRINT AT I+I,3*J;S) ce qui affiche le déplacement du cavalier et également verrouille la position (I,J) qui ne contient plus le "." marqueur des positions libres.

Sur les Pockets BASIC, la syntaxe du PRINT est moins permissive que sur les micro-ordinateur, cela provient simplement de la taille de l'affichage et du fait qu'il n'y ait qu'une seule ligne et que le "saut de ligne " ne peut être effectué avant que l'utilisateur n'ai signifié qu'il à lu l'affichage par une pression sur ENTER, RETURN ou EXE.
Sur les micro, tout PRINT qui se termine sans ponctuation crée un "saut de ligne" qui éventuellement, si l'on est un bas de l'affichage crée un défilement vers le haut.

L'air de rien, l'astuce de ce programme n'est pas aisée à reproduire sur tous les micro sans une bonne connaissance de leur fonctionnement afin d'adapter l'adresse du PEEK à effectuer; Rares sont les BASIC qui ont une instruction de lecture des caractères affichés. Et pour certain micro de cette époque que j'ai pratiqué, la détermination du PEEK à effectuer peut être très compliquée selon la configuration exacte du système lors du lancement du programme.

Voici la traduction pour CBM 8001/8032, Super PET, VIC 20 (muni de la cartouche d'extension Super Expander) et C128/C1128D en mode 40 ou 80 col :

Code : Tout sélectionner

10 s=1:a$="56653223":b$="653223"+a$+"56":a$=a$+a$:open 3,3:print#3,chr$(147)
20 for i=1 to 8:for j=1 to 8:char 1,3*j,i+i,".":next j,i
30 char 0,0,18:input "initial pos l,c ";i,j
40 char 1,3*j,i+i,mid$(str$(s),2):z%=1+8*rnd(1)
50 for z=z% to 8+z%: a=i+val(mid$(a$,z,1))-4:b=j+val(mid$(b$,z,1))-4
60 c$="":if a>0 thenif b>0 thenif a<9 thenif b<9 then char 0,3*b,a+a:get#3,c$
70 if c$<>"." then next z:char 1,0,20,str$(s):close 3:end
80 i=a:j=b:s=s+1:goto 40

Ce code n'utilise pas de PEEK mais l'instruction de lecture GET qui lorsqu'elle est liée au canal #3 lit le contenu de l'écran.
Le canal logique de l'écran est ouvert avec l'instruction OPEN 3,3. Ce canal est ouvert en lecture/écriture. Le code CHR$(147) correspond au caractère d'effacement de l'écran (touches SHIFT+CLR/HOME). L'instruction GET#3,C$ lie le code PETscii sous le "curseur d'affichage" qui est positionné par l'instruction CHAR qui est l'équivalent d'un PRINT AT.


Pour le PET, les CBM 4000, le VIC 20 sans extension et le Commodore C64 qui n'ont pas de CHAR, on peut palier à son absence à l'aide d'un sous programme utilisant les codes de déplacements curseur ou une instruction PEEK pour lire le dans la mémoire caractère de l'écran mais l'adresse à lire dépend de chaque système, et pour un système donné de la quantité de RAM installée, la page écran étant déplacée selon la configuration mémoire.

Code : Tout sélectionner

10 s=1:a$="56653223":b$="653223"+a$+"56":a$=a$+a$:open3,3:print chr$(147)
20 for a=1 to 8:for b=1 to 8:gosub 100:print ".":next b,a:print
30 input "initial pos l,c ";a,b
40 i=a:j=b:gosub 100:print mid$(str$(s),2):z%=1+8*rnd(1)
50 for z=z% to 8+z%: a=i+val(mid$(a$,z,1))-4:b=j+val(mid$(b$,z,1))-4
60 c$="":if a>0 thenif b>0 thenif a<9 thenif b<9 then gosub 100:get#3,c$
70 if c$<>"." then next z:b=0:a=10:gosub 100:print s:close 3:end
80 s=s+1:goto 40
100 d$=left$("↓↓↓↓↓↓↓↓↓",a):e$=left$("→→→→→→→→",b):print "♥"e$d$e$d$e$;:return

Pour le C64, la version avec un PEEK ressemblerai à cela: notez que comme il n'y a pas de PRINT AT ou CHAR, le plus facile est de d'utiliser un POKE pour afficher les "." (code d'affichage 46) et deux POKE pour les numéro de jetons.

On obtient donc un code avec quelques PEEK, POKE , GOTO mais un seul PRINT:

Code : Tout sélectionner

10 r=32:s=49:a$="56653223":b$="653223"+a$+"56":a$=a$+a$:sc=1144:print chr$(147);
20 for a=1 to 8:for b=1 to 8:poke sc+80*a+3*b,46:next b,a
30 input "initial pos l,c ";i,j
40 poke sc+80*i+3*j-1,r:poke sc+80*i+3*j,s:z%=1+8*rnd(1)
50 for z=z% to 8+z%: a=i+val(mid$(a$,z,1))-4:b=j+val(mid$(b$,z,1))-4
60 c=0:if a>0 thenif b>0 thenif a<9 thenif b<9 then c=peek(sc+80*a+3*b)
70 if c<>46 then next z:b=0:poke 1904,r:poke 1905,s:end
80 i=a:j=b:s=s+1:if s>57 then s=48:r=(r or 16)+1
90 goto 40

Le plus général est donc d'utiliser un autre moyen pour marquer les positions encore libres.

[Marge]

Merci pour cette profusion de détails, C.Ret !
Je ne connaissais sur "grand" écran que le BASIC du TRS-80 qui, dans mon souvenir de près de quatre décennies, ne propose pas ces subtilités de saut de ligne - je n'étais cependant pas davantage un spécialiste des langages informatiques à l'époque.

[C.Ret]

Mais de rien.

En fait, le Sinclair ZX-81 est une machine très capable :

MPO91 - Full board solved on SINCLAIR ZX81.gif (23.55 Kio) Vu 6172 fois

Et ceci avec un code BASIC non optimisé. Je suis sûr qu'il doit y avoir moyen de faire bien plus court, et aussi plus rapide (notamment si l'on ne dessine plus l'évolution de l'algorithme au fur et à mesure de la progression )

MPO91 - Full board solve begins on SINCLAIR ZX81.gif (13.59 Kio) Vu 6172 fois

MPO91 - Full board solve ends on SINCLAIR ZX81.gif (20.35 Kio) Vu 6172 fois

Code : Tout sélectionner

  4 LET S$="22356653"
  6 LET T$="35665322"
  8 DIM E(8,8)
 10 FOR I=1 TO 8
 12  LET C$=CHR$(165-I)
 14  PRINT AT I,0;C$
 16  PRINT AT I,27;C$
 18  LET A=9-I
 20  FOR J=1 TO 8
 22   LET C$="#"+CHR$(165+J)+"#"
 24   IF I=1 THEN PRINT AT 0,3*J;C$
 26   IF I=8 THEN PRINT AT 9,3*J;C$
 28   LET B=9-J
 30   LET R=I+J
 32   IF R>4 THEN LET R=4+2*(J>1)
 34   LET E(I,J)=-R
 36   IF A<I THEN LET E(I,J)=E(A,J)
 38   IF J>2 THEN LET E(I,J)=2*E(I,1)
 40   IF B<J THEN LET E(I,J)=E(I,B)
 42   PRINT AT I,3*J,E(I,J)
 44  NEXT J
 46 NEXT I
 48 LET I=11
 50 LET J=0
 52 PRINT AT 18,0;"INITIAL POS:"
 54 INPUT P$
 56 LET U=9-   CODE P$(2)
 58 LET V= CODE P$(1)-38
 60 PRINT AT 18,12;P$
 62 FOR N=1 TO 64
 64  LET X=U
 66  LET Y=V
 68  LET R=-8
 70  LET E(X,Y)=N
 71  LET P$=CHR$(37+Y)+CHR$(37-X)
 72  PRINT AT I,J,P$
 74  PRINT AT X,3*Y;" ";N
 76  FOR Z=1 TO 8
 78   LET A=X+VAL(MID$(S$,Z,1))-4
 80   LET B=Y+VAL(MID$(T$,Z,1))-4
 82   IF A<1 OR B<1 OR A>8 OR B>8 THEN GOTO 98
 84    IF E(A,B)>0 THEN GOTO 98
 86     LET E(A,B)=1+E(A,B)
 88     PRINT AT A,3*B,E(A,B)
 90     IF E(A,B)<=R THEN GOTO 98
 92      LET U=A
 94      LET V=B
 96      LET R=E(A,B)
 98  NEXT Z
100  LET J=J+3
102  IF J<31 THEN GOTO 108
104   LET I=I+1
106   LET J=0
108 NEXT N

EDIT: Je n'ai pas trouvé sur l'émulateur que j'ai utilisé comment afficher la mémoire disponible ou restante et donc je n'ai pas la taille exacte de ce code que j'ai estimé à 812 octets. Je ne suis donc pas loin de la limite des 1K utilisable de cette petite machine bien surprenante.

Si un utilisateur plus spécialiste de l'engin que moi pouvait me confirmer que mon calcul a un sens; j'ai compté 4 octets pour le numéro de ligne et son adresse binaire, un octet par tocken des instructions basiques, puis un octet par symbole ou caractère et un octet pour marquer la fin de ligne (le NEW LINE).
Mais je ne suis pas sûr que c'est ainsi que s'encode les lignes, notamment les valeurs numériques sont peut être codées sur deux octets ou plus ??

[Marge]

Bonjour,

Dis, C.Ret, j'ai cherché ton code adapté de mon programme pour HP-15C, mais tu n'as publié ici qu'une version BASIC. Cela t'embêterait de publier la version RPN ? J'aimerais comparer les temps d'exécution des deux machines (petite et grande sœurs) et avec ta permission, publier ton code (avec tous les honneurs !) dans le fil Knight's Tour du HPM où réside déjà le mien, ou bien simplement un lien vers ici - ou même, tu pourrais publier toi-même ton code sur l'HPM dans le même fil, pourquoi pas ? Merci !

[C.Ret]

Mais avec grand plaisir surtout que la version rapide en BASIC découle de cette version non publiée utilisant la résolution par l'algorithme du Compte de Wansdorff pour HP-15C. Ma version HP-15C est en réalité très exactement la version de Marge relue et remodelée afin de tirer partie de l'arithmétique en mémoire (STO+/RCL+) et de suivre les sept prédicats suivants :

-1- Utiliser un seul indice par case de l'échiquier; comme pour la version par dé-mnémonisation-polaire-rectangle utiliser la valeur entière pour les colonnes (ou les lignes si l'on veux, cela revient au même) et les dixièmes pour indiquer la position dans la dite colonne (ou ligne).

Ainsi, 1.1 désigne la case A1, 5.3 la case E3 etc.

-2- Utiliser les registres R1 à R8 pour mémoriser l'état de l'échiquier.: l'idée est d'utiliser le registre d'adressage indirect comme le fait la version du Maître. Et donc d'utiliser (i) pour faire référence aux cases de l'échiquier. Les registres correspondent donc aux colonnes.

-3- Coder l'état de chaque case de l'échiquier à l'aide du code digital suivant :
'0' : case inconnue, ce code est le reliquat d'une version plus ancienne et plus lente qui n'initialisait pas l'échiquier mais calculait les degrés de liberté à l'aide d'une boucle supplémentaire exactement comme le fait la version publiée pour HP-41C.
'1' ~'8' : degré de liberté de la case: c'est à dire le nombre de cases voisines accessibles par le cavalier d'échec encore disponibles.
'9' : case occupée par un jeton. Code qui ne sera finalement pas utilisé dans la version ultime pour HP-15C (voir explication paragraphe suivant)

-4- Initialiser l'échiquier avec les degrés de liberté: finalement, je me suis ravisé en cours de développement, la solution remplissant les registres R1 à R8 dès le début est plus rapide et plus efficace que ma solution par le calcul. Le temps de calcul des cases encore inconnues est loin d'être négligeable et ne produit pas un code plus court.
Effet corollaire, je n'ai plus besoin du code '9', remettre à '0' les cases occupées par un jeton (celles où le cavalier est déjà passé) est plus simple à faire (un petit CLx des maisons) et plus facile à tester (x=0?)

-5- Ne pas utiliser le registre I pour balayer les cases voisines accessibles: comme expliqué dans un de mes précédents posts, je trouve l'idée d'utiliser les drapeaux très astucieuse. En utilisant un code binaire réflexif (Code de Gray), il est possible d'optimiser le mécanisme des drapeaux en ayant qu'un seul des trois drapeaux à manipuler pour chacune des 8 cases voisines; Et en prime, les trois drapeaux se retrouvent dans l'état initial à l'issue du cycle balayant les 8 cases.

Cela marche fort bien, mais je n'ai gardé que le drapeau F1 car cette solution avait l'inconvénient de nécessiter à chaque fois de calculer l'adresse de la cellule voisine. Or, les 'offsets' sont identiques et au signe près, il n'y en a que 4 de différents. d'où l'idée de les mémoriser lors de l'initialisation;

-6- Mémoriser les quatre 'offsets' permettant de calculer les indices des cases voisines et utiliser le drapeau F1 pour parcourir les deux signes.
Si l'on considère que le cavalier est sur la case d'indice (5.5), on se rend compte que que les huit cases voisines accessibles par le cavalier sont(dans l'ordre) les case d'indices (6,3) (7,4) (7.6) (6.7) (4.7) (3.6) (3.4) et (4.3) . c'est à dire aux indices décalés des 'offsets' suivant +0.8 +1.9 +2.1 +1.2 -0.8 -1.9 -2.1 et -1.2

L'astuce des trois drapeaux permettait de balayer les huit cases voisines en modifiant l'état d'un drapeau et en appelant le sous-programme de test qui commençait par calculer ces 'offsets'. Comme ce sont les mêmes à chaque fois, il est plus rapide de les mémoriser dans quatre registres.

Le balayage des huit cases voisines se fait donc par deux appels d'une même sous-routine qui rappelle successivement les quatre registres et le sous-programme de test qui changera le signe de l'offset en fonction de l'état du drapeau F1 (FS?1 CHS) et l'ajoutera à la position en cours par un simple RCL+.0

-7- Couper le registre codant une colonne en trois puis recoller els trois morceaux :Pour lire ou modifier l'état d'une case, il faut pouvoir facilement extraire le chiffre correspondant du registre concerné et placer ce chiffre dans le registre X: où il sera testé, remis à zéro ou modifié; Puis, éventuellement, facilement reconstituer l'intégrité du nombre pour le remettre dans le registre en question.
Là aussi, je me suis inspiré de la solution géniale de Marge, en découpant le registre en trois morceaux que je garde dans la pile (registres Y et Z) prêt à être réassemblés en quelques opérations simples.
Comme il s'agit de nombres décimaux, les multiplications ou divisions nécessaires aux démontage du registre colonne puis à son remontage utilisent un registre contenant le facteur 10 et un registre contenant 10^I où l est l'indice de ligne c'est à dire la fraction décimale de I = c.l.
Afin de n'avoir qu'un minimum d'opérations à effectuer pour découper ou recoller le registre colonne, un décalage systématique est observé dans la position des décimales. Ainsi, le codage initial des registres R1 à R8 est fait de la façon suivante :
R1 = 0.023444432
R2 = 0.034666643
R3 = 0.046888864
etc.
Afin que les deux coupures se fassent aux bons endroits avec un minium d'opérations (multiplication/division par 10 ou 10^L, partie entière, partie fractionnaire, additions).

La procédure qui recolle utilise le fait que l'addition est commutative. De la même façon que Marge qui mémorise la valeur de l'état de la case en l'ajoutant dans la partie entière du registre, j'utilise la duplication automatique du registre T: pour recoller les morceaux et remplir le haut de la pile avec la valeur modifiée ce qui permet de la retrouver plus loin dans le code pour la comparer avec le d.d.l. min du registre R.1


Outre ces sept principes, il y a aussi un point faible à mon code qui concerne le test vérifiant que l'indice est bien sur l'échiquier. Comme chaque case est indexée par une seule coordonnée C.L, il faut à chaque fois en extraire parties entières et fractionnaires et les comparer à 1 et 8 pour détecter les cases qui sont hors de l'échiquier.
Ce n'est pas une mince affaire, d'autant plus que c'est là l'opération la plus répétée de tout le code. En effet, les tests avec 1 et 8 seront répétés 1026 fois à chaque résolution d'un échiquier (à chaque utilisation du programme).
La performance de ce bout de code est donc ce qui détermine la performance de l'ensemble, les autres opérations étant répétées de bien moins nombreuse fois sauf peut-être le sous-programme "d'ouverture" d'une colonne pour extraire l'état d'une case. Le recollage étant exécuté bien moins souvent - uniquement lorsque l'état d'une case est modifié .

Pour tenter de gagner un peu de temps, le principe de ce sous-programme (LBL-E) et de celui de l'analyse des cases voisines (LBL 4) est basé sur celui de la passoire: si la case ne convient pas, comme une passoire qui ne retient pas les liquides, l'on sort du sous-programme et l'on retombe dans le niveau appelant à l'aide d'un RTN. L'idée est que le premier échec évite ainsi d'avoir à parcourir tout le sous-programme et donc de réaliser tous les tests.

Je donne ci-dessous dans mon listing le nombre de répétitions de chacune des instructions. Il s'agit du nombre total d'itérations de chaque instruction du code à l'issue de la résolution complète de l'échiquier. Le nombre total de répétitions des instructions observé est le même quelque soit la case initiale, sauf pour les instruction 101 à 105.
Les instructions 101~105 sont répétées un nombre différent de fois en fonction de la case initiale. Je donne les répétitions observées après avoir commencé par B3 et H8. Les différences proviennent du fait que les meilleurs cases n'apparaissent pas dans le même ordre à chaque cas.

Ces variations sont minimes par rapport à l'ampleur des taches que doit effectuer cette pauvre HP-15C pour suivre l'algorithme de Wansdorff.

D'où d'ailleurs l'idée du code BASIC qui limite fortement toutes ces répétitions, et notamment les répétitions du test d'appartenance à l'échiquier et le balayage systématique des huit positions voisines. L'astuce du code binaire et de la détermination du "nombre de bits à 1" réduisant drastiquement toutes ces répétions. Malheureusement, l'HP-15C est dépourvue d'instructions binaires qui rendrait cette approche efficace; Et l'HP-16C qui les possède n'a pas un nombre de registres binaires suffisant.

Le code ci-dessous est lent, car il faut "ouvrir" de multiple fois les registres contenant l'échiquier pour obtenir l'état des huit cases voisines pour se rendre compte que souvent, elles sont déjà occupées par un jeton ou qu'elles ont un degré de liberté plus important que la meilleure case en cours. La découverte d'une meilleure case voisine n'arrive que 81 à 87 fois pour 336 cases "prospectées".


Enfin, et pas des moindre sur le temps d'exécution, est l'ordre des sous-programme. Il faut être vigilent et faire attention à l'ordre des 'appels des sous-programmes afin de limiter la "distance de recherche du label"; le temps perdu est proportionnel aux nombres d'appels ce qui est loin d'être négligeable pour les sous-programmes appelés en boucle. Par contre, comme l'HP-15C mémorise la position du GSB appelant, le retour à l'instruction suivante est presque instantané.
Comme je l'indiquait dans un de mes précédent posts, en remaniant l'ordre des sous-programmes de mon code, j'ai eut la bonne surprise de voir les calculs plus rapides et passer en dessous de la minute par coup.

MPO91 - HP-15C méthode Wansdorf - Simplification code de Marge.gif (188.59 Kio) Vu 6023 fois

Usage:
Saisir indice case initiale C.L (par exemple 2.3 pour la case B3 ou 5.5 pour E.5, etc) puis pressez sur f-D pour lancer.
f-A permet d'afficher la dernière position déterminée qui s'affiche "C.L nn" avec C.L indice colonne/ligne de la case et nn compteur de jetons (= " positions placées). Depuis cet affichage, faire R/S pour lancer le calcul de la position suivante.
f-C permet de continuer (équivalent au R/S après f-A)
f-E permet de vérifier que la position est valide (dans l'échiquier). Un affichage clignotant indique une position hors de l'échiquier (drapeau indicateur d'erreur F9 activé).

Registres:
R0: Numéro du de jeton (varie de1 à 64)
R1 ~R8 : Echiquier
R9 : Constante décimale
R.0 : Position en cours du cavalier.
R.1 : Valeur minimale du degré de liberté des cases voisines.
R.2 : Meilleure position pour le prochain saut (=case voisine de d.d.l. minimum)
R.3 ~R.6 : valeur absolue des 'offsets' pour saut aux cases voisines.
R.7 : Facteur de division pour coupure du registre en fonction de la ligne cible
Flg1 : Direction + ou - du saut
Flg9 : Indicateur de saut hors échiquier


Entrée/Sortie par label:
LBL D : Entrée X:=indice C.L case initiale Sortie : ..
LBL A : Entrée/Sortie: néant/néant, Affiche "C.L nn" position courante puis R/S déterminer la position suivante.
LBL C : Entrée/Sortie: néant/néant, Détermine puis affiche la position suivante.
LBL 1 : Entrée X:= indice C.L case à "ouvrir" contenant l'état des cases 0.0abcd(e)fgh - Sortie I:C.L, Z: abcd , Y: 0.fgh, X: e
LBL 2 : Entrée I:C.L, Z: abcd , Y: 0.fgh, X: e - Sortie T:Z:Y:e, X:R(i):0.0abcd(e)fgh
LBL 3 : Entrée Flg1: + ou - - Sortie : R.1 et R.2 (meilleure position et d.d.l. minimal)
LBL 4 : Entrée X:|offset| - Sortie : Flg9, R.1 et R.2 (meilleure position et d.d.l. minimal)
LBL E: Entrée X:Indice case C.L - Sortie : X:Indice case ou indicateur d'erreur Flg9

Pour compter comme Marge:
149 instructions dont 26 codées sur deux octets soit 175 bytes de code utilisant les registres fixes RI: R0: et R1: ainsi que les registres
variables de R2 à R.7 (inclu), soit un total de 287 "octets"

Chronométrages:

MPO91 - Chronometrage Varification HP-15C simplification code de Maitre Marge.gif (50.29 Kio) Vu 6020 fois

Sur uneHP-15C classique, moins de 44 s en moyenne par position.