Parcours du Cavalier

[invite2ec994dc]

Le problème du parcours du cavalier est bien connu...

Effectivement, il suffit de savoir lire...
Je ne connais pas ce problème quelqu'un peut-il me l'expliquer ?
-----

[invite2ec994dc]

Merci.

Le problème du cavalier (ou encore polygraphie ou algorithme du cavalier) est un problème mathématico-logique fondé sur les déplacements du cavalier du jeu d'échecs (une case partageant un côté commun puis une case en diagonale dans la même direction). Un cavalier posé sur une case quelconque d'un échiquier doit en visiter toutes les cases sans passer deux fois sur la même.

Je n'ai pas trouvé ce qu'est l'horizontale et la verticale,mais tout laisse à penser que ce sont celles qui passe par le centre de l'échiquier, dans le cas contraire les axes de symétrie pourrait formé un triangle -> pas possible de trouver un échiquier fini.

PS1 : Tout cela matérialise mon cheminement, en espérant être mieux compris...
PS2 : si cela est gênant, j’essaierais d'arrêter.

[invite2ec994dc]

Bonjour,

Pour le problème général : http://fr.wikipedia.org/wiki/Probl%C3%A8me_du_cavalier...

Bonjour,

Ceci est la preuve que le problème vient de moi.

PS : c'est sûr mais je m'en rends compte.

[invite51d17075]

Passer plus de 2 fois par une même case est-il autorisé ?

non, cette condition doit être respectée si j'ai bien saisi.
trop facile sinon.

[invite51d17075]

re Mediat,
j'avais une petite question concernant ta solution ( post #18 )
est elle liée à une démarche heuristique, ou bien à une analyse mathématique pure, et si oui, laquelle.?
merci si tu as le temps.
Cdt

[Médiat]

Bonsoir ansset,

J'ai eu l'idée de cette énigme alors que je cherchais quelle question poser ici (en Science Ludique) afin d'introduire une heuristique (et avoir à la fois le côté ludique et le côté scientifique).

[invite51d17075]

donc, je suppose que tu es parti du principe simple d'un multiple de 4 ( homogène sur l'échiquier )
et qu'au fur et à mesure.
pas de solution à 4 cases, ni à 8, .... jusqu'à une solution à 28 ....

[Médiat]

donc, je suppose que tu es parti du principe simple d'un multiple de 4 ( homogène sur l'échiquier )
et qu'au fur et à mesure.
pas de solution à 4 cases, ni à 8, .... jusqu'à une solution à 28 ....

J'exposerai une méthode plus opérationnelle ...

[invite51d17075]

bonne soirée en attendant.
Cdt.

[shokin]

Le cavalier peut-il passer d'un bord à l'autre ? (par exemple de la case (1;2) à la case (7;1))

[invite51d17075]

Le cavalier peut-il passer d'un bord à l'autre ? (par exemple de la case (1;2) à la case (7;1))

ben non, sinon c'est un cavalier des X-men ou des advengers !!

[Médiat]

Bonjour,

En dessinant l'échiquier sur un tore ...
Pourquoi pas mais ce serait un autre problème, on peu aussi envisager la question sur un cylindre.

[invite2ec994dc]

Sinon pour votre problème, la proposition de shokin est astucieuse.
En effet on pourrait redessiner l'échiquier de manière à ce que le déplacement du cavalier soit traduit en un déplacement du roi sur un échiquier modifier (qu'il reste à déterminer)
Remarque cela est possible car : si on a un cavalier au centre il peut se déplacer vers 8 cases différentes, tout comme le roi, et cela simplifierait énormément le problème...

[invite2ec994dc]

