|
| 13 267 364 410 532 solutions !! par ins174 le
[Aller à la fin] |
| Problèmes | |
De quoi me direz-vous ? ;o)
D'un problème classique et ancien, la plus ancienne mention connue figure dans un manuscrit arabe du IXème siècle qui propose deux solutions.
Il s'agit ici des cicuits fermés ou "réentrants" du Cavalier.
C'est à dire de ceux que peut parcourir ce Cavalier en ne s'arrêtant qu'une seule fois sur chaque case et en revenant à son point de départ.
Dans la version plus simple, sans revenir à la case de départ, le problème a tellement de solutions que ... on n'est pas encore parvenu à les compter !
Tous les détails, dans un article de Alain Grigis et Benoît Rittaud, in La Recherche n°376 de Juin 2004, p 54.
Passionnant !
|
|
|
j'ai pas compris le pb... Il est où le cavalier au départ?
Il y a des autres pièces sur l'échiquier?
|
|
|
Hé bien a) n'importe où
b) non
Je vais chercher l'article dès cet après-midi, merci Yvap pour l'info!
Sait-on combien de solutions génèrent un carré magique? pseudo-magique?
|
|
|
Il n'y a qu'un cavalier ... qui doit parcourir toutes les cases de l'échiquier.
Au départ il peut être où tu veux. Evidemment en imposant une case particulière au départ, il y aura moins de solutions.
|
|
|
pour Puch ... les carrés magiques sont évoqués mais pas traités.
Le sujet principal étant : L'ensemble des "tours du cavalier" a-t-il une structure ?
Ce qui nous emmène dans un epace à 4 dimensions, dans les symétries de l'échiqier, etc ...
|
|
|
deux precisions (1) Il n'y a pas de tours magiques. Voir
http://perso.club-internet.fr/ydenef/index.htm ou en anglais http://mathworld.wolfram.com/news/2003-08-06/magictours/
(2)Je suppose que la nombre de solutions propose pour les cycles de chevalier est independent de la case du depart, car il est indivisible par 64.
|
|
|
Parcours du cavalier Quelques infos sur iechecs.com/probleme.htm
Vous pouvez vous entrainer à trouver un parcours du cavalier avec l'echiquier en ligne iechecs.com/iechecs.htm. Choisir le mode "Probleme" et selectionner remplissage du cavalier. Le bouton solution affiche une solution que vous pouvez rejouer pas à pas avec la barre de navigation présente sous l'échiquier...
|
|
|
Pas de tour magique ? Il me semble qu'Euler avait trouvé une solution du circuit de cavalier qui formait un carré magique...
|
|
|
ref Thanatos Il n'existe pas de carré magique d'ordre pair (comme un echiquier 8x8)
|
|
|
Oui mais on en trouve des "presque" magiques, où les sommes des colonnes et traverses sont constantes.
|
|
|
carre semi-magique sur iechecs.com/probleme.htm
je donne l'exemple du carre semi-magique ou chaque somme des lignes/rangées vaut 260.
|
|
|
Au passage Quelqu'un a-t-il eu l'ouvrage récent "Across the Board:
The Mathematics of Chessboard Problems" de John J. Watkins entre les mains?
Je serais intéressé pour le commander, mais j'aimerais avoir un avis auparavant...
|
|
|
Lien indispensable Pour ceux qui aiment les maths un site de reference indispensable : mathworld.wolfram.com, avec une partie consacrée aux échecs mathworld.wolfram.com/Chess.html
par contre c'est en anglais...
|
|
|
Bizarre On a eu des graphes eulériens (= on peut parcourir tout le graphe en ne passant qu'une seule fois par chaque sommet) en DS d'info cette année, et si je me rappelle bien il faut que tous les sommets du graphe soient à un croisement d'un nombre pair d'arêtes, et il me semble que l'échiquier avec le caval ne vérifiait pas ça (mais je vérifierai, parce que là ch'uuis plus sûr du tout!!!)
|
|
|
Graphes eulériens Ce ne sont pas les sommets qui sont visités une seule fois, mais les arètes.
|
|
|
mais la condition que tu donnes est bien une condition nécessaire (évident) et suffisante (nettement moins évident). Comme certains sommets du graphe ont un nombre impair d'arètes (par exemple b1), on ne peut pas faire un circuit de cavalier ou chque coup de cavalier est joué une et une seule fois.
|
|
|
Je viens d'écrire une bétise ... cherchez l'erreur !
|
|
|
Ben si 2 sommets seulement ont un nb impair d'arêtes ça peut le faire non ?
|
|
|
Non, non, on parle de circuits fermés.
|
|
|
La "bétise" de François: "chaque coup de cavalier" dans un sens ou dans l'autre, c'est-à-dire que Cb1-d2 et Cd2-b1 sont considérés comme un même coup.
|
|
|
C'est ça
|
|
|
ref FPC ?? un truc m'échappe -> "on ne peut pas faire un circuit de cavalier ou chaque coup de cavalier est joué une et une seule fois"
l'exemple du carré semi-magique donné sur iechecs.com/probleme.htm
est bien un circuit fermé ou chaque coup de cavalier est joué une et une seule fois...
|
|
|
"chaque coup" C'est-à-dire tous les coups légaux avec un cavalier (beaucoup plus long que le parcours de toutes les cases!): une suite de coups avec à la fois Ca1-c2, Ca1-b3, Cb1-a3, Cb1-c3, Cb1-d2, etc... une fois et une seule, et dans un ordre quelconque.
|
|
|
Ben oui, il faut suivre ! C'est Benji3000 qui a lancé le problème des graphes eulériens, très différent du problème initial.
|
|
|
Ma B.U. n'a pas encore reçu le numéro de juin de La Recherche... Snif... Faut patienter.
|
|
|
En tout cas je confirme, c'étaient bien les cases b1/a2 h7/g8 a7/b8 et h2/g1 qui posaient problème. Sinon je viens de relire les deux dernières questions et c'était bien les arêtes (sorry), même si ça ne change pas énormément le problème a priori (j'espère ne pas gaffer là ;o)):
4) G est un graphe (= couple (S,A) où S est un ensemble de sommets (cases de l'échiquier, ici) et A un ensemble d'arêtes du type (u,v) ou u et v sont dans S) [comme ça tout le monde pourra suivre! Y'a pas que des matheux sur ce forum :-p] connexe (ce qui est le cas de notre échiquier, chaque case du caval étant accessible depuis n'importe quelle autre). Etablir que si G est eulérien alors il vérifie la loi de Kirchhoff (ie chaque sommet voit un nombre pair d'arêtes).
---> Ca c pas trop dur avec un petit dessin, en effet!
5) Réciproquement G est un graphe connexe vérifiant la loi de Kirchhoff. Prouver que G est eulérien.
---> Là direct ça doit effectivement être dur mais on avait les questions précédentes pour nous aider :-p
Ceci dit, j'ai l'impression que ça répond en partie à la question: on ne peut pas trouver un chemin pour le cavalier qui passerait sur tout l'échiquier avec un seul passage par case, et ce quelle que soit la case de départ (car eulérien implique Kirchhoff, et là y'a po Kirchhoff...). Mais bon en passant deux fois par la même case, je sais pas... Je m'étais d'ailleurs amusé à essayer qqes parcours mais il y avait 4 à 6 cases où le joyeux caval repassait :-/ Bon j'vé voir le site de Fleysour pis vé dodoter!! @+
|
|
|
Bah zut alors... Je viens de faire un tour sur iechecs.com/problemes et après avoir parcouru les 64 cases du tit échiquier, n'en croyant pas mes yeux ni ma souris le caval avait fait les 64 cases, n'en déplaise à ce M. Euler :-/ Très joli... Mais je n'y comprend plus rien du coup là!!! Heeeeelp!!! Dodo is ze better way in those situations, isn't it? Yeaaah :-p Bonne nuit alors tout le mone!
|
|
|
Tu as parcouru les 64 sommets, mais pas les 168 (je crois) arêtes. Ton circuit est donc hamiltonien, mais pas eulerien.
Le problème de parcourir toutes les arêtes est très différent de celui de parcourir tous les sommets.
|
|
|
Un exemple avec une tour sur le carré a1-c3 :
Circuit hamiltonien : a1-a2-a3-b3-c3-c2-b2-b1-c1-a1.
Chacune des 9 cases est visitée une et une seule fois. C'est le problème initial.
Circuit eulérien : a1-a2-a3-a1-b1-b2-a2-c2-b2-b3-a3-c3-b3-b1-c1-c2-c3-c1-a1.
Chacune des 18 arêtes est parcourue une et une seule fois. C'est le problème posé (involontairement) par benji3000.
Il existe 13 267 364 410 532 circuits hamiltoniens pour le cavalier sur l'échiquier de 64 cases, mais 0 circuit eulerien.
|
|
|
Euh ... je peux dire un petit truc ... ? Je ne connais rien aux hamiltoniens, ni aux eulériens, mais dans ton 1er exemple et d'après ta définition FPC, la case a1 est visitée 2 fois puique le circuit est fermé ou "réentrant".
Ce qui correspond effectivement au problème initial. Mais est-ce bien un circuit hamiltonien dans ce cas ?
Ta définition ne correspondrait-elle pas plutôt aux circuits non fermés qui eux sont pour l'instant "innombrables" en ce qui concerne le cavalier ?
|
|
|
non, tais-toi ;-) En fait, tout est dans le mot "circuit". Un circuit est forcément fermé, et n'a vraiment de case de départ ou de case d'arrivée. J'ai répété la case a1, par souci de clarté (peut-être aurais-je dû m'abstenir) mais le ciruit a1-a2-a3-b3-c3-c2-b2-b1-c1-a1 est strictement le même que a2-a3-b3-c3-c2-b2-b1-c1-a1-a2. Et chaque case n'est visitée qu'une seule fois.
C'était le sens de la seconde remarque d'anselan : si on distingue sur chaque circuit une case de départ, alors pour chaque circuit hamiltonien, on peut en trouver 63 autres. Le nombre total de solutions est donc un multiple de 64. Or ce n'est pas le cas. On ne donne donc pas de case de départ au circuit.
Je ne sais donc pas ce qu'est un circuit non fermé ! Je crois qu'en français on emploie plutôt le mot "parcours" lorsque ce n'est pas une boucle.
|
|
|
OK FPC! J'ai compris :) Merci!
|
|
|
Ah ben v'là aut'chose !!!!???? Au temps pour moi, j'ai relu l'article et effectivement, c'est le terme "parcours" qui est utilisé et non "circuit" que j'ai indûment substitué. Merci FPC pour la correction.
Cela dit, y a encore un truc qui me chagrine ! ;o))
Si je fais le parcours a1-a2-a3-b3-b2-b1-c1-c2-c3, il n'est pas "fermé", la tour ne pouvant revenir en a1 sauf à se transformer en fou, ou peut-être si on considère un "hyper-échiquier" de dimension supérieure à 2.
Ce parcours (chacune des cases est visitée une seule fois) est-il toujours hamiltonien ?
Les liens donnés dans l'article :
Les données du calcul
En savoir plus
Amusez-vous bien ! ;o))
|
|
|
Remarque: Comme l'a fait remarquer Andrew, le nomber avancé n'ets pas mulitple de 64, ne sont donc considérés que le circuits partant de 'a1' (par exemple).
Mais un même circuit parcouru dans un sens ou l'autre a-t-il été compté une fois ou deux?
Juste pour chercher la petite bête, car le résultat exact peut varier du simple au double sans troubler mon sommeil outre mesure...
|
|
|
Bon, une fois lu l'article... On reste un peu sur sa faim. Enfin la méthode utilisée semble remarquable, l'échiquier étant considéré comme plan projectif d'un espace quadridimentionnel!
|
|
|
