Résoudre le problème du cavalier

Rédigé par Fred - - Aucun commentaire

Le problème du cavalier est le suivant : il faut déplacer un cavalier sur un échiquier de façon à ce qu’il passe par toutes les cases, une seule fois. On ajoute également souvent une contrainte : il doit pouvoir revenir à sa case de départ, un parcours dit « fermé » (et donc former un cycle hamiltonien).

De nombreux programmes permettent de résoudre ce problème, et c’est également un bon exercice pour ceux qui apprennent la programmation.

Évidemment, c’est un problème très intéressant mathématiquement, et algorithmiquement parlant. Mais ce qui m’intéresse ici, c’est plutôt de résoudre le problème de tête.

Un peu de « culture »

Si vous voulez en savoir un peu plus sur ce problème, comme d’habitude les pages wikipedia française et anglaise offret un bon point de départ.

On y apprend par exemple que :

  • il y a 19 591 828 170 979 904 solutions (suite A165134 sur l’oeis), et seulement 26 534 728 821 064 parcours fermés, qui peuvent se terminer sur la case de départ ;
  • les premières références du problème et de sa solution ont été trouvées au neuvième siècle ;
  • Euler a été parmi les premiers à étudier le problème ;
  • Rudrata, un poète indien, ainsi que des ouvrages de l’Oulipo (et notamment Georges Pérec1) utilisent la contrainte du déplacement du cavalier pour écrire des œuvres ;
  • un automate, le Turc mécanique, résoud le problème en 1770 (c’est en fait un canular, mais Benjamin Franklin ou Napoléon ont joué contre lui) ;

En cherchant un peu, on peut également trouver des façons de résoudre le problème en construisant des carrés semi-magiques (wolfram), ou alors en faisant de « jolis » dessins. Des variantes existent en changeant la taille de l’échiquier (voire en utilisant un échiquier en 3 dimensions), ou la pièce à utiliser (reine, tour… en ajoutant d’autres contraintes). Si vous voulez en savoir plus, je vous conseille ce site : http://www.mayhematics.com/t/t.htm.

Résoudre le problème de tête

Sur ce dernier site, en particulier dans son introduction au problème du cavalier, il y a une partie sur les façons de résoudre ce problème en utilisant des « diamants » et des « carrés », et la règle de Warnsdorf, une heuristique pour résoudre ce problème : aller sur la case qui propose le moins de déplacements possibles.

Et en lisant à droite à gauche, on trouve des références à Georges Koltanowski, joueur d’échecs Belge, qui s’amusait à faire des « tours » avec ce problème du cavalier : il demandait à son audience de remplir chaque case de l’échiquier avec des noms de rues, des dates de naissances, des villes, des noms de personnes… puis après avoir regardé l’échiquier 3 à 4 minutes, il lui tournait le dos et demandait à son audience de donner une case de départ. À partir de là, il récitait de mémoire ce qu’il y avait dans la case, puis récitait le contenu de chaque autre case, en se déplaçant de case en case à la manière d’un cavalier. Il pouvait également réciter les entrées dans l’ordre des colonnes, des lignes, ou des diagonales, voire faire ce tour avec 2 échiquiers.

De ce que j’ai pu trouver, il n’avait pas d’astuces particulières pour se souvenir du contenu des cases, mais il avait mémorisé un parcours fermé et pouvait donc commencer à partir de n’importe quelle case.

En utilisant des coordonnées chiffres/chiffres plutôt que chiffres/lettres (12 au lieu de a2, 25 au lieu de b5…) on peut « facilement » utiliser le système PAO combiné à une méthode de Loci retenir cela plus facilement.

Enfin, sur ce site, on trouve une méthode pour trouver un parcours qui part et finit sur n’importe quelle case (pourvu qu’elles soient de couleurs différentes). Comme je n’ai pas trouvé d’équivalent français, je propose une traduction pour les non-anglophones ici : résoudre le problème du cavalier les yeux fermés. Et pour s’entraîner, c’est par (attention, il reste des bugs ;]).

Footnotes:

1

Voir par exemple http://classes.bnf.fr/echecs/pedago/antho/19.htm. Sur un tout autre sujet, cette citation (du même site) qui « montre » que le jeu de go, c’est mieux que les échecs


Écrire un commentaire

Quelle est la troisième lettre du mot kgpwvm ?