Exemple

Accueil Remonter Carrés Magiques Synthèse résultats

 

Internet Explorer permet d'activer, via un langage de script, les propriétés du contrôle présent sur cette page. On peut alors indirectement piloter le contrôle ActiveX, en proposant une IHM basée sur des contrôles HTML. Le code JavaScript, associé à ces contrôles, modifie les paramètres de recherche en modifiant les propriétés du contrôle.

Le contrôle activeX est un objet connu du JavaScript au même titre que les contrôles HTML. Son nom est défini par l'attribut "ID" de la balise "codebase". 

Les options sont classées en 3 catégories (toutes les options disponibles ne sont pas programmables à travers cette page). 

1 Cible de la recherche

Un carré semi-magique est magique et un carré avec diagonales semi-magiques possède des diagonales magiques. Il existe donc des relations gérées automatiquement entre ces quatre options.

    Carré Magique                    Diagonales Magiques

    Carré Semi-magique          Diagonales Semi-magiques

2 Code optimisé 

Lorsque le code est optimisé, les classes utilisées par l'algorithme de recherche ne contiennent pas de test sur les options du contrôle. L'algorithme est donc plus rapide. C'est la force du développement objet et du polymorphisme. Les tests sont intégrés dans l'arbre d'héritage
De plus, dans ce mode, il n'y a pas d'enregistrement de statistiques. Cet enregistrement est coûteux en terme de temps de calcul car les traces sont stockées dans des entiers de 64 bits, gérés sous forme de structure. Chaque incrémentation génère une dizaine d'instructions assembleur.  Le bouton STAT du contrôle présente une synthèse des traces enregistrées au niveau de la méthode IsFree. Les raisons pour lesquelles une case est déclarée libre ou occupée sont comptabilisées en fonction de l'Index de recherche (nombre de bonds actuels du cavalier) . 

    Code optimisé  

3 Tri initial des cases "destination"

Chaque case maintient un tableau de 2 à 8 éléments qui mémorise les cases à distance d'un saut de cavalier. Les performances de l'algorithme de recherche dépendent de la façon dont les éléments de ce tableau sont ordonnés. Quand le cavalier arrive sur une case, il essaye la première case du tableau. Lorsque toutes les solutions de chemins sont essayées à partir de cette case, le cavalier revient sur la case et essaye la deuxième du tableau, et ainsi de suite. Au début de l'algorithme, trois règles de tri sont possibles. 

    Distance minimale par rapport au bord de l'échiquier

     Distance minimale par rapport à la case A1 (coin en bas à gauche)

    Tri aléatoire

Le premier tri donne de loin les meilleurs résultats. Lorsque le tri sur les cases destinations est aléatoire, l'obtention d'une solution peut être très longue.

Une fois le contrôle ActiveX  chargé, il suffit de cliquer sur une case et de lancer la recherche en appuyant sur START.

 

La distance minimale par rapport au bord de l'échiquier donne des temps de recherche de chemin simple optimum, de l'ordre de la centaine de micro-secondes.

La "Combo box" sous le bouton SAV, indique les temps de passage pour parcourir la totalité d'un sous arbre à partir d' un nombre de sauts initiaux donné. Par exemple lorsque la ligne I:20 -Case: 17 -T:2 sec signifie qu'au 20ème bond du cavalier il était sur la case 17 et à mis 2 sec pour parcourir toutes les possibilités de chemin à partir de cette case. Plus l'objectif est ambitieux (par exemple carré semi magique avec diagonales magiques) plus les contraintes sont importantes sur l'algorithme et plus le temps de recherche est court.