Le problème du parcours du cavalier est bien connu, mais on peut modifier l'échiquier, par exemple en enlevant des cases, d'où la question :
Quel est l'échiquier minimal, symétrique par rapport à l'horizontale, la verticale, et les diagonales (de l'échiquier standard 8x8) qui peut être entièrement parcouru par le cavalier ?
Comme la réponse peut dépendre du point de départ choisi : on fixe (arbitrairement) le point de départ en (1, 2) (lignes et colonnes sont numérotées de 1 à 8).
Je suis Charlie.
J'affirme péremptoirement que toute affirmation péremptoire est fausse
Bonjour,Envoyé par Médiat
échiquier symétrique par rapport à l'horizontale, la verticale et les diagonales ???
Je ne comprends pas ou tu veux dire un échiquier carré ?
C'est bon merci j'ai compris, c'est le fait que tu ais mis "de l'échiquier standard 8x8" entre parenthèse qui m'a perturbé.
bjr Mediat,
je dois mal comprendre l'énoncé.
un cavalier peut potentiellement atteindre toutes les cases.
quelque chose m'échappe.
et je ne connais pas le soit disant connu "pb du parcours du cavalier" ( pourtant je joue aux échecs ).
J'ai trouvé c'est l'échiquier à une case.
oublie ma question.
je comprend mieux.
parcours du cavalier ( c-a-d sans repasser par la même case) sur un "sous échiquier" de taille n*n
J'ai tout faux, en effet je n'ai pas tenue compte de ta remarque (que j'ai mis en gras), la réponse n'est l'échiquier à une case.
Tentative x.0 :
Cliquez pour afficher
Qu'en penses-tu ?
Désolé, Médiat.
Je n'ai plus les prétentions que j'ai avancé dans ma réponse.
Cordialement.
Bonjour,
Pour le problème général : http://fr.wikipedia.org/wiki/Probl%C3%A8me_du_cavalier. Dans l'article de wikipedia il est surtout question des tours fermés, ici tous les tours sont acceptables.
Les conditions de symétries que j'ai données, associées au point de départ, interdisent une solution du type "sous-échiquier strict" n*n.
Il s'agit d'un échiquier 8*8 dans lequel on enlève des cases, par exemple en enlevant les 4 cases de coins (qui est une solution, mais pas la solution minimale (le moins de cases valides)).
Dernière modification par Médiat ; 14/01/2015 à 08h25.
Je suis Charlie.
J'affirme péremptoirement que toute affirmation péremptoire est fausse
merci pour cette précision.
joli casse tête.
je n'arrive qu'à éliminer les 4 cases de coin pour l'instant.
je laisse reposer un peu pour trouver une méthodologie plus maligne.
J'ai trouvé un tour de cavalier à 20 cases. Qui dit mieux ?
Au fait, il n'est pas obligatoire qu'un roi puisse aller d'une case à l'autre, ou bien ?
Bon, dans ce que j'ai trouvé, il n'y a pas le point (1;2) (la case A2).
Dernière modification par shokin ; 14/01/2015 à 12h20.
Pardon, humilité, humour, hasard, tolérance, partage, curiosité et diversité => liberté et sérénité.
Je propose ci-dessous un cadre pour afficher les solutions (sous spoiler éventuellement), les X représentent les cases autorisées) :
Je suis Charlie.
J'affirme péremptoirement que toute affirmation péremptoire est fausse
Pas comprisAu fait, il n'est pas obligatoire qu'un roi puisse aller d'une case à l'autre, ou bien ?
Comme c'est le point départ, c'est gênant
Je suis Charlie.
J'affirme péremptoirement que toute affirmation péremptoire est fausse
je ne saisi pas bien ta réponse.J'ai trouvé un tour de cavalier à 20 cases. Qui dit mieux ?
Au fait, il n'est pas obligatoire qu'un roi puisse aller d'une case à l'autre, ou bien ?
Bon, dans ce que j'ai trouvé, il n'y a pas le point (1;2) (la case A2).
que vient faire le roi ? c'est un gag ?
ensuite on doit bien partir de (1,2) non ?
Disons que l'ensemble que j'ai trouvé n'est pas une île, mais plusieurs îles. Le roi (aux échecs ; il se déplace d'une case à chacune des huit cases contiguës) ne peut pas traverser toutes les cases sans passer par des cases non comprises dans l'ensemble des cases que j'ai trouvé (parcourues par le cavalier). Autrement dit, les cases de l'ensemble ne sont pas toutes collées entre elles.Pas compris
J'avais commencé à chercher une solution pour avoir le moins de cases possibles, sans cette contrainte d'une case imposée (donc des 7 autres obtenues par des symétries).Comme c'est le point départ, c'est gênant
Bon, avec la case (1;2), j'ai trouvé une possibilité à 28 cases (de nouveau avec ces îlots séparés).
Dernière modification par shokin ; 14/01/2015 à 12h46.
Pardon, humilité, humour, hasard, tolérance, partage, curiosité et diversité => liberté et sérénité.
Ok,
Pas de problème avec les îlots.
En partant de (1, 2), 28 n'est pas le minimum
En partant de n'importe où j'ai une solution à 12 cases.
Cliquez pour afficher
Si on relache la condition que les symétries sont celles de l'échiquier 8x8, il y a une solution (évidente) à 8 cases.
Dernière modification par Médiat ; 14/01/2015 à 13h00.
Je suis Charlie.
J'affirme péremptoirement que toute affirmation péremptoire est fausse
Mais c'est réductible à un carré 6*6, il me semble ?En partant de n'importe où j'ai une solution à 12 cases.
Cliquez pour afficher
[Ou alors j'ai mal interprété le code tex, ayant toujours ce problème d'encadré rouge.]
Dernière modification par shokin ; 14/01/2015 à 13h19.
Pardon, humilité, humour, hasard, tolérance, partage, curiosité et diversité => liberté et sérénité.
Oui, c'est réductible à un carré 6x6, mais c'est la case de départ qui impose d'être dans un carré 8x8, donc si on relache cette contrainte, on peut réduire le carré dans lequel la solution s'inscrit (on pourrait trouver des variantes en imposant qu'au moins une case des bords fasse partie de la solution)
Je suis Charlie.
J'affirme péremptoirement que toute affirmation péremptoire est fausse
très joli.
que veux tu dire par "relâcher la condition de symétrie" ?
Cdt
Ah ! okay ! la solution initiale que j'avais (à 20 cases) ne partait pas de la case (1;2) et n'était pas réductible à un carré plus petit que 8*8. L'irréductibilité à un carré 8*8 me semblait être une des contraintes que tu avais posées.
La solution que tu as est-elle réductible à un carré plus petit que 8*8 ?En partant de (1, 2), 28 n'est pas le minimum
Pardon, humilité, humour, hasard, tolérance, partage, curiosité et diversité => liberté et sérénité.
La condition initiale est :
autrement dit une figure telle que l'échiquier 8x8 qui la contient possède ces symétries.Quel est l'échiquier minimal, symétrique par rapport à l'horizontale, la verticale, et les diagonales (de l'échiquier standard 8x8)
que l'on peut remplacer par
Autrement dit une figure qui possède ces symétries en elle-même,Quel est l'échiquier minimal, symétrique par rapport à l'horizontale, la verticale, et ses diagonales
D'ailleurs dans ce dernier cas une solution à 1 case fonctionne très bien, il faudrait donc, dans ce cas, imposer au moins 2 cases.
Dernière modification par Médiat ; 14/01/2015 à 13h50.
Je suis Charlie.
J'affirme péremptoirement que toute affirmation péremptoire est fausse
Impossible en partant de (1, 2)La solution que tu as est-elle réductible à un carré plus petit que 8*8 ?
Je suis Charlie.
J'affirme péremptoirement que toute affirmation péremptoire est fausse
c'est indirectement le point qui me génait.
merci.
Bon, je chercherai ce soir. Là, je dois y aller. Dans l'entre-temps, peut-être que d'autres auront trouvé.
Pardon, humilité, humour, hasard, tolérance, partage, curiosité et diversité => liberté et sérénité.
Bon courage
A tout hasard, je n'ai pas vu ce problème sur le Net, pourtant il doit bien exister (c'est une question assez naturelle), si quelqu'un a un lien ...
Je suis Charlie.
J'affirme péremptoirement que toute affirmation péremptoire est fausse
Passer plus de 2 fois par une même case est-il autorisé ?
Ce que l'on cherche est un sous-ensemble de l'échiquier symétrique par rapport aux diagonales (il en suffit de 2 paralléles et distincts) alors l'echéquier serait stable par translation
Théoréme utilisé la composé de 2 symétries paralléles est une translation.
Un échiquier fini, non vide, stable par translation, ça me parait juste impossible.
Encore une erreur de ma part un carré n'a que 2 diagonales, donc stable par symétrie centrale d'axe le centre de l'échiquier.
L'horizontale, et la verticale ceci indique une indique une direction et non un axe, sauf si pour les connaisseur d'échecs ces axes sont identifiés (horizontale et verticale)
et alors cela voudrais dire que ce défi ne s'adresse qu'a certain.
Car sans cela le problème est mal posé.
