Nombre de déplacements minimaux et maximaux

Bonsoir
Je cherche des pistes de recherches/démonstrations autres que par la programmation informatique du problème suivant.

Dans un échiquier classique (8x8), quel est le nombre de déplacements minimaux et maximaux d'une tour pour paver tout l'échiquier sans repasser par le même point.
Une tour se déplaçant horizontalement ou verticalement.

J'ai essayé de poser le problème sous forme de programmation linéaire.
Si h et v sont le nombre de déplacements horizontaux et verticaux, on a :
v <= 64
h <=64
On cherche le minimum ou maximum de v+h

Je n'arrive pas à écrire la contrainte : "paver tout l'échiquier sans repasser par le même point."
Merci pour vos pistes.
JeremyJeff



Edité 2 fois. La dernière correction date de il y a sept mois et a été effectuée par AD.

Bonjour

Nombre minimum: 63 puisqu'il faut passer au moins une fois par chacune des 64 cases. Ceci est vraie avant même de parler de la moindre méthode.
Nombre maximum: 63 puisqu'il est interdit de repasser par le même point. Ceci est vraie avant même de parler de la moindre méthode.

Quel était l'esprit du problème de départ ?

Que veut dire "paver" dans ce contexte ? Cela veut-il dire "survoler les cases" ?
Dans ce cas, on peut arriver à bien moins de déplacements.

Bonsoir,

Paver , signifie passer une et une seule fois par chaque case de l'échiquier.

En cherchant des déplacements sur des longueurs de 2 ou de 1 (la tour se déplace verticalement ou horizontalement) , j'arrive à 56 déplacements, qui est le nombre de déplacements maximaux que je trouve.
L'idée étant la suivante: Pour un déplacement de tours assez grand (> 3), on peut trouver une déplacement intermédiaire.


Pour le nombre de déplacements minimaux, on essaie de se déplacer au maximum dans une direction (disons horizontalement) (7 ou 8 cases) et au minimum dans une autre (une case).
J'arrive alors à 16 déplacements.

Une autre approche serait de dire , comment décomposer le nombre 64 en sommes maximales ou minimales:

MIN : 64 = ( 8 + (1 + 7) + (1 + 7) + (1 + 7) + (1 + 7) + (1 + 7) + (1 + 7) + ( 6 + 1 + 1) ) , et on arrive à 16 termes, donc 16 déplacements

MAX : 64 = ( 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 2 + + ( 1 + 1 + 1 + 1 + 1 + 1 ) + 2 + ( 1 + 1 + 1+ 1 + 1) + 2 + ( 1 + 1 + 1 + 1 + 1 +1 ) + 3 + .... ) et on arrive à 56 termes donc 56 déplacements


Ceci est plus de la "bidouille" qu'autre chose.

Peut-on théoriser ceci et trouver une démonstration qu tienne la route.
Décomposition d'entiers, théorie des graphes ... Je suis preneur.

Merci

Ahhhhh. Donc c'est Bisam qui avait raison. Une case survolée est une case parcourue.

Par contre, pour le maximum, j'en démords pas. 63 déplacements pour atteindre les 64 cases. Pas 56. Sinon, tu en as oublié.
Pour le minimum, il y a plus rapide. 15 coups, partant de a1, en atteignant le centre par un mouvement spiral ou escargot.

Quant à la démonstration, j'aurais tendance à faire une exploration informatique. Considères-tu la démonstration du théorème des quatre couleurs par l'informatique comme valide ? Ici, c'est pareil.

bonsoir,

il me semble que le nombre maximum de déplacements est 63 et le nombre minimum 15

Citation
Jeremyjeff
Paver , signifie passer une et une seule fois par chaque case de l'échiquier.

et s'y poser ? Ou la survoler ?
Il y a deux interprétations, ce qui donne un dialogue de sourds.

Cordialement.

Survoler

La tour passe, sans forcément s'arrêter à toutes les cases, mais elle laisse une trace (imaginons la trace d'une craie).
A la fin du parcours, toutes les cases ont été recouvertes.
Du coup je trouve moins que 64 pour le maximum.

Théorème des quatre couleurs pour démonstration ? intéressant
Et quelles sont les quatre couleurs ?

Cordialement, jeremyJeff

Et si on rajoute comme hypothèse, de former un circuit fermé ?
On part d'un point et on parcourt tout l'échiquier (en le survolant) , sans passer par le même point, jusqu'à arriver au point de départ.

Tout cela pour dire qu' une contrainte supplémentaire peut changer complètement la méthode de résolution.
Sauf, que de méthodes, je n'en ai pas ....

Au départ, tu cherchais une chaîne hamiltonienne dans le graphe dans lequel les 64 nœuds sont les positions possibles de la tour et les arêtes sont les déplacements possibles. Maintenant que tu parles de "circuit fermé", tu cherches un cycle hamiltonien dans le même graphe.

"Du coup je trouve moins que 64 pour le maximum. "
Oui. 63.

Bonsoir,

Pour le nombre de déplacements maximum, en circuit fermé, j'ai fait une figure.
Voici ce que je trouve.

Voyez-vous d'autres circuits ?


Cordialement



Edité 2 fois. La dernière correction date de il y a six mois et a été effectuée par jeremyjeff.

Il suffit de s'arrêter à toutes les cases.

Exact, et si on rajoute une contrainte supplémentaire :
Nombre de virages maximal ou minimum

Du coup on cherche des graphes hamiltoniens de 64 noeuds, mais comment exprimer cette contrainte ?
La solution est-elle unique ?

A tâtons ?

Cordialement

Liste des forums - Statistiques du forum

Total
Discussions: 148 604, Messages: 1 497 686, Utilisateurs: 28 280.
Notre dernier utilisateur inscrit Section Paloise.

---

Ce forum
Discussions: 886, Messages: 7 497.