Profondeur historique : Le tour du cavalier est une séquence mathématique dans laquelle un cavalier visite exactement une fois chaque case d'un échiquier. Il s'agit à la fois d'un défi stratégique et d'un problème classique de mathématiques récréatives.
Origines :
Ce problème est loin d'être une découverte moderne. Les premières solutions connues remontent au IXe siècle, fournies par des maîtres de Bagdad comme Al-Adli et As-Suli. Par ailleurs, dans la littérature indienne du IXe siècle, le poète cachemirien Rudrata a démontré cette esthétique mathématique dans son œuvre Kavyalankara, où il a composé un poème qui suit la séquence de la tournée d'un chevalier.
Littérature occidentale :
Au XIIIe siècle, le roi Alphonse X de Castille a présenté des manœuvres complexes basées sur le mouvement du chevalier dans son célèbre Libro de los Juegos (Livre des jeux). Cependant, les fondements mathématiques modernes du problème ont été posés en 1759 par Leonhard Euler, dont l'analyse est aujourd'hui reconnue comme l'une des pierres angulaires de la théorie des graphes.
Caractéristiques :
Visite fermée (ré-entrée) : Si le chevalier termine sa course sur une case située à exactement un coup de chevalier de la case de départ, il peut immédiatement recommencer le tour.
Visite libre :
Si le cavalier visite toutes les cases mais termine sur une case à partir de laquelle il ne peut pas atteindre le point de départ en un seul mouvement.
Posé par Max Bezzel en 1848 et attirant l'attention de génies tels que Carl Friedrich Gauss, ce problème a été transformé en “manifeste de programmation” dans les années 1970 par l'un des pères de l'informatique moderne, Edsger W. Dijkstra.
Dans son ouvrage de référence, Notes sur la programmation structurée (1972), Dijkstra a utilisé le problème des 8 reines pour démontrer comment un algorithme peut être systématiquement construit grâce à un processus qu'il a appelé “raffinement par étapes”.”
Le pouvoir du retour en arrière :
Selon Dijkstra, cette approche représente la première étape importante dans l'affinement du processus “essai-erreur” en une séquence logique sans faille qu'un coopérateur peut suivre.
Légende et origine :
Selon l'histoire, lorsque l'inventeur du jeu d'échecs, Sissa bin Dahir, a présenté le jeu au roi de l'Inde, celui-ci lui a demandé quelle récompense il souhaitait. Sissa fit une demande apparemment modeste : “Je veux un grain de blé pour la première case : ”Je veux un grain de blé pour la première case de l'échiquier, deux pour la deuxième, quatre pour la troisième, et pour chaque case suivante, le double de la précédente. Le roi a d'abord rejeté cette demande, pensant qu'il ne s'agissait que d'une “poignée de blé” ; cependant, lorsque le calcul a commencé, il est devenu évident que ni le trésor ni les stocks de blé du monde entier ne suffiraient à répondre à cette demande.
Historique : Ibn Khallikan (1256)
La première trace écrite connue de cette célèbre histoire a été consignée en 1256 par le célèbre biographe et historien Ibn Khallikan. Ibn Khallikan a intégré cet événement dans son ouvrage, non seulement comme un conte, mais aussi comme une preuve que les mathématiques repoussent les limites de l'imagination.
Réalité mathématique :
Cette demande faite pour les 64 cases de l'échiquier est l'exemple le plus pur de la progression géométrique (croissance exponentielle). Le montant de chaque case est calculé à l'aide de la formule suivante 2n-1 . L'équation fournissant la quantité totale de blé est la suivante :
63
∑
i=0
2i = 264 - 1
Le chiffre massif résultant de ce calcul est le suivant :
18,446,744,073,709,551,615
Pourquoi est-ce si important ?
Leçon stratégique : Ce problème est une ancienne leçon de sagesse qui enseigne aux dirigeants et aux stratèges comment de petits changements (“doublement”) peuvent se transformer en forces incontrôlables au fil du temps.
