Le Problème du Cavalier d'Euler

Accueil Le problème Carré Magique Les Solutions Intégration WEB

 

Algorithme et technologie

Les différents programmes disponibles sur ce site proposent plusieurs solutions au problème classique du cavalier d'Euler. Ce problème est abordé sous deux aspects.

  • L' algorithme

    Comment concevoir l'algorithme pour que la recherche soit la plus rapide possible ? Comment prendre en compte dans l'algorithme les contraintes nécessaires à l'élaboration d'un carré magique et quels sont tous les carrés magiques possibles ?

     

  • Les technologies informatiques

Comment intégrer simplement le programme de recherche dans un environnement Web pour le rendre directement utilisable à travers une page HTML ?

En 2004, il fallait plus de 50 jours pour trouver toutes les solutions de carrés magiques. En 2011, les 140 solutions sont trouvées en moins de 4 jours. Le temps de recherche a été divisé par 15 en 7 ans. En 2017, il suffit de 1,3 jour. Cette réduction est due à la fois à des améliorations dans l'algorithme de recherche et à l'utilisation de processeurs plus performants (pentium 4 2,4 Ghz en 2004, i3 2330 en 2011, i5 4310M en 2016, i72600 en 2017).

L'algorithme de recherche est basé sur 64 objets coopérants, représentant les 64 cases de l'échiquier. La présentation suivante Présentation Powerpoint décrit les principales fonctions de recherche . L'algorithme est implémenté sous forme d'un contrôle ActiveX (Kmagic.ocx) intégré dans cette présentation. Il faut utiliser l'outil d'enregistrement des contrôles (regsvr32.exe) pour y accéder. Les paramètres de supervision de l'algorithme sont présentés dans un autre contrôle activeX, mschrt20.ocx qu'il faut également enregistrer.

Les résultats, après parallèlisation de l'algorithme sur plusieurs threads indépendants, sont synthétisés dans le tableau suivant.

Search solutions

:

  • Start : indique le numéro de la case de départ pour la recherche. Les 10 départs correspondent aux cases numérotées 0,1,2,3,9,10,11,18,19,27.

Start Squares

  • rang : l'ordre dans lequel les 10 recherches (à partir des 10 départs) sont lancés. Ces recherches sont lancées en séquence, les unes après les autres. Une nouvelle recherche débute quand la recherche précédente est terminée. Pour chaque nouvelle recherche, on supprime de la liste des fins de parcours possible les cases, et toutes leurs symétries sur l'échiquier, qui ont été utilisées comme case de départ d'une recherche précédente. Cette méthode permet de réduire le temps de recherche en évitant de trouver 2 fois les solutions (1 chemin direct et un chemin retour)
  • Sol. Tot. :le nombre total de solutions trouvées. Certaines solutions trouvées ont des relations de symétrie, comme c'est le cas pour les 2 solutions de l'exemple suivant. La case de départ est la case 3.

solution 1solution n3

Le chemin inverse de la première solution (chaque valeur x est remplacée par 65 - x) donne la solution suivante.

Solution 2

qui est une symétrie de la seconde solution.

  • Sol. uniq. : nombre de solutions indépendantes, une fois que toutes les symétries ont été supprimées
  • Temps (sec) : temps en secondes de la recherche complète à partir de la case de départ
  • Temps (jours) : temps en jour (secondes/86400)
  • Temps loop (ns) : temps / Firstep en nanosecconds
  • FirstStep :nombre de bonds en avant du cavalier pour parcourir l'ensemble de l'arbre de recherche

Auteur :  Yann DENEF  mailto:ydenef@free.fr

    compteur