#1
5
(Traducido por Microsoft)
-
- Supongo que las reglas básicas para mover los anillos son bien conocidas.
- Si el número de anillos es impar sólo necesita 1 paso para colocar el anillo superior recto en la parte superior del anillo que desea.
- Si es par, hay una necesidad de dos pasos para hacer el movimiento. Supongamos clavijas A, B y C de izquierda a derecha. Si, por ejemplo, en B tenemos una pila con anillos 1,2,3,4 y queremos colocarlos sobre el anillo 5 en C, el primer paso será de 1 a A y 2 a C, y siguiente, 1 a C.. .y con un total de 15 movimientos tendremos los 1,2,3,4 anillos sobre 5 en la clavija C.
- En el diseño inicial hay anillos más grandes en la parte superior de anillos más pequeños (esa es la principal diferencia de la versión I de este juego) pero cuando empiezas a jugar no se puede poner un anillo más grande en la parte superior de uno más pequeño como en la Torre de Hanoi I.
- Creo que el mejor enfoque para resolver el juego es comenzar con una mirada rápida a las posiciones de los anillos 9, 8 y 7. Es importante ver si el anillo 9 ya está en la base de una clavija. Y si no lo es, cuál es la mejor manera (menos movimientos) para ponerlo allí. En este caso a menudo sucede (especialmente si 7 y 8 están en diferentes clavijas) que uno necesita colocar 7 sobre 8 para tener una clavija libre para 9. Por otra parte, es posible que tengamos que colocar 6 en 9, 7 pasar a la clavija libre después de mover 6 y luego 6 sobre 7 . El resultado será una pila de 1 a 7 y la necesidad de 127 movimientos adicionales para colocar estos 7 anillos en la parte superior de 8,9 (el número mínimo de movimientos para resolver un juego en la torre de Hanoi I situación es : movimientos mínimos - 2 n - 1 donde n es el número de anillos por lo que, 3 anillos necesitarán 7 movimientos, 4 anillos necesitarán 15 ... 7 anillos necesitarán 127 y así sucesivamente).
- Cualquiera que sea el caso, el propósito es, con el número mínimo de movimientos posibles, cambiar el diseño inicial a una situación de la Torre de Hanoi I. Esto significa que siempre sabrás de antemano si el juego se puede resolver sin tener que terminarlo. Cuando los anillos están en una situación de la Torre de Hanoi I (una pila en orden ascendente a partir de anillos 1,2... en una clavija, una clavija libre, y una clavija con los anillos restantes, también en orden ascendente, terminando en la base de la clavija donde está 9, sólo tiene que añadir los movimientos ya hechos a los movimientos necesarios dados por la ecuación anterior y el resultado debe ser igual a los movimientos mínimos necesarios (siempre que hago ese control sólo añadir el último dígito).
- Tres ejemplos (todos de este sitio web).
- Diseño inicial (145 movimientos mínimos necesarios)
Peg A - 1,8,2,9
Peg B - 7,3
Peg C - 6,5,4
Paso 1 - La mejor estrategia es colocar 9 en la base de la clavija C y 6 en la parte superior de 7 en la clavija B.
El primer movimiento es: anillo 3 en la parte superior de 9 en A, luego 4 en la parte superior de 7 en B...
Después de 18 movimientos desde el diseño inicial obtenemos:
Peg A - 1
Peg B - 7,6,5,4,3,2 18 movimientos
Peg C – 9,8
Paso 2 – Si miramos este diseño cuidadosamente, notaremos que esto es equivalente a 6 anillos en la parte superior de 7 en B, siempre que el siguiente movimiento sea colocar el anillo 1 encima de 8 en C. Estamos hablando de 6 anillos (6,5 ... 1 es decir, incluso, en la clavija B y 2 pasos son necesarios). Así que para colocar estos seis anillos en A necesitamos un primer movimiento para colocar 1 en la otra clavija, en este caso C.
Como ya sabemos, para mover 6 anillos a otra clavija (peg A) necesitamos 63 movimientos. Después de estos movimientos hay uno adicional para colocar 7, ahora gratis, en la parte superior de 9,8.
Por lo tanto, en este Paso 2 los movimientos serán 63 + 1 x 64 y el diseño que obtenemos es:
A - 6,5,4,3,2,1
B - 63+1 á 64 movimientos
C - 9,8,7
Hasta ahora, tenemos 18 movimientos en el Paso 1 más 64 en el Paso 2
Paso 3 – El diseño anterior corresponde a lo que llamo una situación de la Torre de Hanoi I.
Para terminar el juego necesitamos mover los 6 anillos (6,5,... 1) en la clavija A a la parte superior de 9,8,7 en la clavija C. Esto requerirá otros 63 movimientos.
Total de movimientos 18 + 64 + 63 a 145 que es el mínimo de movimientos necesarios. - Diseño inicial (256 movimientos mínimos necesarios)
A - 5,3,9
B - 8,1,6,4
C - 2,7
Para colocar 9 en la base, ya que 8 y 7 están en diferentes clavijas, tenemos que colocar 7 en la parte superior de 8 en B.
Paso 1 - Nuestro objetivo es colocar 9 en C y 7 encima de 8 en B. Para lograr esto primero tenemos que mover 6,4 a la parte superior de 9 en A para liberar A para recibir el 9.
Los primeros cinco movimientos son 4 encima de 7,6 en la parte superior de 9 en A ,4 a 6,1 a 4 y 7 a 8 en la clavija B.
Después de 20 movimientos, el diseño será
A – 5,3
B – 8,7,6,4,2,1 20 movimientos
C – 9
Paso 2 colocar 6 sobre 9 en la clavija C. Para lograr esto necesitamos 4 encima de 5 en A terminando este Paso 2 con 5,4,3,2,1 en la clavija A. Esto se hace con 13 movimientos y el diseño es
A – 5,4,3,2,1
B – 8, 7 13 movimientos
C - 9,6
Paso 3 – Mueva 5,4...,1 (5 anillos) a la parte superior de 6 en la clavija C. Esto corresponde a 31 movimientos más 1 para colocar 7 en la clavija A. Por lo tanto, el número de movimientos en el Paso 3 31 + 1 - 32 y el diseño será
A – 7
B – 8 32 movimientos
C – 9,6,5,4,3,2,1
Paso 4 - Mover 6,5,... 1 a la parte superior de 7 en la clavija A requerirá (6 anillos) 63 movimientos más otro para poner 8 en la parte superior de 9 en C. Total se mueve en el paso 4 63 + 1 - 64 y el diseño de la disposición
A – 7,6,5,4,3,2,1
B - 63+1 á 64 movimientos
C - 9,8
Paso 5
Tenemos una situación de la Torre de Hanoi I. El último paso es mover los 7 anillos de la clavija A
a la parte superior de 9,8 en la clavija C. Esto significa 127 movimientos.
Total de movimientos: 20 + 13 + 32 + 64 + 127 x 256 movimientos mínimos necesarios. - Diseño inicial (303 movimientos mínimos necesarios)
A – 4,9,7,5,8
B – 6,2
C – 3,1
Este ejemplo es un poco más difícil que los dos anteriores.
Tenga en cuenta que 9 está atascado en A con tres anillos en la parte superior (7,5,8). Además, B y C no son clavijas libres. Está claro la necesidad de colocar el 8,7 en una clavija libre de lo contrario no tendremos una clavija libre para 9.
La mejor manera de hacer esto es colocar 8,7 en la clavija C y mover 6 a la parte superior de 8,7 en C.
Después de esto se hace Peg B será libre de recibir 9. Tenga en cuenta, sin embargo, antes de liberar 7 tenemos que colocar 5 encima de 6 en B.
Paso 1 - Lugar 8, en C y 6,5,3,2,1 en B
Los primeros siete movimientos son:
2 en A
1 en A
3 en la parte superior B (encima de 6)
1 en C
2 en B
1 en B
8 en C
23 movimientos después del inicio obtenemos el diseño
A – 4,9
B – 6,5,3,2,1 23 movimientos
C – 8,7
Paso 2 – Coloque el 6,5,3,2,1 (5 anillos) en C encima de 8,7 (la clavija B será libre de colocar el 9).
Mover 5 anillos a otra clavija requiere 31 movimientos más otro para colocar 9 en B por lo que, en este paso necesitamos 31 + 1 32 movimientos .
El diseño es
A – 4
B – 9 31 +1o 32 movimientos
C – 8,7,6,5,3,2,1
Paso 3 – El propósito ahora es liberar la clavija A para recibir 7 (de lo contrario no podemos colocar 8 en la parte superior de 9). Para lograr esto es necesario mover 6,5,3,2,1 a B encima de 9.
Pero como los movimientos son alternativos para colocar 6 en B, anteriormente necesitamos colocar el 5 en A y 4 en B...
Después de 57 movimientos desde el principio en el paso 2 tendremos el siguiente diseño.
A – 7
B – 9,6,5,4,3,2,1 57 movimientos
C – 8
Es obvio que estos 57 movimientos deben seguir una lógica. De hecho, pueden descomponerse en las siguientes acciones
Acción Número de movimientos 4 en B 1 3,2,1 (3 anillos) en la parte superior 4 en B 7 5 a A 1 4,3,2,1 (4 anillos) a A 15 6 a B 1 5,4,3,2,1 (5 anillos) a B encima de 6 31 7 a A 1 Total 57
Paso 4 - mueve 6,5.....2,1 (6 anillos) a A encima de 7. Esto necesita 63 movimientos. Ahora es posible colocar 8 en la parte superior de 9 en B, lo que significa un movimiento adicional.
Así que en este Paso 4 hay un total de 63+1 a 64 movimientos
Después de esto se hace el diseño es
A – 7,6,5,4,3,2,1
B – 9,8, 63+1-64 (Situación de la Torre de Hanoi I)
C –
Paso 5 – El último paso es mover 7,6,... 2,1 a la clavija B a la parte superior de 9,8 .
Para mover 7 anillos, se necesitarán 127 movimientos.
Por lo tanto, los movimientos totales son 23+32+57+64+127o 303 mueve los movimientos mínimos necesarios
- Diseño inicial (145 movimientos mínimos necesarios)
(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)
de Slb
2020-02-13 16:10:02
Me gusta
Responder
Enviar una respuesta
Enviando…
La respuesta no ha podido ser publicada. Por favor, inténtelo de nuevo. Cerrado