Discussion :

[Tudko]

Bonjour

Je me suis acheté des tours de Hanoi en bois
Après trois jours de tatillonnage sur plus de vingt pages de brouillon j'ai enfin réussi à retrouver par moi même un morceau de l'algorithme général de récursion déplaçant les huit disques de la tour 1 à la tour 3, sans aide sur internet aucune.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
T0 = [ 0, 1, 2, 3, 4, 5, 6, 7 ]
#Disques de diamêtres 0 à 7, empilés du plus petit sur le plus grand
T1 = [ [],[],[],[],  [],[],[],[] ]
T2 = [ [],[],[],[],  [],[],[],[] ]
i=0
j=0
k=0
def move(i, j, k):
  if i == j :
    if k % 2 == 0:
      T0[i] = []
      T2[i] = i
    else:
      T0[i] = []
      T1[i] = i
  else:
    move(0, j-1, k-1)
    move(j, j, k)
    move(0, j-1, k-1)
 
move(0, 7, 2)
#Déplace et empile un par un les cylindres 0 à 7 sur la tour 2
# (jamais un plus grand sur un plus petit)
# en t'aidant de la tour 1
print(T0) ; print(T1) ; print(T2)

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
[[], [], [], [], [], [], [], []]
[0, [], 2, [], 4, [], 6, []]
[[], 1, [], 3, [], 5, [], 7]

Le résultat imprimé par mon Notebook Jupiter semble indiquer que le travail est encore fait à moitié.
Manuellement je maîtrise maintenant parfaitement les 255 déplacements de disques, ce qui n'est pas encore le cas de mon ordinateur.
Je me suis alors replongé le crayon à la main pour chercher la route récursive manquante mais là honnêtement je sollicite votre aide

Merci !

[danielhagnoul]

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
def tour_hanoi(n, i, j):
    """ Déplace n disques du piquet i au piquet j
        Nombre de disques n
        Trois piquets
        6 = 1 + 2 + 3 (somme des numéros des piquets)
        Nombre de déplacements = 2**n - 1
 
        https://www.codingame.com/playgrounds/17176/recueil-dexercices-pour-apprendre-python-au-lycee/tours-de-hanoi
        https://fr.wikipedia.org/wiki/Tours_de_Hano%C3%AF
        https://deptinfo-ensip.univ-poitiers.fr/ENS/doku/doku.php/tp:python:prog01
    """
    if n > 0:
        tour_hanoi(n - 1, i, 6 - i - j)
        print("Déplacer disque du piquet {} au piquet {}".format(i, j))
        tour_hanoi(n - 1, 6 - i - j, j)
 
 
print('Nb déplacement = {}'.format(2**3 - 1)) # Nb déplacement = 7
 
tour_hanoi(3, 1, 3)
 
"""
Déplacer disque du piquet 1 au piquet 3
Déplacer disque du piquet 1 au piquet 2
Déplacer disque du piquet 3 au piquet 2
Déplacer disque du piquet 1 au piquet 3
Déplacer disque du piquet 2 au piquet 1
Déplacer disque du piquet 2 au piquet 3
Déplacer disque du piquet 1 au piquet 3
"""

[wiztricks]

Salut,

Je me suis alors replongé le crayon à la main pour chercher la route récursive manquante mais là honnêtement je sollicite votre aide

C'est peut être à ce moment là qu'il faut chercher un peu sur Internet pour voir comment l'ont codés d'autres (bien) avant vous...

- W

[Sve@r]

Bonjour

Je me suis acheté des tours de Hanoi en bois

C'est sympa. J'ai déjà vu ça aussi. Me semble que le truc est à 8 disques.

Après trois jours de tatillonnage sur plus de vingt pages de brouillon j'ai enfin réussi à retrouver par moi même un morceau de l'algorithme général de récursion déplaçant les huit disques de la tour 1 à la tour 3, sans aide sur internet aucune.

Bel effort. 20 pages ça me parait tout de même exagéré.

Je me suis alors replongé le crayon à la main pour chercher la route récursive manquante mais là honnêtement je sollicite votre aide

Pas compliqué: pour déplacer n (n > 1 impérativement ) disques de la tour 1 à la tour 3, il faut

• déplacer n-1 disques de la tour 1 à la tour 2
• déplacer le dernier disque de la tour 1 à la tour 3
• déplacer n-1 disques de la tour 2 à la tour 3

Un exemple se trouve dans mon tutoriel shell (cf signature). Et je viens de le porter en Python

Code python :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#!/usr/bin/env python3
# coding: utf-8
# Programme de tours de Hanoï
# Usage: prog nb_pions
 
