Un problème très ancien

On pourrait être tenté de ne voir dans ce jeu qu'une simple patience, à peine moins futile que le solitaire (où vous devez déplacer des billes sur un tablier en forme de croix grecque ou de cercle pour, à la fin, n'en avoir plus qu'une seule et de préférence située au milieu) avec qui il partage beaucoup de points communs. C'est pourtant un problème bien plus ancien. Alors que le solitaire semble n'avoir été inventé qu'au XVIIe siècle (selon la légende, par un aristocrate emprisonné à la Bastille), la plus ancienne description connue du problème du cavalier remonte au milieu du IXe siècle dans un manuscrit arabe. Deux joueurs d'échec y exposaient chacun leur solution, l'une était un parcours fermé (la cavalier revient à la case de départ).

euleri Depuis, de nombreux mathématiciens s'y sont intéressés de près. C'est le cas par exemple du mathématicien suisse Leonhard Euler (1707-1783) qui publie un des premiers traités sur la question en 1766. C'est pourquoi ce problème est parfois appelé "cavalier d'Euler". A cette époque, l’académie des sciences de Berlin (où Euler était directeur du département de mathématiques) avait jugé le problème suffisamment important pour proposer un prix conséquent pour le meilleur mémoire sur le sujet.

Il existe un très grand nombre d'ouvrages et de sites qui parlent de ce problème tant sur un plan historique que sur un plan technique. Si vous lisez l'anglais, les deux meilleurs sites sont sans doute ceux rédigés par George Jelliss : soit sa page introductive, soit son site exhaustif. Une mine d'informations et d'analyses, fruit d'une recherche quasiment monomaniaque sur le sujet ! Vous y trouverez aussi tout un ensemble de variantes : des échiquiers de toutes tailles, carrés ou non, avec des règles de déplacements non conventionnels pour le cavalier (qui devient alors un chameau, un zèbre, une girafe, un gnu ou un écureuil).

Une question sérieuse

circuit imprimé Le problème du cavalier est bien plus qu'un simple amusement. Il est relié à un champ extrêmement important et fécond des mathématiques appelé "théorie de graphes", un domaine qui a des retombées très concrètes sur notre vie de tous les jours. Les graphes modélisent de nombreuses situations où interviennent des objets en interaction : connexions routières, ferroviaires ou aériennes, plan d'une ville et de ses rues en sens unique, liens entre les composants d'un circuit électronique. L'ensemble des outils mathématiques mis au point dans ce domaine permettent de démontrer facilement les propriétés d'un graphe et d'en déduire des méthodes de résolution : quel est le plus court chemin pour se rendre d'une ville à une autre ? Comment minimiser la longueur totale des connexions d'un circuit ? Peut-on mettre une rue en sens unique sans rendre impossible la circulation en ville ?

Des milliards de solutions

cavalier Les analyses mathématiques de ce problème abondent. Il existe même quelques principes pour résoudre ce problème. Un des plus célèbres est la règle de Warnsdorff, du nom du mathématicien allemand, H.C. Warnsdorff. Cette règle heuristique extraordinairement efficace date de 1823 et conseille de toujours choisir la case qui laisse le moins possibilité de suite, la case la plus "enclavée" en quelque sorte... Mais il ne s'agit là que d'une technique parmi d'autres et elle ne conduit qu'à une toute petite portion des très nombreuses solutions.

J'ai fait une petite recherche sur les bases de données scientifiques concernant le problème du cavalier. Les mathématiciens sont arrivés à définir certaines propriétés générales comme le théorème de Schwenk qui permet de savoir si un parcours fermé est possible quelles que soient les dimensions de l'échiquier (même s'il est rectangle). Ils se sont vites rendus compte du très grand nombre de solution possible, y compris dans le cas retreint des parcours fermés. Mais combien y en a-t-il exactement ? Jusqu'à récemment, on ne savait pas. En 1995, deux chercheurs allemands, Martin Löbbing et Ingo Wegener, ont publié une analyse du problème. Il pensait qu'il existait 33 439 123 484 294 parcours possibles (cf. leur article original). Ce résultat a été obtenu en utilisant vingt puissantes stations de calcul Sun pendant quatre mois ! Malheureusement, ils se sont rendus compte quelque mois plus tard que leur démonstration était fausse. Une petite erreur s'était glissée dans un raisonnement astucieux par ailleurs. Il fallait tout reprendre à zéro.

mckay En 1997, un chercheur australien, Brendan McKay (photo), utilisa une méthode complètement différente et conclut à l'existence de 13 267 364 410 532 circuits fermés (cf. son article). Plus de treize mille milliards de solutions ! Un chiffre colossal. Pour fixer les idées, imaginez un ordinateur très puissant qui chercherait systématiquement toutes les solutions possibles et qui en trouverait un million par minute (ce qui n'est pas rien!). Il lui faudrait 25 ans pour toutes les trouver !

