Répondre à la discussion
Page 2 sur 3 PremièrePremière 2 DernièreDernière
Affichage des résultats 31 à 60 sur 75

Parcours du Cavalier



  1. #31
    contrexemple

    Re : Parcours du Cavalier


    ------

    Citation Envoyé par Médiat Voir le message
    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 ?

    -----

  2. Publicité
  3. #32
    contrexemple

    Re : Parcours du Cavalier

    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.

  4. #33
    contrexemple

    Re : Parcours du Cavalier

    Citation Envoyé par Médiat Voir le message
    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.

  5. #34
    ansset
    Animateur Mathématiques

    Re : Parcours du Cavalier

    Citation Envoyé par contrexemple Voir le message
    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.
    y'a quelque chose qui cloche là dedans, j'y retourne immédiatement !

  6. #35
    ansset
    Animateur Mathématiques

    Re : Parcours du Cavalier

    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
    y'a quelque chose qui cloche là dedans, j'y retourne immédiatement !

  7. #36
    Médiat

    Re : Parcours du Cavalier

    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).
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  8. Publicité
  9. #37
    ansset
    Animateur Mathématiques

    Re : Parcours du Cavalier

    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 ....
    y'a quelque chose qui cloche là dedans, j'y retourne immédiatement !

  10. #38
    Médiat

    Re : Parcours du Cavalier

    Citation Envoyé par ansset Voir le message
    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 ...
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  11. #39
    ansset
    Animateur Mathématiques

    Re : Parcours du Cavalier

    bonne soirée en attendant.
    Cdt.
    y'a quelque chose qui cloche là dedans, j'y retourne immédiatement !

  12. #40
    shokin

    Re : Parcours du Cavalier

    Le cavalier peut-il passer d'un bord à l'autre ? (par exemple de la case (1;2) à la case (7;1))
    Pardon, humilité, humour, hasard, tolérance, partage, curiosité et diversité => liberté et sérénité.

  13. #41
    ansset
    Animateur Mathématiques

    Re : Parcours du Cavalier

    Citation Envoyé par shokin Voir le message
    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 !!
    y'a quelque chose qui cloche là dedans, j'y retourne immédiatement !

  14. #42
    Médiat

    Re : Parcours du Cavalier

    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.
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  15. Publicité
  16. #43
    contrexemple

    Re : Parcours du Cavalier

    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...

  17. #44
    contrexemple

    Re : Parcours du Cavalier

    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.

  18. #45
    Médiat

    Re : Parcours du Cavalier

    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
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  19. #46
    Médiat

    Re : Parcours du Cavalier

    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
    Dernière modification par Médiat ; 16/01/2015 à 11h16.
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  20. #47
    interferences

    Re : Parcours du Cavalier

    Bonjour,

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

    Au revoir
    Ce n'est pas le doute qui rend fou, c'est la certitude.

  21. #48
    Médiat

    Re : Parcours du Cavalier

    Bonjour,

     Cliquez pour afficher


    Vous pouvez poster votre solution sous spoiler au cas où elle serait différente de la mienne ...
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  22. Publicité
  23. #49
    ansset
    Animateur Mathématiques

    Re : Parcours du Cavalier

    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
    y'a quelque chose qui cloche là dedans, j'y retourne immédiatement !

  24. #50
    Médiat

    Re : Parcours du Cavalier

    cf. mon message précédent.
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  25. #51
    contrexemple

    Re : Parcours du Cavalier

    Citation Envoyé par Médiat Voir le message
    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.

  26. #52
    interferences

    Re : Parcours du Cavalier

    Re,

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

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

     Cliquez pour afficher
    Dernière modification par interferences ; 16/01/2015 à 15h17.
    Ce n'est pas le doute qui rend fou, c'est la certitude.

  27. #53
    NicoEnac

    Re : Parcours du Cavalier

    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
    "Quand les gens sont de mon avis, il me semble que je dois avoir tort."O.Wilde

  28. #54
    NicoEnac

    Re : Parcours du Cavalier

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

     Cliquez pour afficher
    "Quand les gens sont de mon avis, il me semble que je dois avoir tort."O.Wilde

  29. Publicité
  30. #55
    Médiat

    Re : Parcours du Cavalier

    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.
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  31. #56
    Médiat

    Re : Parcours du Cavalier

    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
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  32. #57
    ansset
    Animateur Mathématiques

    Re : Parcours du Cavalier

    je suis aussi intéressé par l'algo de NicoEnac, parce qu'il a fait tourner son ordi , semble t-il.
    y'a quelque chose qui cloche là dedans, j'y retourne immédiatement !

  33. #58
    NicoEnac

    Re : Parcours du Cavalier

    Citation Envoyé par Médiat Voir le message
    NicoEnac, si votre méthode est fondamentalement différente, n'hésitez pas à la poster.
    Citation Envoyé par ansset Voir le message
    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.
    "Quand les gens sont de mon avis, il me semble que je dois avoir tort."O.Wilde

  34. #59
    Médiat

    Re : Parcours du Cavalier

    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)
    Dernière modification par Médiat ; 17/01/2015 à 09h43.
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  35. #60
    ansset
    Animateur Mathématiques

    Re : Parcours du Cavalier

    Citation Envoyé par Médiat Voir le message
    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.
    y'a quelque chose qui cloche là dedans, j'y retourne immédiatement !

Page 2 sur 3 PremièrePremière 2 DernièreDernière

Discussions similaires

  1. Réponses: 2
    Dernier message: 11/01/2015, 21h33
  2. Périple du cavalier.
    Par nicozeyo dans le forum Mathématiques du supérieur
    Réponses: 2
    Dernier message: 27/10/2009, 19h23
  3. position cavalier sur DD ibm WDA-L160
    Par soude dans le forum Matériel - Hardware
    Réponses: 2
    Dernier message: 12/08/2009, 12h51
  4. construction d'un pont cavalier
    Par beetle bug 64 dans le forum Physique
    Réponses: 13
    Dernier message: 19/01/2009, 20h44
  5. Cavalier sur disque dur ?
    Par Myr dans le forum Matériel - Hardware
    Réponses: 1
    Dernier message: 04/02/2004, 22h37