# Fonction récursive qui déplace n pions d'une tour x vers une tour y
def deplace(jeu, dep, arr, nb=1):
	# S'il n'y a plus qu'un seul pion
	if nb == 1:
		# Ici on est en fin de récursivité – Il ne reste plus qu'un seul pion à déplacer
		jeu["tours"][dep-1]-=1		# La tour de départ perd un pion
		jeu["tours"][arr-1]+=1		# La tour d'arrivée gagne un pion
		jeu["cpt"]+=1			# Le compteur de mouvements augmente
 
		# On génère le mouvement et on quitte la fonction
		yield "Mvt: %d - %d => %d: Etat: %s" % (
			jeu["cpt"],
			dep,
			arr,
			", ".join(map(str, jeu["tours"])),
		)
		return
	# if
 
	# Ici, on est dans la partie intermédiaire du jeu – Il y a encore des pions qui gènent
	# Déplacement récursif des pions restants de la tour de départ vers une tour intermédiaire
	yield from deplace(
		jeu,
		dep,
		tuple(map(int, set(range(1, 4)) - set((dep, arr))))[0],
		nb - 1,
	)
 
	# Déplacement du dernier pion de la tour de départ vers la tour d'arrivée
	yield next(deplace(jeu, dep, arr))
 
	# Déplacement récursif des pions restants de la tour intermédiaire vers la tour d'arrivée
	yield from deplace(
		jeu,
		tuple(map(int, set(range(1, 4)) - set((dep, arr))))[0],
		arr,
		nb - 1,
	)
# deplace
 
# Programme principal
if __name__ == "__main__":
	import sys
	import os
 
	# Vérification arguments
	if len(sys.argv) <= 1 or int(sys.argv[1]) < 1:
		print("Usage: %s nb_pions positifs" % os.path.basename(__file__))
		exit(1)
	# if
 
	# Initialisation jeu
	jeu={
		"tours" : [int(sys.argv[1]), 0, 0],
		"cpt" : 0,
	}
 
	# Affichage position de départ
	print("Départ: %s" % ", ".join(map(str, jeu["tours"])))
 
	# Lancement mouvement de la tour 1 vers la tour 3
	print("\n".join(deplace(jeu, 1, 3, int(sys.argv[1]))))
 
	# Affichage position d'arrivée
	print("Arrivée: %s" % ", ".join(map(str, jeu["tours"])))
# if

[Tudko]

Merci beaucoup
C'est vrai que c'était intéressant de m'entraîner à chercher ma propre version

[Tudko]

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
T0 = [ 0, 1, 2, 3,  4, 5, 6, 7 ]
T1 = [ [],[],[],[], [],[],[],[] ]
T2 = [ [],[],[],[], [],[],[],[] ]
i=0
j=0
k=0
def move(i, j, k):
  if i == j :
    if k % 2 == 0:
      T0[i] = []
      T2[i] = i
    else:
      T0[i] = []
      T1[i] = i
  else:
    move(0, j-1, k)
    move(j, j, k)
    move(0, j-1, k) # et non pas k-1
 
move(0, 7, 2)
print(T0) ; print(T1) ; print(T2)

[[], [], [], [], [], [], [], []]
[[], [], [], [], [], [], [], []]
[0, 1, 2, 3, 4, 5, 6, 7]

BINGO


Mais j'avoue que je n'ai pas saisi mathématiquement pourquoi k [le compteur : déplacer de 1 ou de 2 tours ; déplacer de 3(impair)tours revenant à revenir à la tour 1 et ainsi de suite] au lieu de k-1. En effet, si vous vous êtes renseignés sur le jeu, partir de n=8 disques pour arriver à la tour 2 (k=+2) demande de d'abord faire k-1 =+1 aux n-1=7 premiers tours, afin de laisser au préalable place au disque 8 sur la tour 2 (ici la première tour est la tour 0). Et ainsi de suite. Enfin d'après moi

[Sve@r]

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
T0 = [ 0, 1, 2, 3,  4, 5, 6, 7 ]
T1 = [ [],[],[],[], [],[],[],[] ]
T2 = [ [],[],[],[], [],[],[],[] ]

Pourquoi la tour 0 contient des disques (des valeurs) et les autres tours contiennent des listes ???

[[], [], [], [], [], [], [], []]
[[], [], [], [], [], [], [], []]
[0, 1, 2, 3, 4, 5, 6, 7]

BINGO

Oui enfin on voit jiste l'état final. Ce qui est bien, c'est de voir chaque mouvement.

Pas compliqué: pour déplacer n (n > 1 impérativement ) disques de la tour 1 à la tour 3, il faut

• déplacer n-1 disques de la tour 1 à la tour 2
• déplacer le dernier disque de la tour 1 à la tour 3
• déplacer n-1 disques de la tour 2 à la tour 3

En effet, si vous vous êtes renseignés sur le jeu, partir de n=8 disques pour arriver à la tour 2 (k=+2) demande de d'abord faire k-1 =+1 aux n-1=7 premiers tours, afin de laisser au préalable place au disque 8 sur la tour 2 (ici la première tour est la tour 0). Et ainsi de suite. Enfin d'après moi

Oui, c'est aussi ce que j'avais écrit.

[Tudko]

Pourquoi la tour 0 contient des disques (des valeurs) et les autres tours contiennent des listes ???


Oui enfin on voit jiste l'état final. Ce qui est bien, c'est de voir chaque mouvement.


Oui, c'est aussi ce que j'avais écrit.

La tour 0 contient la valeur 1 pour disque 1, je pense que ça reste manipulable

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
 
