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

[steste]

Bravo....

?

....Marge, jolis et long
programme, on sent la sueur due
a la météo capricieuse. boul boul boul, super!

Salut, st

[Marge]

Merci, steste, mais bon, la météo a bon dos...

Je trouve que je faiblis... si c'était encore possible tant j'étais déjà faible

Mais on va y arriver !

[gege]

Bonjour,
Aurais-tu un listing pour tester le problème du x=0? ?
Très intéressant !
Merci,
G.E.

[Marge]

Bonjour, gege,
Oui, c'est prévu, mais chaque chose en son temps - ah, ces jeunes, toujours pressés !

[Marge]

a2 - c1 - a2 - b4 - a6 - b8 - d7 - f8 - h7 - f6 - g8 - e7 - g6 - h8 - f7 - d8 - b7 - a5 - b3 - a1 - c2 - a1 - a1 - a1 (ad lib.)...

Mais qu'a-t-il dans la caboche, ce maudit canasson ?

P.-S. : Problème identifié (ein großes Problem...)

[steste]

Salut marge,

Donc, ce qui est en rouge, c'est
les sauts faux.
(Ce qui devrait être un désastre pour la suite mais
les sauts suivants, pourquoi son-t’ils justes ?)

A tu une explication logique (des problèmes) a nous fournir
avant de laisser tomber.

Ton programme est plus impressionnants, tout
les programmes longs sont impressionnants.

Pourquoi ces chiffres rouges de m.... ?

SIC:
Je crois avoir compris le principe de l'analyse
"polaire/triangulaire" !

c'est tout, salut tout le monde, bonne journée, ste

..

[Marge]

Bonjour, Steste,

En fait, les coordonnées rouges ne devraient pas apparaître parce que la case a déjà été parcourue. Dans ma représentation de la balade du cavalier avec les registres 1 à 8 contenant les valeurs de sauts potentiels de chacune des cases de l'échiquier sur huit décimales, cette erreur se produit parce qu'un décalage involontaire est malheureusement effectué lors de la routine de séparation du registre en trois parties entières si le début de la rangée commence par la valeur '0', ce qui est le cas grâce au placement initial qui met le cavalier sur la première colonne. Le décalage provoque alors l'erreur car le zéro est remplacé par le '4' qui devrait correspondre à B2 - et non A2.

Je ne désespère pas de trouver une solution à ce problème : il suffit de retourner les parties de gauche et de droite en décimales, et non en entiers, mais ça prend beaucoup de pas supplémentaires et je me trouve vraiment à la limite de ce que peut la 15C. Pour le moment, j'ai essayé de gagner de la place mais je crains de devoir commencer à mordre sur l'initialisation - ce que je n'aime pas car je préfère largement un programme totalement autonome : on entre l'emplacement initial et zou...

Dans le pire des cas, j'adapterai le programme à la HP-41CV, au besoin en utilisant un module Double-MEM ; je préférerais tout de même terminer cela relativement rapidement sur la 15C.

copie.jpg (45.09 Kio) Vu 5500 fois

Photo Chess Bazaar

[Marge]

Mission accomplie :

Springer.png (126.21 Kio) Vu 5470 fois

J'éditerai les commentaires plus tard. Le code est finalement plus court que prévu.

Entrez x, [ENTER], y [GSB] [A], puis R/S entre chaque coup. C'est quasi-instantané sur la 15C LE.

P.-S. : la routine 8 est en cours d'amélioration (ce qui saute au yeux...).

[C.Ret]

Woaw...

Là il va falloir que je prennes un bon café noir et que je m'y colle sérieusement... Il y a de la technique.
D'abord, il va falloir que je révise mes bases, je ne sais plus comment dans quel ordre les labels multiples sont appelés. Car là il y a plusieurs fois le même label, et je sais plus...

En suite, il y a des GTO et des GSB B C D .0 , ça c'est OK. Mais tous plein de labels de 0 à 8 mais pas de GTO ou GSB 1,2 ,3 etc. Ruse ?
Ah! Il y a un GTO I, faut donc aussi que je révise les appels indexés, je sais plus non plus ...