Si on regarde le groupe de symétrie, c'est un groupe engendré par une rotation de centre O (le centre de l'échiquier classique), si l'échiquier était 9*9 cela aurait été facilement traductible pour l'échiquier équivalent (avec déplacement d'un roi), peut-être que cela le reste toujours sur 8*8 mais j'arrive pas à visualiser....
9*9 facile car le centre de l'échiquier est le centre d'une case.
8*8 difficile car le centre de l'échiquier est le centre du côté d'une case.

[Médiat]

Je n'ai pas démontré que c'est la solution minimale, mais pour le plaisir, voici une solution à 20 cases, sur le tore (spécial pour X-men et avengers )

 Cliquez pour afficher

[Médiat]

Arrgghh sur le tore il y a une solution à 12 cases qui est bien minimale (et en plus c'est un tour fermé) :

 Cliquez pour afficher

[interferences]

Bonjour,

A plat, je n'ai qu'une solution a 24 cases.

Au revoir

[Médiat]

Bonjour,

 Cliquez pour afficher

Et il n'y a pas mieux, je posterai la démonstration durant le week-end.

Vous pouvez poster votre solution sous spoiler au cas où elle serait différente de la mienne ...

[invite51d17075]

perso, j'ai pas mieux, mais peut on prouver qu'il n'existe pas de solution inférieure.
il me semble que oui en passant par les multiples de 4

[Médiat]

cf. mon message précédent.

[invite2ec994dc]

Je n'ai pas démontré que c'est la solution minimale, mais pour le plaisir, voici une solution à 20 cases, sur le tore (spécial pour X-men et avengers )

 Cliquez pour afficher

Il faut que tu m'expliques comment tu passes de la case 01 à 02 avec un cheval, sauf si tu es déjà sur un tore.

[interferences]

Re,

En fait c'est pas un tore c'est une sphère.

PS : voilà mon brouillon...(solution à oreilles de lapin ^^)

 Cliquez pour afficher

brou.jpg

[NicoEnac]

Bonjour,

Sympathique petite énigme qui a eu le mérite de me faire trimer ainsi que mon ordi
Voici mes solutions que j'ai élargies en testant toutes les cases de départ possibles :

 Cliquez pour afficher

Vu les symétries de l'échiquier, les cases de départ à tester sont (1,1), (1,2) (celle de l'énoncé donc), (2,2), (1,3), (2,3), (3,3), (1,4), (2,4), (3,4), (4,4).
Les échiquiers minimaux sont ainsi les suivants (case de départ en rouge, autres cases actives en jaune) :
Résultats.jpg

Remarque : il est inscrit "NB = x" au dessus de chacun des échiquiers. Le x indique le nombre d'échiquiers de taille minimale existants. Lorsque x est supérieur à 1, je n'ai donc représenté qu'une seule des solutions.

[NicoEnac]

Voici mes réponses en supposant l'échiquier "sur un tore" :

 Cliquez pour afficher

Résultats_tore.jpg

[Médiat]

Bravo à tous les 2

Je posterai, comme prévu, la démonstration que 24 est bien le minimum dans le cas de la question de départ.

[Médiat]

Voici, la démonstration que 24 est bien la bonne solution, et une description d'une l'heuristique qui recherche les parcours sur un échiquier donné.

NinoEnac, si votre méthode est fondamentalement différente, n'hésitez pas à la poster.

 Cliquez pour afficher

A chaque case de l'échiquier on peut associer le nombre de cases que l'on peut atteindre à partir d'icelle, ce nombre de cases sera appelé ici le "Potentiel de la case".

Par exemple les 4 cases de coins ont un potentiel de 2 et les 4 cases centrales ont un potentiel de 8.

Première étape : cette partie, qui n'est pas très intéressante, consiste à minorer le nombre de cases de la solution minimale, en commençant en (1, 2) l'ensemble des 2 premiers mouvements est facile à lister :

(1,2)─┬─> (2, 4)─┬─> (1, 6) ≥ 24
      │          ├─> (3, 6) > 20 (plus de 2 cases avec potentiel = 1)
      │          ├─> (4, 5) > 20 (plus de 2 cases avec potentiel = 1)
      │          ├─> (4, 3) ≥ 24
      │          └─> (3, 2) ≥ 24
      ├─> (3, 3)─┬─> (1, 4) > 20 (plus de 2 cases avec potentiel = 1)
      │          ├─> (2, 5) > 20 (plus de 2 cases avec potentiel = 1)
      │          ├─> (4, 5) > 20 (plus de 2 cases avec potentiel = 1)
      │          ├─> (5, 4) > 20 (plus de 2 cases avec potentiel = 1)
      │          ├─> (5, 2) > 20 (plus de 2 cases avec potentiel = 1)
      │          ├─> (4, 1) > 20 (plus de 2 cases avec potentiel = 1)
      │          └─> (2, 5) > 20 (plus de 2 cases avec potentiel = 1)
      └─> (3, 1)─┬─> (2, 3) ≥ 24
                 ├─> (4, 3) ≥ 24
                 └─> (5, 2) ≥ 24

Comme les symétries imposent que le nombre de cases soit un multiple de 4, ont peut affirmer que la solution minimale contient au moins 24 cases, il reste à montrer qu'il en existe une, voir par exemple, la solution de NinoEnac (la mienne était identique).

Deuxième étape : mise en place d'une méthode heuristique, dont le déroulement est le suivant (très facile à implémenter sur ordinateur) :

1) Calculer les potentiel de chaque case.
2) Choisir le point de départ (ici, c'est (1, 2)) qui devient la case courante et mettre son potentiel à -1.
3) Diminuer de 1 le potentiel de chaque case, dont le potentiel est strictement positif, atteignable à partir de la position courante.
4) Si toutes les cases atteignables ont un potentiel négatif, l'algorithme s'arrête en échec.
5) Choisir comme nouvelle case courante, une des cases atteignables, dont le potentiel est minimal (parmi les cases atteignables de potentiel positif) et mettre son potentiel à -1.
6) Si la fin n'est pas atteinte, aller en 3).
7) Fin avec succès.

