Nombre de déplacements minimaux et maximaux

jeremyjeff

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

PetitLutinMalicieux

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 ?

bisam

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.

jeremyjeff

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

PetitLutinMalicieux

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.

depasse

bonsoir,

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

gerard0

Jeremyjeff a écrit:

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.

jeremyjeff

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

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

PetitLutinMalicieux

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.

jeremyjeff

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

PetitLutinMalicieux

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

jeremyjeff

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