Forum de mathématiques - Bibm@th.net

Bonjour

1. Avant de se "ruer sur Python", il y a le temps de la réflexion. En l’occurrence je n'ai commencé à "programmer" qu'après avoir délimité les difficultés et pour mieux "valider sans erreur" mes essais papier-crayon...

2. Il n'y a pas de solution sans au moins 15 mouvements.

3. Votre défi :
Tenant compte de la symétrie par rapport à l'axe 0-4, il y a 36 solutions en commençant à déplacer le train 1 et 40 autres en commençant à déplacer le train 2. Ces 76 solutions réparties sur 944 177 chemins fermés (sur un total de 7 229 184 chemins possibles)

3 La surprise serait de voir ces nombres confirmés par des formules calculées, bien que la théorie en ait surement été faite...
Pourquoi un résultat obtenu avec l'aide d'un ordinateur devrait-il être dédaigné ?

Cordialement

Re-

@amatheur : je n'ai peut-être pas été très clair, mais dans mon premier post, je parle d'échanger les positions. Donc je veux que le 1 soit à la place du 7 et le 7 à la place du 1.

@tous : je me doutais bien en posant cette énigme que les certains allaient se ruer sur Python.
Allez, il y a un défi associé pour les programmeurs. Trouvez toutes les solutions en 15 coups (qui est l'optimum, je crois).
Vous allez voir, vous allez être surpris!

Fred.

re,

Pour éviter toute confusion, mieux vaut garder les notations de l'énoncé :
Au début les trains de 1 à 7 sont sur les quais respectifs de 1 à 7, le quai 0 est le quai vide.

Voici les mouvements numérotés de 0 à 15 sortis par mon programme Python :
0 [0, 1, 2, 3, 4, 5, 6, 7] le quai vide est en 0
1 [2, 1, 0, 3, 4, 5, 6, 7] le quai vide est en 2  ; le train 2  a rejoint le quai 0
2 [2, 1, 4, 3, 0, 5, 6, 7] le quai vide est en 4  ; le train 4  a rejoint le quai 2
3 [2, 1, 4, 0, 3, 5, 6, 7] le quai vide est en 3  ; le train 3  a rejoint le quai 4
4 [2, 1, 4, 5, 3, 0, 6, 7] le quai vide est en 5  ; le train 5  a rejoint le quai 3
5 [2, 1, 4, 5, 0, 3, 6, 7] le quai vide est en 4  ; le train 3  a rejoint le quai 5
6 [2, 1, 4, 5, 6, 3, 0, 7] le quai vide est en 6  ; le train 6  a rejoint le quai 4
7 [0, 1, 4, 5, 6, 3, 2, 7] le quai vide est en 0  ; le train 2  a rejoint le quai 6
8 [1, 0, 4, 5, 6, 3, 2, 7] le quai vide est en 1  ; le train 1  a rejoint le quai 0
9 [1, 5, 4, 0, 6, 3, 2, 7] le quai vide est en 3  ; le train 5  a rejoint le quai 1
10 [1, 5, 0, 4, 6, 3, 2, 7] le quai vide est en 2  ; le train 4  a rejoint le quai 3
11 [1, 5, 6, 4, 0, 3, 2, 7] le quai vide est en 4  ; le train 6  a rejoint le quai 2
12 [1, 5, 6, 0, 4, 3, 2, 7] le quai vide est en 3  ; le train 4  a rejoint le quai 4
13 [1, 0, 6, 5, 4, 3, 2, 7] le quai vide est en 1  ; le train 5  a rejoint le quai 3
14 [1, 7, 6, 5, 4, 3, 2, 0] le quai vide est en 7  ; le train 7  a rejoint le quai 1
15 [0, 7, 6, 5, 4, 3, 2, 1] le quai vide est en 0  ; le train 1  a rejoint le quai 7

Pour rechercher une solution par programme, c'est plus facile en cherchant le parcours du "quai 0". cela revient à chercher un parcours des arêtes du graphe dans lequel les arêtes sont parcourues une fois, et 2 au maximum pour certaines...

Cordialement

Bonsoir,

Tout à fait d'accord avec les vérifications de nerosson : les solutions à 14 et 13 mouvements d'amatheur ne correspondent pas à la demande de l'énoncé.
Pour optimiser et valider j'ai utilisé un algorithme de graphe transcrit en Python.

Cordialement

Salut à tous,

@amatheur,

Tu vas croire que je t'ai dans le nez : pas du tout, mais en vérifiant ta solution à 13, je trouve :
A4, B3, C2, D1, E7, F vide, G5, H6.

Ci-dessous ma vérification (pas très lisible, je sais):

re
qu'il soit maudit ce chiffre 13; j'ai beau faire varier l'ouverture, je n'arrive pas à faire mieux!

j'ai pigé le truc!

bonjour.
solution en 14 mouvements:

désolé, je n arrive pas à utiliser la balise correctement. quelqu'un pourrait me corriger s'il vous plait.

[EdIt] by yoshi
Pas d'espaces dans les balises quelles qu'elles soient !