Il est important que l'étape 5 soit aléatoire, car comme cette méthode est heuristique, elle ne donne pas toujours la solution du premier coup (dans mes différents tests, soit la solution a été trouvée en 4 essais au plus, ou aucune solution n'a été trouvée en 1000 essais).

Cette méthode permet de trouver un parcours sur un échiquier donné, pas de fabriquer des échiquiers.

[invite51d17075]

je suis aussi intéressé par l'algo de NicoEnac, parce qu'il a fait tourner son ordi , semble t-il.

[NicoEnac]

NicoEnac, si votre méthode est fondamentalement différente, n'hésitez pas à la poster.

je suis aussi intéressé par l'algo de NicoEnac, parce qu'il a fait tourner son ordi , semble t-il.

Ma méthode est beaucoup moins intelligente que celle de Médiat.
Je suis parti sur tous les échiquiers possibles respectant les conditions de symétrie donc à partir de toutes les combinaisons des 10 cases dont je parle dans mon premier message :
(1,1) (1,2) (2,2) (1,3) (2,3) (3,3) (1,4) (2,4) (3,4) (4,4)
Puis j'ai testé les échiquiers par ordre de taille (4 cases, puis 8, puis 12, etc...) en testant toutes les cases de départ possibles.

Une fois l'échiquier et la case de départ définis, je teste tous les chemins possibles et je boucle tant que je ne les ai pas tous explorés ou que je n'ai pas trouvé de solutions.
Voulez-vous les détails de cet algo ? C'est un simple parcours d'arbre.

Il m'a ensuite suffit de chercher parmi les échiquiers possédant une solution et de répertorier la case de départ.

[Médiat]

Bonjour,

Deux précisions :

1) L'heuristique proposée est très facile à implémenter, et très efficace (pas de backtracking)
2) Cette heuristique est générale, et peut s'appliquer à de nombreux cas (parcours d'un graphe pondéré)


Autre point, pour le plaisir et les programmeurs : comment programmer la recherche des cases atteignables à partir d'une case donnée dans le cas du cheval (sans aucun test sur les bornes, afin que l'on puisse faire varier la taille de l'échiquier ainsi que sa topologie (plan, tore, cylindre ...), c'est à dire qu'à partir de (1, 1), (0, -1) est valide).

Si (i, j) est la position courante, comment trouver les 8 valeurs possibles de (x, y), donc sous la forme :
x = f(i)
y = g(j)

[invite51d17075]

Si (i, j) est la position courante, comment trouver les 8 valeurs possibles de (x, y), donc sous la forme :
x = f(i)
y = g(j)

j'obtiens simplement x=i+((-1)^n)(3-|j-k|) avec n=1,2
et réciproquement.