T0 =[0, 1,  2,  3,  4,  5,  6,  7]
T1 =[[],[],[],[],  [],[],[],[] ]
T2 =[[],[],[],[],  [],[],[],[] ]
i=0
j=0
k=0
def move(i, j, k):
  if i == j :
    if k % 2 == 0:
      T0[i] = []
      T2[i] = i
    else:
      T0[i] = []
      T1[i] = i
  else:
    move(0, j-1, k)
    move(j, j, k)
    move(0, j-1, k)
    print(T0) ; print(T1) ; print(T2)
move(0, 7, 2)
 
[[], [], 2, 3, 4, 5, 6, 7]
[[], [], [], [], [], [], [], []]
[0, 1, [], [], [], [], [], []]
[[], [], [], 3, 4, 5, 6, 7]
[[], [], [], [], [], [], [], []]
[0, 1, 2, [], [], [], [], []]
[[], [], [], 3, 4, 5, 6, 7]
[[], [], [], [], [], [], [], []]
[0, 1, 2, [], [], [], [], []]
[[], [], [], [], 4, 5, 6, 7]
[[], [], [], [], [], [], [], []]
[0, 1, 2, 3, [], [], [], []]
[[], [], [], [], 4, 5, 6, 7]
[[], [], [], [], [], [], [], []]
[0, 1, 2, 3, [], [], [], []]
[[], [], [], [], 4, 5, 6, 7]
[[], [], [], [], [], [], [], []]
…

C'est un peu mieux toujours pas cohérent mathématiquement, franchement les machines..
Est-ce que Python n'est pas le meilleur langage pour faire ça? Il faudrait un langage proprement fonctionnel comme Scheme/Haskell??

[Tudko]

Bonjour

C'est sympa. J'ai déjà vu ça aussi. Me semble que le truc est à 8 disques.


Bel effort. 20 pages ça me parait tout de même exagéré.


Pas compliqué: pour déplacer n (n > 1 impérativement ) disques de la tour 1 à la tour 3, il faut

• déplacer n-1 disques de la tour 1 à la tour 2
• déplacer le dernier disque de la tour 1 à la tour 3
• déplacer n-1 disques de la tour 2 à la tour 3

Un exemple se trouve dans mon tutoriel shell (cf signature). Et je viens de le porter en Python

Code python :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#!/usr/bin/env python3
# coding: utf-8
# Programme de tours de Hanoï
# Usage: prog nb_pions
 
# Fonction récursive qui déplace n pions d'une tour x vers une tour y
def deplace(jeu, dep, arr, nb=1):
	# S'il n'y a plus qu'un seul pion
	if nb == 1:
		# Ici on est en fin de récursivité – Il ne reste plus qu'un seul pion à déplacer
		jeu["tours"][dep-1]-=1		# La tour de départ perd un pion
		jeu["tours"][arr-1]+=1		# La tour d'arrivée gagne un pion
		jeu["cpt"]+=1			# Le compteur de mouvements augmente
 
		# On génère le mouvement et on quitte la fonction
		yield "Mvt: %d - %d => %d: Etat: %s" % (
			jeu["cpt"],
			dep,
			arr,
			", ".join(map(str, jeu["tours"])),
		)
		return
	# if
 
	# Ici, on est dans la partie intermédiaire du jeu – Il y a encore des pions qui gènent
	# Déplacement récursif des pions restants de la tour de départ vers une tour intermédiaire
	yield from deplace(
		jeu,
		dep,
		tuple(map(int, set(range(1, 4)) - set((dep, arr))))[0],
		nb - 1,
	)
 
	# Déplacement du dernier pion de la tour de départ vers la tour d'arrivée
	yield next(deplace(jeu, dep, arr))
 
	# Déplacement récursif des pions restants de la tour intermédiaire vers la tour d'arrivée
	yield from deplace(
		jeu,
		tuple(map(int, set(range(1, 4)) - set((dep, arr))))[0],
		arr,
		nb - 1,
	)
# deplace
 
# Programme principal
if __name__ == "__main__":
	import sys
	import os
 
	# Vérification arguments
	if len(sys.argv) <= 1 or int(sys.argv[1]) < 1:
		print("Usage: %s nb_pions positifs" % os.path.basename(__file__))
		exit(1)
	# if
 
	# Initialisation jeu
	jeu={
		"tours" : [int(sys.argv[1]), 0, 0],
		"cpt" : 0,
	}
 
	# Affichage position de départ
	print("Départ: %s" % ", ".join(map(str, jeu["tours"])))
 
	# Lancement mouvement de la tour 1 vers la tour 3
	print("\n".join(deplace(jeu, 1, 3, int(sys.argv[1]))))
 
	# Affichage position d'arrivée
	print("Arrivée: %s" % ", ".join(map(str, jeu["tours"])))
# if

ValueError Traceback (most recent call last)
<ipython-input-8-d605c888f81a> in <module>()
50
51 # Vérification arguments
---> 52 if len(sys.argv) <= 1 or int(sys.argv[1]) < 1:
53 print("Usage: %s nb_pions positifs" % os.path.basename(__file__))
54 exit(1)

ValueError: invalid literal for int() with base 10: '-f'

[Sve@r]

La tour 0 contient la valeur 1 pour disque 1, je pense que ça reste manipulable