ernesto mordecki Bon ça, c'est pour les circuits fermés (qui reviennent à la case de départ). Mais la plupart des solutions sont des circuits ouverts. Il n'y en surement pas un nombre infini puisque l'échiquier n'a que 64 cases. Poutant, on ne sait pas encore combien il y en a exactement. Assez récemment, Ernesto Mordecki (photo), un mathématicien uruguayen ayant fait sa thèse à Moscou, a prouvé en 2001 que le nombre de solutions au problème du cavalier dans sa forme général était inférieur à 1,3.10^35 parcours (cf. son article). Ca ne veut pas dire qu'il y en a autant, mais c'est déjà un énorme progrès vers le nombre de solution. La suite au prochain épisode… (Ajout du 05 décembre 2006 : déja du nouveau sur la question !)

Pourtant ce n'est pas si facile

Donc il y a au moins des milliers de milliards de solutions (et sans doute beaucoup plus). Mais c'est toujours un véritable défi quand on essaye d'en trouver ne serait-ce qu'une seule. Beaucoup de sites webs proposent de jouer au problème du cavalier sur des applications javascript. Mais elles sont souvent malcommodes et ne permettent pas de revenir en arrière pour corriger un coup. C'est pourquoi, j'ai passé un peu de temps à développer cette petite application (en plus d'être un excellent exercice en Flash). Et même en ayant la possibilité de revenir en arrière, il faut souvent beaucoup tâtonner pour trouver un parcours possible. Et ce parcours n'est valable que pour une case de départ donnée. Il peut être complètement différent si on part d'une autre case.

chessbase Pour la petite histoire, signalons le cas mystifiant d'un enfant de neuf ans qui participait en 2003 à l'émission télévisée allemande "Wetten dass?" (Vous voulez parier ?) qui présente des performances hors du commun. Il était capable de résoudre de tête le problème du cavalier en partant de n'importe quelle case (voir la vidéo ou ce compte rendu sur chessbase). Très impressionnant n'est-ce pas ? Surtout si vous vous être frotté au problème en essayant de le résoudre vous même. En réalité, ce n'est pas complètement insurmontable. Il suffisait au jeune garçon d'apprendre un seul parcours, un circuit fermé dans lequel le cavalier revient à la case de départ. Dans ce cas, quelle que soit la case demandée, il pouvait facilement annoncer la suite du circuit.

Et Perec dans tout ça ?

Et bien, ce problème fortement mathématique a souvent attiré les poètes et les artistes. Rudrata, un poète du Cachemire de la fin du IXe siècle, en donne une solution entièrement rédigée en vers. Plus tard, le problème devient une contrainte littéraire souvent utilisée en France et en Angleterre au XIXe, ce que George Jelliss appelle les cryptotours. Chaque case de l'échiquier correspond à un mot. En reconstituant le parcours, vous retrouvez le poème.

timbre perec Un problème extrêmement simple dans sa formulation, mais riche et complexe dans sa résolution. Voila de quoi exciter l'imagination de Perec et des membres de l'Oulipo, grands amateurs de contraintes littéraires. Dans son foisonnant roman "La vie mode d'emploi" (prix Médicis en 1978), Georges Perec décrit 100 ans de la vie d'un immeuble parisien. Il a découpé son immeuble en un quadrillage de dix fois dix pièces. Il consacre un chapitre à chacune d'elles. Mais ça serait un peu laborieux de passer de l'une à l'autre en suivant un parcours linéaire. Il aurait aussi pu choisir de les présenter au hasard. Or, le hasard est justement quelque chose que les poètes oulipiens détestent. Non, il y a bien plus élégant et stimulant. Ordonner les chapitres comme un problème du cavalier sur un échiquier de dix par dix ! Et c'est exactement cette règle qui structure son roman.


Voilà donc un petit jeu qui traverse douze siècles d'histoire des mathématiques et de littérature ! Et vous, en avez-vous trouvé une solution ?