#1
5
(Traduit par Microsoft)
-
- Je suppose que les règles de base pour déplacer les anneaux sont bien connues.
- Si le nombre d’anneaux est impair, vous n’avez besoin que d’une étape pour placer l’anneau supérieur directement sur le dessus de l’anneau que vous voulez.
- Si c’est égal, il faut deux étapes pour faire le déplacement. Supposons que les chevilles A, B et C de gauche à droite. Si, par exemple, sur B nous avons un tas avec des anneaux 1,2,3,4 et que vous voulez les placer sur l’anneau 5 sur C , la première étape sera 1 à A et 2 à C, et la prochaine, 1 à C.. .et avec un total de 15 mouvements, nous aurons les 1,2,3,4 anneaux de plus de 5 sur la cheville C.
- Dans la mise en page initiale il ya de plus grands anneaux sur le dessus de petits anneaux (c’est la principale différence de la version I de ce jeu), mais quand vous commencez à jouer, vous ne pouvez pas mettre un anneau plus grand sur le dessus d’un plus petit comme dans la tour de Hanoi I.
- Je pense que la meilleure approche pour résoudre le jeu est de commencer par un rapide coup d’oeil aux positions des anneaux 9, 8 et 7. Il est important de voir si l’anneau 9 est déjà sur la base d’une cheville. Et si ce n’est pas le cas, quelle est la meilleure façon est (moins de mouvements) de le mettre là. Dans ce cas, il arrive souvent (surtout si 7 et 8 sont sur des chevilles différentes) que l’on a besoin de placer 7 sur 8 pour avoir une cheville libre pour 9. En outre, nous pouvons avoir à placer 6 sur 9, 7 se déplaçant à la cheville libre après le déplacement 6, puis 6 sur 7 . Le résultat sera un tas de 1 à 7 et le besoin de 127 mouvements supplémentaires pour placer ces 7 anneaux sur le dessus de 8,9 (le nombre minimal de mouvements pour résoudre un jeu dans la tour de Hanoi I situation est: mouvements minimes = 2 ^ n - 1 où n est le nombre d’anneaux de sorte, 3 anneaux auront besoin de 7 mouvements, 4 anneaux auront besoin de 15 ... 7 anneaux auront besoin de 127 et ainsi de suite).
- Quoi qu’il en soit, le but est, avec le nombre minimal de mouvements possibles, de changer la disposition initiale à une tour de Hanoi I situation. Cela signifie que vous saurez toujours à l’avance si le jeu peut être résolu sans avoir à réellement le terminer. Lorsque les anneaux sont dans une tour de Hanoi je situation (un tas dans l’ordre croissant à partir des anneaux 1,2 ... sur une cheville, une cheville libre, et une cheville avec les anneaux restants, également dans l’ordre croissant, la finition sur la base de la cheville où 9 est), il suffit d’ajouter les mouvements déjà faits aux mouvements nécessaires donnés par l’équation ci-dessus et le résultat doit être égal aux mouvements minimaux nécessaires (chaque fois que je fais ce contrôle juste ajouter le dernier chiffre).
- Trois exemples (tous à partir de ce site).
- Disposition initiale (145 mouvements minimaux nécessaires)
Cheville A - 1,8,2,9
Peg B - 7,3
Peg C - 6,5,4
Étape 1 - La meilleure stratégie est de placer 9 sur la base de la cheville C et 6 sur le dessus de 7 sur la cheville B.
Premier mouvement: anneau 3 sur le dessus de 9 sur A, puis 4 sur le dessus de 7 sur B ...
Après 18 mouvements de la mise en page initiale, nous obtenons:
Peg A - 1
Peg B - 7,6,5,4,3,2 18 mouvements
Peg C – 9,8
Étape 2 – Si nous regardons attentivement cette disposition, nous remarquerons que c’est l’équivalent de 6 anneaux sur le dessus de 7 sur B, à condition que le prochain mouvement est de placer l’anneau 1 sur le dessus de 8 sur C. Nous parlons de 6 anneaux (6,5 ... 1 qui est, même, sur la cheville B et 2 étapes sont nécessaires). Donc, pour placer ces six anneaux sur A, nous avons besoin d’un premier mouvement pour placer 1 sur l’autre cheville, dans ce cas C.
Comme nous le savons déjà, pour déplacer 6 anneaux à une autre cheville (cheville A) nous avons besoin de 63 mouvements. Après ces mouvements, il ya un autre à placer 7, maintenant libre, en plus de 9,8.
Donc, dans cette étape 2 les mouvements seront 63 + 1 = 64 et la mise en page que nous obtenons est:
A - 6,5,4,3,2,1
B - 63+1 = 64 mouvements
C - 9,8,7
Jusqu’à présent, nous avons 18 coups sur l’étape 1 plus 64 sur l’étape 2
Étape 3 – La disposition ci-dessus correspond à ce que j’appelle une tour de Hanoi I situation.
Pour terminer le jeu, nous avons besoin de déplacer les 6 anneaux (6,5,... 1) sur la cheville A au sommet de 9,8,7 sur la cheville C. Cela nécessitera 63 autres mouvements.
Total des mouvements = 18 + 64 + 63 = 145 qui est le minimum de mouvements nécessaires. - Disposition initiale (256 mouvements minimaux nécessaires)
A - 5,3,9
B - 8,1,6,4
C - 2,7
Pour placer 9 sur la base, comme 8 et 7 sont sur des chevilles différentes, nous avons besoin de placer 7 sur le dessus de 8 sur B.
Étape 1 - Notre objectif est de placer 9 sur C et 7 sur le dessus de 8 sur B. Pour ce faire, nous avons d’abord besoin de passer 6,4 au sommet de 9 sur A à C gratuit pour recevoir le 9.
Les cinq premiers mouvements sont 4 au-dessus de 7,6 sur le dessus de 9 sur A ,4 à 6,1 à 4 et 7 à 8 sur la cheville B.
Après 20 mouvements, la mise en page sera
A – 5,3
B – 8,7,6,4,2,1 20 mouvements
C – 9
Étape 2 place 6 sur 9 sur la cheville C. Pour ce faire, nous avons besoin de 4 sur le dessus de 5 sur A finition cette étape 2 avec 5,4,3,2,1 sur la cheville A . Cela se fait avec 13 mouvements et la mise en page est
A – 5,4,3,2,1
B – 8, 7 13 coups
C - 9,6
Étape 3 – Déplacez 5,4...,1 (5 anneaux) vers le haut de 6 sur la cheville C. Cela correspond à 31 mouvements plus 1 à placer 7 sur la cheville A. Ainsi, le nombre de mouvements à l’étape 3 31+1=32 et la mise en page seront
A – 7
B – 8 32 coups
C – 9,6,5,4,3,2,1
Étape 4 - Déménagement 6,5,... 1 au sommet de 7 sur la cheville A nécessitera (6 anneaux) 63 coups plus un autre pour mettre 8 sur le dessus de 9 sur C. Total se déplace sur l’étape 4 63+1=64 et la disposition
A – 7,6,5,4,3,2,1
B - 63+1 = 64 mouvements
C - 9,8
Étape 5
Nous avons une tour de Hanoi I situation. La dernière étape consiste à déplacer les 7 anneaux de la cheville A
au sommet de 9,8 sur la cheville C. Cela signifie 127 mouvements.
Total des mouvements- 20 + 13 + 32 + 64 + 127 = 256 mouvements minimes nécessaires. - Disposition initiale (303 mouvements minimaux nécessaires)
A – 4,9,7,5,8
B – 6,2
C – 3,1
Cet exemple est un peu plus difficile que les deux précédents.
Notez que 9 est coincé sur A avec trois anneaux sur le dessus (7,5,8). En outre, B et C ne sont pas des chevilles libres. Il est clair la nécessité de placer le 8,7 sur une cheville libre sinon nous n’aurons pas une cheville libre pour 9.
La meilleure façon de le faire est de placer 8,7 sur la cheville C et passer 6 au sommet de 8,7 sur C.
Après cela est fait Peg B sera libre de recevoir 9. Notez cependant, avant de libérer 7 nous avons besoin de placer 5 sur le dessus de 6 sur B.
Étape 1 - Place 8, sur C et 6,5,3,2,1 sur B
Les sept premiers mouvements sont les suivants :
2 sur A
1 sur A
3 sur le dessus B (au-dessus de 6)
1 sur C
2 sur B
1 sur B
8 sur C
23 mouvements après le départ, nous obtenons la disposition
A – 4,9
B – 6,5,3,2,1 23 mouvements
C – 8,7
Étape 2 – Placez les 6,5,3,2,1 (5 anneaux) sur C au-dessus de 8,7 (la cheville B sera libre de placer le 9).
Déplacer 5 anneaux à une autre cheville nécessite 31 mouvements plus un autre à placer 9 sur B donc, dans cette étape, nous avons besoin de 31 +1 = 32 mouvements .
La mise en page est
A – 4
B – 9 31+1= 32 mouvements
C – 8,7,6,5,3,2,1
Étape 3 – Le but est maintenant de libérer la cheville A pour recevoir 7 (sinon nous ne pouvons pas placer 8 sur le dessus de 9). Pour ce faire, il est nécessaire de déplacer 6,5,3,2,1 à B sur le dessus de 9.
Mais comme les mouvements sont alternatifs à la place 6 sur B, nous avons précédemment besoin de placer le 5 sur A et 4 sur B ...
Après 57 mouvements à partir du début sur l’étape 2, nous aurons la disposition suivante.
A – 7
B – 9,6,5,4,3,2,1 57 mouvements
C – 8
Il est évident que ces 57 mouvements doivent suivre une logique. En fait, ils peuvent être décomposés sur les actions suivantes
Action Nombre de mouvements 4 sur B 1 3,2,1 (3 anneaux) sur le top 4 sur B 7 5 à A 1 4,3,2,1 (4 anneaux) à A 15 6 à B 1 5,4,3,2,1 (5 anneaux) à B en plus de 6 31 7 à A 1 Total 57
Étape 4 - déplacer 6,5 .....2,1 (6 anneaux) à A sur le dessus de 7. Cela nécessite 63 mouvements. Maintenant, il est possible de placer 8 sur le dessus de 9 sur B ce qui signifie un mouvement supplémentaire.
Donc, dans cette étape 4 il ya un total de 63 +1 = 64 mouvements
Une fois cela fait, la mise en page est
A – 7,6,5,4,3,2,1
B – 9,8, 63+1=64 (Situation de la Tour de Hanoi I)
C –
Étape 5 – La dernière étape consiste à déplacer 7,6,... 2,1 à la cheville B au sommet de 9,8 .
Pour déplacer 7 anneaux, 127 mouvements seront nécessaires.
Ainsi, les mouvements totaux sont 23+32+57+64+127= 303 mouvements minimes nécessaires
- Disposition initiale (145 mouvements minimaux nécessaires)
(Original) Solving Tower of Hanoi II
-
- I assume the basic rules for moving the rings are well known.
- If the number of rings is odd you only need 1 step to place the top ring straight on top of the ring you want.
- If it’s even, there is a need for two steps to make the move. Let’s assume pegs A,B and C from left to right. If, for example, on B we have a pile with rings 1,2,3,4 and want to place them over ring 5 on C , the first step will be 1 to A and 2 to C, and next, 1 to C.. .and with a total of 15 moves we will have the 1,2,3,4 rings over 5 on peg C.
- In the initial layout there are larger rings on top of smaller rings (that’s the main difference from version I of this game) but when you start playing you can’t put a larger ring on top of a smaller one as in Tower of Hanoi I.
- I think the best approach to solve the game is starting with a quick look at the positions of rings 9, 8 and 7. It’ s important to see if ring 9 is already on the base of a peg. And if it isn’t, what the best way is (less moves) to put it there. In this case it often happens (especially if 7 and 8 are on different pegs) that one needs to place 7 over 8 to have a free peg for 9. Moreover we may have to place 6 on 9, 7 moving to the free peg after moving 6 and then 6 over 7 . The result will be a pile from 1 to 7 and the need of 127 additional moves to place these 7 rings on top of 8,9 (the minimal number of moves to solve a game in Tower of Hanoi I situation is : minimal moves = 2^n - 1 where n is the number of rings so, 3 rings will need 7 moves, 4 rings will need 15… 7 rings will need 127 and so on).
- Whatever the case, the purpose is, with the minimal number of moves possible, to change the initial layout to a Tower of Hanoi I situation. This means you will always know in advance if the game can be solved without having to actually finish it. When the rings are in a Tower of Hanoi I situation (a pile in ascending order starting with rings 1,2… on one peg, a free peg, and a peg with the remaining rings, also in ascending order, finishing on the base of the peg where 9 is), just add the moves already made to the necessary moves given by the above equation and the result should be equal to the minimal moves needed (whenever I do that control just add the last digit).
- Three examples (all from this website).
- Initial layout (145 minimal moves needed)
Peg A - 1,8,2,9
Peg B - 7,3
Peg C - 6,5,4
Step 1 - The best strategy is to place 9 on the base of peg C and 6 on top of 7 on peg B.
First move is: ring 3 on top of 9 on A, then 4 on top of 7 on B…
After 18 moves from the initial layout we get:
Peg A - 1
Peg B - 7,6,5,4,3,2 18 moves
Peg C – 9,8
Step 2 – If we look at this layout carefully, we’ll note this is equivalent to 6 rings on top of 7 on B, provided the next move is to place ring 1 on top of 8 on C. We are speaking of 6 rings (6,5 …1 that is, even, on peg B and 2 steps are required). So to place these six rings on A we need a first move to place 1 on the other peg, in this case C.
As we already know, to move 6 rings to another peg (peg A) we need 63 moves. After these moves there is an addtional one to place 7, now free, on top of 9,8.
So, in this Step 2 the moves will be 63 + 1= 64 and the layout we get is:
A - 6,5,4,3,2,1
B - 63+1 = 64 moves
C - 9,8,7
So far, we have 18 moves on Step 1 plus 64 on Step 2
Step 3 – The above layout corresponds to what I call a Tower of Hanoi I situation.
To finish the game we need to move the 6 rings (6,5,…1) on peg A to the top of 9,8,7 on peg C. This will require another 63 moves.
Total moves= 18 + 64 + 63 = 145 which is the minimal moves needed. - Initial layout (256 minimal moves needed)
A - 5,3,9
B - 8,1,6,4
C - 2,7
To place 9 on the base, as 8 and 7 are on different pegs, we need to place 7 on top of 8 on B.
Step 1 - Our goal is to place 9 on C and 7 on top of 8 on B. To achieve this we first need to move 6,4 to the top of 9 on A to free C to receive the 9.
The first five moves are 4 on top of 7,6 on top of 9 on A ,4 to 6,1 to 4 and 7 to 8 on peg B.
After 20 moves the layout will be
A – 5,3
B – 8,7,6,4,2,1 20 moves
C – 9
Step 2 place 6 over 9 on peg C. To achieve this we need 4 on top of 5 on A finishing this Step 2 with 5,4,3,2,1 on peg A . This is done with 13 moves and the layout is
A – 5,4,3,2,1
B – 8, 7 13 moves
C - 9,6
Step 3 – Move 5,4…,1 (5 rings) to the top of 6 on peg C. This corresponds to 31 moves plus 1 to place 7 on peg A. So, the number of moves in Step 3 31+1=32 and the layout will be
A – 7
B – 8 32 moves
C – 9,6,5,4,3,2,1
Step 4 - Moving 6,5,…1 to the top of 7 on peg A will require (6 rings) 63 moves plus another one one to put 8 on top of 9 on C. Total moves on Step 4 63+1=64 and the layout
A – 7,6,5,4,3,2,1
B - 63+1 = 64 moves
C - 9,8
Step 5
We have a Tower of Hanoi I situation. The final step is moving the 7 rings from peg A
to the top of 9,8 on peg C. This means 127 moves.
Total moves- 20 + 13 + 32 + 64 + 127 = 256 minimal moves needed. - Initial layout (303 minimal moves needed)
A – 4,9,7,5,8
B – 6,2
C – 3,1
This example is a bit harder than the previous two.
Note that 9 is stuck on A with three rings on top (7,5,8). Also, B and C are not free pegs. It’s clear the need to place the 8,7 on a free peg otherwise we will not have a free peg for 9.
The best way to do this is to place 8,7 on peg C and move 6 to the top of 8,7 on C.
After this is done Peg B will be free to receive 9. Note however, before freeing 7 we need to place 5 on top of 6 on B.
Step 1 - Place 8, on C and 6,5,3,2,1 on B
The first seven moves are:
2 on A
1 on A
3 on top B (on top of 6)
1 on C
2 on B
1 on B
8 on C
23 moves after the start we get the layout
A – 4,9
B – 6,5,3,2,1 23 moves
C – 8,7
Step 2 – Place the 6,5,3,2,1 (5 rings) on C on top of 8,7 (peg B will be free to place the 9).
Moving 5 rings to another peg requires 31 moves plus another one to place 9 on B so, in this step we need 31+1 =32 moves .
The layout is
A – 4
B – 9 31+1= 32 moves
C – 8,7,6,5,3,2,1
Step 3 – The purpose now is to free peg A to receive 7 (otherwise we can’t place 8 on top of 9). To acheive this it’s needed to move 6,5,3,2,1 to B on top of 9.
But as the moves are alternate to place 6 on B we previously need to place the 5 on A and 4 on B…
After 57 moves from the start on Step 2 we will have the following layout.
A – 7
B – 9,6,5,4,3,2,1 57 moves
C – 8
It’s obvious these 57 moves must follow a logic. In fact they can be decomposed on the following actions
Action Number of moves 4 on B 1 3,2,1 (3 rings) on top 4 on B 7 5 to A 1 4,3,2,1 (4 rings) to A 15 6 to B 1 5,4,3,2,1 (5 rings) to B on top of 6 31 7 to A 1 Total 57
Step 4 - move 6,5…..2,1 (6 rings) to A on top of 7. This needs 63 moves. Now it’s possible to place 8 on top of 9 on B which means an additional move.
So in this Step 4 there is a total of 63+1 = 64 moves
After this is done the layout is
A – 7,6,5,4,3,2,1
B – 9,8, 63+1=64 (Tower of Hanoi I situation)
C –
Step 5 – The final step is to move 7,6,…2,1 to peg B to the top of 9,8 .
To move 7 rings, 127 moves will be needed.
So, the total moves are 23+32+57+64+127= 303 moves minimal moves needed
- Initial layout (145 minimal moves needed)
par Slb
2020-02-13 16:10:02
J’aime
Répondre