Je parlais pas de la tour 0 qui contient les disques (ça j'ai compris), je parlais des autres tours qui contiennent des listes vides ce que je ne comprends pas. Ma question concernait donc ces autres tours, et la partie de ma question qui parle de la tour 0 était juste là pour illustrer le fait que vu qu'elle contient des nombres (les largeurs des disques probablement), c'était pas normal d'avoir les autres tours contenant des listes.

Est-ce que Python n'est pas le meilleur langage pour faire ça? Il faudrait un langage proprement fonctionnel comme Scheme/Haskell??

Personne ne t'a obligé à utiliser Python. C'est toi qui est venu ici poser la question. Ce forum n'est pas le lieu pour débattre de quel langage est meilleur que lequel (ce qui d'ailleurs est un faux débat => "Aucun langage de programmation n'est parfait. Il n'existe même pas un langage meilleur que d'autre ; il n'y a que des langages en adéquation ou peu conseillés pour des buts particuliers. (Herbert Mayer)").

ValueError Traceback (most recent call last)
<ipython-input-8-d605c888f81a> in <module>()
50
51 # Vérification arguments
---> 52 if len(sys.argv) <= 1 or int(sys.argv[1]) < 1:
53 print("Usage: %s nb_pions positifs" % os.path.basename(__file__))
54 exit(1)

ValueError: invalid literal for int() with base 10: '-f'