Enfin, il y une utilisation plus qu'astucieuse des drapeaux, j'attends avec impatience les explications et indices pour comprendre, parce que là ça fait beaucoup d'info à gérer d'un seul coup.

Chapeau bas et Coup de Maitre très cher Marge.

Je commence à comprendre pourquoi je n'arrivais pas à implémenter un Wansdorf sur une HP-15C...

Et le détail qui me tue, "c'est instantané sur une HP-15 LE" -Pfouf je suis jaloux comme un poux ...

[steste]

Salut !

BEAUCOUP ! ...de travail....

Les limites (?) de la série Pionnier
il me semble.

Tu est certainement le seul a le
comprendre ce programme...

BRVO !

a plus,

very well...

st

[Marge]

Merci, C.Ret. Je dois avouer que je n'aurais jamais pu terminer ce programme sans ton allant ni tes encouragements.

Merci également, Steste, pour avoir manifesté ton intérêt et ton enthousiasme pour mon petit travail (finalement à la portée de tous, avec de l'opiniâtreté).

Il est tard et la semaine a été longue, j'ai commencé une explication mais viens de me rendre compte que je pouvais encore gagner trois pas : cela modifie le programme, la représentation du code et les explications elles-mêmes, permettez-moi donc de les remettre à demain samedi après-midi, en soirée pour vous. À bientôt !

[gege]

Bonjour;
Ca a l'air super, on attend avec impatience les explications !
Une lecture rapide et hop... je n'ai rien compris.
A+
G.E.

[Hobiecat]

Avec les couleurs, on comprend à peu près la structure générale, mais ensuite viennent les LBL identiques et le GSB I et là ça se corse un peu.

En tout cas, ça reste plus lisible que du RPL.

[Marge]

Voici donc le programme a priori définitif(*) qui permet à une HP-15C, une HP-15C Limited Edition - ou une quelconque application pour téléphone ou ordinateur se comportant de la même manière - de résoudre ce problème. Il doit être possible de le faire également fonctionner sur une HP-41CV sans trop de modifications, et même sur une HP-67 - mais pas encore plus facilement, comme j'ai pu l'écrire un peu vite... et même peut-être pas du tout.

L'heuristique utilisée est celle du génial Herr Warnsdorf qui découvrit en 1823 un moyen infaillible de parcourir toutes les cases de l'échiquier sans perte de temps (comme on le dit aux échecs, c'est-à-dire sans perte de mouvement) en choisissant toujours une case de plus faible valeur de potentiel de sauts parmi celles légalement disponibles. Chaque case de l'échiquier est à cet effet définie par sa valeur initiale telle que décrite dans le diagramme suivant :

Code : Tout sélectionner

2 3 4 4 4 4 3 2
3 4 6 6 6 6 4 3
4 6 8 8 8 8 6 4
4 6 8 8 8 8 6 4
4 6 8 8 8 8 6 4
4 6 8 8 8 8 6 4
3 4 6 6 6 6 4 3
2 3 4 4 4 4 3 2

Le programme est complet : une fois introduit dans la machine, on presse l'abscisse d'entrée (x), puis [ENTER], puis l'ordonnée (y) et enfin [GSB] [A]. Le programme affiche d'abord les coordonnées de cette première case ainsi que le numéro du coup (par exemple : 1,2______01) ; une pression sur [R/S] commence et poursuivra le cheminement du cavalier.

Voici le code suivi de quelques nécessaires explications.

Knight15.png (118.63 Kio) Vu 5357 fois

Pas 001-038 : Initialisation

Une fois les coordonnées entrées, la pression sur [A] formate l'affichage, puis efface tous les registres ; suit le stockage des coordonnées initiales puis l'emplissage des registres 1 à 8 sous forme décimale inférieure à 1 (la partie entière servira dans la routine 9) ; on termine par l'initialisation du registre 0 avec sa limite supérieure en partie décimale.

Pas 039-146 : Boucle principale et Calcul déplacement

Les couleurs utilisées dans le code doivent permettre, je l'espère, de comprendre que cet ensemble constitue l'âme du programme : ici on gère l'affichage (pas 54 , R/S) et le déplacement du cavalier (le registre I sert dans ce premier cas à connaître le numéro du mouvement sur l'échiquier) : si le numéro du déplacement atteint 64, on s'arrête avec le Return (pas 57).
Le pas 58 voit apparaître un deuxième LBL B (une vieille habitude maintenant de réutiliser les étiquettes antérieures du programme héritée de l'utilisation de la HP-29C, simplement un saut pour reprendre la course si la case 64 n'est toujours pas atteinte) et on procède à une interversion des registres 0 et I pour la suite : le registre 0 ne sera plus nécessaire pendant ces opérations mais le registre I, grandement !
Le travail qui commence alors est de mettre la valeur de la case où se trouve le cavalier à zéro : on place donc les coordonnées actuelles dans les registres I (y, ou ligne) et x (x, ou colonne), puis on appelle les routines 9 (séparation de la ligne I en trois parties pour la pile : x : Valeur en entier ; y : 1ère partie et z : 2ème partie, toutes deux en décimales inférieures à 1) et 8 (assemblage de l'ensemble de la ligne) avec la mise à zéro de la valeur de la case où se trouve le cavalier entre les deux routines. C'est à cet endroit que j'avais perdu beaucoup de pas lors de la confection du précédent programme à laisser ces deux extrêmes de la ligne de l'échiquier représentés par des entiers - mais vous savez ce que c'est : on commence quelque chose de bizarre, on continue sur la même pente, et à la fin, on se retrouve à pester jusqu'à trouver la lumière qui était placée juste au-dessus. Finalement, j'ai opté pour la conservation du facteur d'isolation (i.e. la puissance de 10 qui permet d'isoler la décimale dans la ligne) pour un gain vraiment étonnant de pas de programme. La partie entière du registre indexé par I permet de retenir temporairement la décimale isolée.

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.

Pas 147-178 : Comparaison

Quand une case fait une bonne candidate, il faut comparer son contenu (qui sera diminué de un puisqu'en raison de la présence du cavalier à sa portée, elle perd son potentiel d'autant) avec la valeur la plus faible précédente - ou placer sa valeur dans le registre de comparaison si elle est la première du cycle des huit cases à vérifier. Cette grosse manœuvre est assurée par la routine C (en vert clair) qui va à son tour appeler les routines 9 et 8 d'isolation et d'assemblage en utilisant de nouveau le registre I, raison des échanges R12<->R I. Il faut aussi vérifier si les valeurs des cases ne sont pas nulles (pas 153), si la case n'est pas la première (pas 162) et enfin si elle est intéressante car de moindre valeur que la précédente enregistrée (pas 164) : c'est alors la routine E qui se charge de conserver la valeur et les coordonnées de la case retenue (pas 167-173).
Tant que les huit états de drapeaux n'ont pas été modifiés, cela signifie que le cycle alentour du cavalier n'a pas été accompli et qu'il faut donc recommencer.

Le curseur revient enfin au pas 110, on vérifie si la case 64 est atteinte et si ce n'est pas le cas, on place les nouvelles coordonnées (registres 13 et 14) en tant que coordonnées officielles (registres 9 et 10), sans oublier de vider le registre 15 (valeur initiale du cycle égale à zéro) aux pas 113 à 118. Et c'est reparti pour un tour.

Épilogue

Sur la 15C Limited Edition, j'ai à peine le temps de voir clignoter "running" entre chaque mouvement - et encore, parce que j'ai modifié la fin pour gagner quelques pas, je crois que c'est la routine 11 qui provoque ce retard. Je n'ose pas chronométrer sur la 15C d'origine, mais je le ferai peut-être.

Comme le programme est assez ramassé finalement, je tenterai peut-être une version pour l'HP-41 afin de conserver une trace imprimée des parcours, voire de les comparer entre eux... par exemple, pour trouver ceux qui sont fermés, c'est-à-dire qui permettent au cavalier de revenir à sa position d'origine. Plus tard, peut-être, un poème... et j'écumerai les tavernes de Suisse à la recherche de ceux qui ne connaissent pas l'histoire d'Euler et de son cavalier.

(*) J'ai tout de même gagné encore quelques pas...

[Hobiecat]

Merci Marge pour les explications ! Je relirai ça à tête reposée.