Il semble que tu utilises ipython (et probablement basé sur Python2). Mon script est écrit en Python3.
Te faut remplacer les deux yield from deplace(...) (lignes 27 et 39) par for x in deplace(...): yield x (le yield from iterable n'existe pas en P2).

Et j'espère que ce "-f" que je vois c'est pas toi qui l'a invoqué comme option quand tu appelles ce programme.

[Tudko]

Salut je reviens vers vous

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
T= [[0, 1, 2, 3, 4, 5, 6, 7],[],[]]
i = 0
j=0
compteur=0
def move(i, j):
  global compteur
  if j == i:
    j=i
    if compteur %2 == 0:
        del T[compteur][j]
        compteur= compteur +2
        T[compteur].append(j)
 
    else:
        del T[compteur][j]
        compteur= compteur +1
        T[compteur].append(j)
 
  else:
    move(i, j-1)
    move(j, j)
    move(i, j-1)
    print(T); print()#sauter une ligne entre deux étapes affichées
    compteur=compteur%3
move(0, 7)
 
IndexError                                Traceback (most recent call last)
<ipython-input-29-4b0d0af17ac1> in <module>()
     23     print(T); print()#sauter une ligne entre deux étapes affichées
     24     compteur=compteur%3
---> 25 move(0, 7)
 
<ipython-input-29-4b0d0af17ac1> in move(i, j)
     18 
     19   else:
---> 20     move(i, j-1)
     21     move(j, j)
     22     move(i, j-1)
 
<ipython-input-29-4b0d0af17ac1> in move(i, j)
     18 
     19   else:
---> 20     move(i, j-1)
     21     move(j, j)
     22     move(i, j-1)
 
<ipython-input-29-4b0d0af17ac1> in move(i, j)
     18 
     19   else:
---> 20     move(i, j-1)
     21     move(j, j)
     22     move(i, j-1)
 
<ipython-input-29-4b0d0af17ac1> in move(i, j)
     18 
     19   else:
---> 20     move(i, j-1)
     21     move(j, j)
     22     move(i, j-1)
 
<ipython-input-29-4b0d0af17ac1> in move(i, j)
     18 
     19   else:
---> 20     move(i, j-1)
     21     move(j, j)
     22     move(i, j-1)
 
<ipython-input-29-4b0d0af17ac1> in move(i, j)
     18 
     19   else:
---> 20     move(i, j-1)
     21     move(j, j)
     22     move(i, j-1)
 
<ipython-input-29-4b0d0af17ac1> in move(i, j)
     19   else:
     20     move(i, j-1)
---> 21     move(j, j)
     22     move(i, j-1)
     23     print(T); print()#sauter une ligne entre deux étapes affichées
 
<ipython-input-29-4b0d0af17ac1> in move(i, j)
      8     j=i
      9     if compteur %2 == 0:
---> 10         del T[compteur][j]
     11         compteur= compteur +2
     12         T[compteur].append(j)
 
IndexError: list assignment index out of range (?)

J'ai essayé de faire afficher chaque étape du jeu pour avoir et le résultat attendu et le bon raisonnement, ce qui fut un échec précédemment et l'est toujours

[Tudko]

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
T0 =[0, 1,  2,  3,  4,  5,  6,  7]
T1 =[[],[],[],[],  [],[],[],[] ]
T2 =[[],[],[],[],  [],[],[],[] ]
i=0
j=0
k=0
def move(i, j, k):
  if i == j :
    if k % 2 == 0:
      T0[i] = []
      T2[i] = i
    else:
      T0[i] = []
      T1[i] = i
  else:
    move(0, j-1, k)
    move(j, j, k)
    move(0, j-1, k)
    print(T0) ; print(T1) ; print(T2)
move(0, 7, 2)
 
[[], [], 2, 3, 4, 5, 6, 7]
[[], [], [], [], [], [], [], []]
[0, 1, [], [], [], [], [], []
…

D'ailleurs pourquoi précédemment l'algo déplace DEUX disques par étape?

[Sve@r]

D'ailleurs pourquoi précédemment l'algo déplace DEUX disques par étape?

Je n'en sais absolument rien. Peut-être parce que ton algo n'a pas de commentaire et que j'y pige que dalle (déjà toi est-ce que tu t'en sors ???). Pourquoi par exemple tester si "i" est pair ???. Peut-être parce que les lignes 10 et 13 sont les mêmes bien que l'une soit dans le "if" et l'autre dans le "else" (si j'ai ceci alors faire cela, sinon faire cela !!! ). Ou alors peut-être parce que les lignes 16 et 18 sont là aussi les mêmes (sans compter la ligne 17 où je ne sais pas trop si "j" représente le nb de pions ou les tours de départ et d'arrivée mais où, dans tous les cas, ne peut pas être utilisé 2 fois ..)

Bref pour résumer, parce que ton code bien qu'il "ressemble" à un algo de Hanoi, ne reproduit absolument pas l'algo de base qui est (déjà dit)
Déplacer n disques de la tour 1 à la tour , c'est

• déplacer n-1 disques de la tour 1 à la tour 2
• déplacer le dernier disque de la tour 1 à la tour 3
• déplacer n-1 disques de la tour 2 à la tour 3

[tyrtamos]

Bonjour,

Problème ancien et toujours très intéressant. Comme le PO a l'air en panne, je donne un petit coup de pouce.

Je part de l'algorithme cité par Sve@r:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
Déplacer n disques de la tour 1 à la tour , c'est
    déplacer n-1 disques de la tour 1 à la tour 2
    déplacer le dernier disque de la tour 1 à la tour 3
    déplacer n-1 disques de la tour 2 à la tour 3

Une version mini en Python pourrait être:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def hanoi(nbdisques, orig=[], dest=[], inter=[]):
 
    if nbdisques>0:
 
        # 1er appel récursif
        hanoi(nbdisques-1, orig, inter, dest)
 
        # déplacement
        dest.append(orig.pop())
 
        # affichage
        print(orig, inter, dest)
 
        # 2ème appel récursif
        hanoi(nbdisques-1, inter, dest, orig)
 
n = 3
orig = [i for i in range(n, 0, -1)]
print(orig, [], [])
hanoi(n, orig)

Ce qui donne pour n=3:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
[3, 2, 1] [] []
[3, 2] [] [1]
[3] [1] [2]
[] [3] [2, 1]
[] [2, 1] [3]
[2] [3] [1]
[] [1] [3, 2]
[] [] [3, 2, 1]

On voit que ça marche, mais l'affichage a un problème: l'ordre des tours n'est pas toujours la même puisqu'il dépend de l'ordre des arguments de chaque appel. Si on veut bien comprendre, il faut afficher les tours dans le bon ordre: "origine", "intermédiaire" et "destination". On va donc changer la structure de données comme ça:
orig = [1, [i for i in range(nbdisques, 0, -1)]]
inter = [2, []]
dest = [3, []]
ce qui permettra de retrouver lors de l'affichage les 3 tours dans l'ordre: 1=>origine, 2=>intermédiaire et 3=> destination.

Voilà un code plus complet:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#############################################################################
def _hanoi(nbdisques, orig, dest, inter):
    global nbcoups
 
    if nbdisques>0:
 
        # 1er appel récursif
        _hanoi(nbdisques-1, orig, inter, dest)
 
        # procède au déplacement
        dest[1].append(orig[1].pop())
 
        # affichage du déplacement
        nbcoups += 1
        tours = {1:"origine", 2:"intermédiaire", 3:"destination"}
        print("coup", nbcoups, " - déplace disque de ", tours[orig[0]], " à ", tours[dest[0]])
        tours = sorted([orig] + [inter] + [dest], key=lambda v: v[0])
        print(tours[0][1], tours[1][1], tours[2][1])
        print()
 
        # 2ème appel récursif
        _hanoi(nbdisques-1, inter, dest, orig)
 
#============================================================================
def hanoi(nbdisques):
 
    # crée les tours avec les disques demandés sur la tour d'origine
    orig = [1, [i for i in range(nbdisques, 0, -1)]]
    dest = [3, []]
    inter = [2, []]
    nbcoups = 0
 
    # affiche la situation de départ pour les 3 tours
    print("Etat des 3 tours au départ, avec", nbdisques, "disques sur la tour origine:")
    print("origine:", orig[1], "intermédiaire:", inter[1], "destination:", dest[1])
    print()
 
    _hanoi(nbdisques, orig, dest, inter)
 
############################################################################# 
if __name__ == "__main__":
 
    # pour compter le nombre de déplacements nécessaires (var globale)
    nbcoups = 0
 
    n = 3 # nombre de disques à déplacer
    hanoi(n)

Ce qui donne cette fois pour 3 disques à déplacer de la tour "orig" à la tour "dest":

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
Etat des 3 tours au départ, avec 3 disques sur la tour origine:
origine: [3, 2, 1] intermédiaire: [] destination: []
 
coup 1  - déplace disque de  origine  à  destination
[3, 2] [] [1]
 
coup 2  - déplace disque de  origine  à  intermédiaire
[3] [2] [1]
 
coup 3  - déplace disque de  destination  à  intermédiaire
[3] [2, 1] []
 
coup 4  - déplace disque de  origine  à  destination
[] [2, 1] [3]
 
coup 5  - déplace disque de  intermédiaire  à  origine
[1] [2] [3]
 
coup 6  - déplace disque de  intermédiaire  à  destination
[1] [] [3, 2]
 
coup 7  - déplace disque de  origine  à  destination
[] [] [3, 2, 1]

Et là, on voit bien tous les mouvements effectués par l'algorithme. Ici, pour n=3 disques, on fait ça en 2**n-1=7 coups.

On peut, bien sûr, utiliser pour n'importe quelle valeur de n, à condition d'être raisonnable à cause des limites de la pile de récursion.

Par exemple, pour n=20 qui demande 2**20-1=1048575 déplacements:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
Etat des 3 tours au départ, avec 20 disques sur la tour origine:
origine: [20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1] intermédiaire: [] destination: []
 
coup 1  - déplace disque de  origine  à  intermédiaire
[20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2] [1] []
 
coup 2  - déplace disque de  origine  à  destination
[20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3] [1] [2]
 
coup 3  - déplace disque de  intermédiaire  à  destination
[20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3] [] [2, 1]
 
coup 4  - déplace disque de  origine  à  intermédiaire
[20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4] [3] [2, 1]
 
coup 5  - déplace disque de  destination  à  origine
[20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 1] [3] [2]
 
...
 
coup 1048571  - déplace disque de  destination  à  origine
[2, 1] [3] [20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4]
 
coup 1048572  - déplace disque de  intermédiaire  à  destination
[2, 1] [] [20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3]
 
coup 1048573  - déplace disque de  origine  à  intermédiaire
[2] [1] [20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3]
 
coup 1048574  - déplace disque de  origine  à  destination
[] [1] [20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2]
 
coup 1048575  - déplace disque de  intermédiaire  à  destination
[] [] [20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1]

[Sve@r]

Problème ancien et toujours très intéressant.

Une légende dit que Dieu a créé 3 aiguilles et 64 disques d'or et chargé ses prêtres de déplacer les 64 disques de l'aiguille 1 à l'aiguille 3. Et quand tout sera fini, ce sera la fin du monde.

Comme le PO a l'air en panne

Ben en fait je pense qu'il a décroché...

à condition d'être raisonnable à cause des limites de la pile de récursion.

Il existe aussi une solution itérative : commencer par établir le premier coup (tour nb impair => commencer par tour d'arrivée, tour nb pair commencer par la tour intermédiaire). Ensuite toujours choisir le disque qui n'a pas bougé au coup précédent (sinon ça veut dire que le même disque bouge 2 fois) et si 2 possibilités pour l'autre disque, alors toujours choisir la tour qui n'est pas celle d'où il est venu (sinon ça signifie qu'on annule son déplacement précédent)

Prenons cet algo avec 3 tours A, B et C sur 3 disques à amener de A vers C. Position de départ: 3 0 0

• Au premier coup, il y a possibilité de partir de A vers B ou C. Toutefois A a 3 disques (nb impair). Le premier disque va donc de A vers C. Ce qui donne 2 0 1
• Ensuite on peut soit déplacer C (mais il vient d'arriver donc interdit), soit déplacer A. Qui là ne peut aller que sur B => 1 1 1
• Ensuite on peut soit déplacer B (mais il vient d'arriver donc interdit), soit déplacer C qui pourrait aller sur A (mais il vient de A ce qui annulerait alors son coup précédent) donc il va sur B => 1 2 0
• Ensuite on peut soit déplacer B (mais il vient d'arriver donc interdit) soit déplacer A qui ne peut aller que sur C => 0 2 1
• Ensuite on peut soit déplacer C (mais il vient d'arriver donc interdit), soit déplacer B qui pourrait aller sur C (mais il vient de C) donc il va sur A => 1 1 1
• Ensuite on peut soit déplacer A (mais il vient d'arriver donc interdit) soit déplacer B qui ne peut aller que sur C => 1 0 2
• Ensuite on peut soit déplacer C (mais il vient d'arriver donc interdit), soit déplacer A qui pourrait aller sur B (mais il vient de B) donc il va sur C => 0 0 3

Ps: j'ai lancé mon code récursif avec 50 avant de commencer à taper ce post. Et j'ai fini de taper que mon truc est toujours en train de calculer ses mouvements (et je crois même que la machine virtuelle sur laquelle il tourne est freezée.. )

[wiztricks]

Salut,

Vieux problème, beaucoup de littérature et des résumés dans Wikipedia.
Pour ce que çà intéresse, l'article anglais fait le tour du sujet et des différentes solutions (car il y en a d'autres que la récursive et l'itérative).

- W

[Sve@r]

Pour ce que çà intéresse, l'article anglais fait le tour du sujet et des différentes solutions

Effectivement, j'en ai trouvé une encore plus simple que celle que j'ai exposée : si on code un mouvement de 1 vers 2 ou de 2 vers 1 par la somme des tours, on obtient 3. Il y a donc 3 valeurs de mouvements possibles (3 pour tour 1 et tour 2, 4 pour tour 1 et tour 3 et 5 pour tour 2 et tour 3).
Et là, on se rend compte que pour un nombre pair de pions, la suite des mouvements est 3, 4, 5, 3, 4, 5, etc (jusqu'à ce que tous les pions aient été déplacés). Et pour un nombre impair, alors la suite est 4, 3, 5, 4, 3, 5, etc. On n'a même pas à se poser de questions. On déroule simplement 3, 4, 5, 3, 4, 5, ... (ou 4, 3, 5, 4, 3, 5, ...) à l'infini. A chaque mouvement (ex 5 qui met en jeu la tour 2 et la tour 3), le sens du mouvement (2 vers 3 ou 3 vers 2) se définit facilement par la seule possibilité (le petit anneau sur le grand).

D'où le code (qui, adapté à l'informatique, utilise le codage 1, 2 et 3 pour les mouvements entre les tours 0, 1 et 2)

Code python :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#!/usr/bin/env python3
# coding: utf-8
# Programme de tours de Hanoï
# Usage: prog nb_pions
 
# Fonction itérative qui déplace nb pions de la tour 0 à la tour 2
def deplace(jeu, nb):
	# Décomposition du coup joué
	def decomp(coup):
		# Calcul des tours affectées
		(x, y)={
			1 : (0, 1),
			2 : (0, 2),
			3 : (1, 2),
		}[coup]
 
		# Dans le tuple renvoyé on met déjà le coup évalué (ça ne mange pas de pain)
		r=(coup,)
 
		# Si l'une des deux tours x/y est vide, elle reçoit alors le pion de l'autre
		if not jeu["tours"][y]: return r + (x, y)
		if not jeu["tours"][x]: return r + (y, x)
 
		# Le sens du coup dépendra du petit pion qui va sur le grand
		return r + ((x, y) if jeu["tours"][x][-1] < jeu["tours"][y][-1] else (y, x))
	# decomp()
 
	# Tant que la dernière tour n'a pas tous les pions
	while len(jeu["tours"][2]) < nb:
		# Décomposition du coup courant par rapport au chemin des coups
		move=decomp(jeu["path"][jeu["cpt"] % 3])
 
		# Positionnement des pions : tour d'arrivée récupère dernier pion tour de départ
		jeu["tours"][move[2]].append(
			jeu["tours"][move[1]].pop(),
		)
		jeu["cpt"]+=1						# Le compteur de mouvements augmente
 
		yield "Mvt %d: %d => %d: Etat: %s" % (
			jeu["cpt"],
			move[1] + 1,
			move[2] + 1,
			affich(jeu),
		)
	# while
# deplace()
 
# Affichage jeu
def affich(jeu, full=False):
	return "%s%s" % (
		", ".join(map(str, (len(t) for t in jeu["tours"]))),
		" => %s" % " ".join(str(list(reversed(x))) for x in jeu["tours"]) if full else "",
	)
# affich()
 
# Programme principal
if __name__ == "__main__":
	import sys
	import os
 
	# Vérification arguments
	if len(sys.argv) <= 1 or int(sys.argv[1]) < 1:
		print("Usage: %s nb_pions positifs" % os.path.basename(__file__))
		exit(1)
	# if
 
	# Initialisation jeu
	nb=int(sys.argv[1])
	jeu={
		"tours" : tuple([] if i else list(range(nb, 0, -1)) for i in range(3)),
		"cpt" : 0,
		"path" : ((2, 1) if nb % 2 else (1, 2)) + (3,),
	}
 
	# Affichage position de départ
	print("Départ: %s" % affich(jeu, True))
 
	# Lancement mouvement
	for x in deplace(jeu, nb): print(x)
 
	# Affichage position d'arrivée
	print("Arrivée: %s" % affich(jeu, True))
# if

Je l'ai lancé pour 64 (en référence à la légende de la fin du monde) et le petit truc s'est vaillamment lancé dans le mouvement des pions. Et là, pas de souci de récursivité limitée...

[tyrtamos]

Bonjour,

A noter que l'article de wikipedia cité par wiztricks existe aussi en français: https://fr.wikipedia.org/wiki/Tours_de_Hano%C3%AF

Un grand merci à Sve@r pour la solution itérative (la 2ème de l'article ci-dessus): j'aime beaucoup!

Voilà mon code pour cette solution itérative:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#############################################################################
def deplace(nomA, A, nomB, B):
    """déplace un disque d'une des 2 tours vers l'autre tour
       sur un disque plus grand ou sur une tour vide
    """
    if len(A)>0 and (len(B)==0 or A[-1]<B[-1]):
        print("Déplace {} => {}".format(nomA, nomB))
        B.append(A.pop())
    else:
        print("Déplace {} => {}".format(nomB, nomA))
        A.append(B.pop())
 
#############################################################################
def _hanoi(nbdisques, tour1, tour2, tour3):
    global nbcoups
 
    if nbdisques%2==0:
        # solution nbdisques pair
        while len(tour1)+len(tour2)!=0:
            #----------------------------------------------------------------
            # somme=3: déplacement 1=>2 ou 2=>1
            nbcoups += 1
            deplace("tour1", tour1, "tour2", tour2)
            print(nbcoups, tour1, tour2, tour3, '\n')
            #----------------------------------------------------------------
            # somme=4: déplacement 1=>3 ou 3=>1
            nbcoups += 1
            deplace("tour1", tour1, "tour3", tour3)
            print(nbcoups, tour1, tour2, tour3, '\n')
            #----------------------------------------------------------------
            # somme=5: déplacement 2=>3 ou 3=>2
            nbcoups += 1
            deplace("tour2", tour2, "tour3", tour3)
            print(nbcoups, tour1, tour2, tour3, '\n')
    else:
        # solution nbdisques impair
        while len(tour1)+len(tour2)!=1:
            #----------------------------------------------------------------
            # somme=4: déplacement 1=>3 ou 3=>1
            nbcoups += 1
            deplace("tour1", tour1, "tour3", tour3)
            print(nbcoups, tour1, tour2, tour3, '\n')
            #----------------------------------------------------------------
            # somme=3: déplacement 1=>2 ou 2=>1
            nbcoups += 1
            deplace("tour1", tour1, "tour2", tour2)
            print(nbcoups, tour1, tour2, tour3, '\n')
            #----------------------------------------------------------------
            # somme=5: déplacement 2=>3 ou 3=>2
            nbcoups += 1
            deplace("tour2", tour2, "tour3", tour3)
            print(nbcoups, tour1, tour2, tour3, '\n')
        #--------------------------------------------------------------------
        # dernier déplacement pour somme impaire
        nbcoups += 1
        print("Déplace tour1 => tour3")
        tour3.append(tour1.pop())
        print(nbcoups, tour1, tour2, tour3, '\n')
 
#============================================================================
def hanoi(nbdisques):
 
    # crée les tours avec les disques demandés sur la tour d'origine
    tour1 = [i for i in range(nbdisques, 0, -1)]
    tour3 = []
    tour2 = []
 
    # affiche la situation de départ pour les 3 tours
    print("Etat des 3 tours au départ, avec", nbdisques, "disques sur la tour origine:")
    print("origine:", tour1, "intermédiaire:", tour2, "destination:", tour3)
    print()
 
    _hanoi(nbdisques, tour1, tour3, tour2)
 
############################################################################# 
if __name__ == "__main__":
    nbcoups = 0 # variable globale
    n = 11 # nombre de disques à déplacer
    hanoi(n)

Ce qui donne par exemple pour n=3:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
Etat des 3 tours au départ, avec 3 disques sur la tour 1:
tour 1: [3, 2, 1] tour 2: [] tour 3: []
 
Déplace tour1 => tour3
1 [3, 2] [] [1] 
 
Déplace tour1 => tour2
2 [3] [2] [1] 
 
Déplace tour3 => tour2
3 [3] [2, 1] [] 
 
Déplace tour1 => tour3
4 [] [2, 1] [3] 
 
Déplace tour2 => tour1
5 [1] [2] [3] 
 
Déplace tour2 => tour3
6 [1] [] [3, 2] 
 
Déplace tour1 => tour3
7 [] [] [3, 2, 1]

Et pour n=4:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
Etat des 3 tours au départ, avec 4 disques sur la tour 1:
tour 1: [4, 3, 2, 1] tour 2: [] tour 3: []
 
Déplace tour1 => tour2
1 [4, 3, 2] [1] [] 
 
Déplace tour1 => tour3
2 [4, 3] [1] [2] 
 
Déplace tour2 => tour3
3 [4, 3] [] [2, 1] 
 
Déplace tour1 => tour2
4 [4] [3] [2, 1] 
 
Déplace tour3 => tour1
5 [4, 1] [3] [2] 
 
Déplace tour3 => tour2
6 [4, 1] [3, 2] [] 
 
Déplace tour1 => tour2
7 [4] [3, 2, 1] [] 
 
Déplace tour1 => tour3
8 [] [3, 2, 1] [4] 
 
Déplace tour2 => tour3
9 [] [3, 2] [4, 1] 
 
Déplace tour2 => tour1
10 [2] [3] [4, 1] 
 
Déplace tour3 => tour1
11 [2, 1] [3] [4] 
 
Déplace tour2 => tour3
12 [2, 1] [] [4, 3] 
 
Déplace tour1 => tour2
13 [2] [1] [4, 3] 
 
Déplace tour1 => tour3
14 [] [1] [4, 3, 2] 
 
Déplace tour2 => tour3
15 [] [] [4, 3, 2, 1]

On retrouve le même nombre de déplacement à faire: 2**n-1

[danielhagnoul]

Je ne comprends pas ce que vous reprochez à la solution du message n° 2, qui n'est pas de moi et qui hors les commentaires tient en 3 lignes !

[wiztricks]

Se faire une idée de l'état de l'art est toujours source d'inspiration.

A noter que l'article de wikipedia cité par wiztricks existe aussi en français: https://fr.wikipedia.org/wiki/Tours_de_Hano%C3%AF

Je n'ai pas mentionné cet article car il est bien moins riche dans ses ouvertures.
Et quitte à revisiter les tours de Hanoï une n^ième fois, autant apprendre quelque chose de nouveau.

- W