#1
5
(Traduzido por Microsoft)
-
- Presumo que as regras básicas para mover os anéis são bem conhecidas.
- Se o número de anéis for estranho, você só precisa de 1 passo para colocar o anel superior em cima do anel que você deseja.
- Se estiver empatado, há a necessidade de dois passos para fazer a mudança. Vamos supor que os pinos A, B e C da esquerda para a direita. Se, por exemplo, em B temos uma pilha com anéis 1,2,3,4 e queremos colocá-los sobre o anel 5 em C , o primeiro passo será 1 a A e 2 para C, e em seguida, 1 a C.. .e com um total de 15 movimentos teremos os 1,2,3,4 anéis sobre 5 na peg C.
- No layout inicial há anéis maiores em cima de anéis menores (essa é a principal diferença da versão I deste jogo), mas quando você começa a jogar você não pode colocar um anel maior em cima de um menor como em Tower of Hanoi I.
- Acho que a melhor abordagem para resolver o jogo é começar com uma rápida olhada nas posições dos anéis 9, 8 e 7. É importante ver se o anel 9 já está na base de um pino. E se não for, qual é a melhor maneira (menos movimentos) para colocá-lo lá. Neste caso, muitas vezes acontece (especialmente se 7 e 8 estão em pinos diferentes) que é preciso colocar 7 sobre 8 para ter um pino livre para 9. Além disso, podemos ter que colocar 6 em 9, 7 movendo-se para o pino livre depois de mover 6 e depois 6 sobre 7 . O resultado será uma pilha de 1 a 7 e a necessidade de 127 movimentos adicionais para colocar esses 7 anéis em cima de 8,9 (o número mínimo de movimentos para resolver um jogo na Situação da Torre de Hanói I é : movimentos mínimos = 2^n - 1 onde n é o número de anéis assim, 3 anéis precisarão de 7 movimentos, 4 anéis precisarão de 15... 7 anéis precisarão de 127 e assim por diante).
- Seja qual for o caso, o objetivo é, com o número mínimo de movimentos possíveis, mudar o layout inicial para uma situação da Torre de Hanói I. Isso significa que você sempre saberá com antecedência se o jogo pode ser resolvido sem ter que realmente terminá-lo. Quando os anéis estão em uma situação torre de Hanói I (uma pilha em ordem ascendente começando com anéis 1,2... em um pino, um pino livre, e um pino com os anéis restantes, também em ordem ascendente, terminando na base do pino onde 9 está), basta adicionar os movimentos já feitos aos movimentos necessários dados pela equação acima e o resultado deve ser igual aos movimentos mínimos necessários (sempre que eu fizer esse controle basta adicionar o último dígito).
- Três exemplos (todos deste site).
- Layout inicial (145 movimentos mínimos necessários)
Peg A - 1,8,2,9
Peg B - 7,3
Peg C - 6,5,4
Passo 1 - A melhor estratégia é colocar 9 na base do peg C e 6 em cima de 7 na estaca B.
O primeiro movimento é: anel 3 em cima de 9 em A, depois 4 em cima de 7 em B...
Depois de 18 movimentos do layout inicial, recebemos:
Peg A - 1
Peg B - 7,6,5,4,3,2 18 movimentos
Peg C – 9,8
Passo 2 – Se olharmos com cuidado para este layout, notamos que isso equivale a 6 anéis em cima de 7 em B, desde que o próximo passo seja colocar o anel 1 em cima de 8 em C. Estamos falando de 6 anéis (6,5 ... 1 ou seja, mesmo, nas estacas B e 2 etapas são necessárias). Então, para colocar esses seis anéis em A precisamos de um primeiro movimento para colocar 1 no outro pino, neste caso C.
Como já sabemos, para mover 6 anéis para outro pino (peg A) precisamos de 63 movimentos. Depois desses movimentos há um adicional para colocar 7, agora livre, em cima de 9,8.
Então, nesta etapa 2 os movimentos serão 63 + 1= 64 e o layout que o obter é:
A - 6,5,4,3,2,1
B - 63+1 = 64 movimentos
C - 9,8,7
Até agora, temos 18 movimentos no Passo 1 mais 64 no Passo 2
Passo 3 – O layout acima corresponde ao que eu chamo de uma torre de Hanói I situação.
Para terminar o jogo precisamos mover os 6 anéis (6,5,... 1) no pino A até o topo de 9,8,7 na estaca C. Isso exigirá mais 63 movimentos.
Total de movimentos= 18 + 64 + 63 = 145 que são os movimentos mínimos necessários. - Layout inicial (256 movimentos mínimos necessários)
A - 5,3,9
B - 8,1,6,4
C - 2,7
Para colocar 9 na base, como 8 e 7 estão em pinos diferentes, precisamos colocar 7 em cima de 8 em B.
Passo 1 - Nosso objetivo é colocar 9 em C e 7 em cima de 8 em B. Para isso, primeiro precisamos passar 6,4 para o topo de 9 em A para liberar C para receber o 9.
Os cinco primeiros movimentos são 4 em cima de 7,6 em cima de 9 em A , 4 a 6,1 a 4 e 7 a 8 no peg B.
Após 20 movimentos, o layout será
A – 5,3
B – 8,7,6,4,2,1 20 movimentos
C – 9
Passo 2 coloque 6 sobre 9 na estaca C. Para isso, precisamos de 4 em cima de 5 em A terminando este Passo 2 com 5,4,3,2,1 na estaca A . Isso é feito com 13 movimentos e o layout é
A – 5,4,3,2,1
B – 8, 7 13 movimentos
C - 9,6
Passo 3 – Mova 5,4...,1 (5 anéis) para o topo de 6 na estaca C. Isso corresponde a 31 movimentos mais 1 para colocar 7 no pino A. Assim, o número de movimentos na Etapa 3 31+1=32 e o layout será
A – 7
B – 8 32 movimentos
C – 9,6,5,4,3,2,1
Passo 4 - Movendo 6,5,... 1 para o topo de 7 no pino A exigirá (6 anéis) 63 movimentos mais outro para colocar 8 em cima de 9 em C. Total move no Passo 4 63+1=64 e no layout
A – 7,6,5,4,3,2,1
B - 63+1 = 64 movimentos
C - 9,8
Passo 5
Temos uma situação na Torre de Hanói I. O passo final é mover os 7 anéis de peg A
para o topo de 9,8 na peg C. Isso significa 127 movimentos.
Total de movimentos- 20 + 13 + 32 + 64 + 127 = 256 movimentos mínimos necessários. - Layout inicial (303 movimentos mínimos necessários)
A – 4,9,7,5,8
B – 6,2
C – 3,1
Este exemplo é um pouco mais difícil do que os dois anteriores.
Note que 9 está preso em A com três anéis no topo (7,5,8). Além disso, B e C não são pinos livres. É claro a necessidade de colocar o 8,7 em um pino grátis caso contrário não teremos um pino livre para 9.
A melhor maneira de fazer isso é colocar 8,7 na estaca C e passar 6 para o topo de 8,7 em C.
Depois que isso for feito, o Peg B estará livre para receber 9. Nota, porém, antes de liberar 7 precisamos colocar 5 em cima de 6 em B.
Passo 1 - Lugar 8, em C e 6,5,3,2,1 na B
Os primeiros sete movimentos são:
2 em A
1 em A
3 no topo B (em cima de 6)
1 em C
2 em B
1 em B
8 em C
23 movimentos após o início temos o layout
A – 4,9
B – 6,5,3,2,1 23 movimentos
C – 8,7
Passo 2 – Coloque os 6,5,3,2,1 (5 anéis) em C em cima de 8,7 (o pino B estará livre para colocar o 9).
Mover 5 anéis para outro pino requer 31 movimentos mais outro para colocar 9 em B assim, nesta etapa precisamos de 31+1 =32 movimentos .
O layout é
A – 4
B – 9 31+1= 32 movimentos
C – 8,7,6,5,3,2,1
Passo 3 – O objetivo agora é liberar o pino A para receber 7 (caso contrário, não podemos colocar 8 em cima de 9). Para isso, é necessário mover 6,5,3,2,1 para B em cima de 9.
Mas como os movimentos são alternativos para colocar 6 em B, anteriormente precisamos colocar os 5 em A e 4 no B...
Depois de 57 movimentos desde o início no Passo 2 teremos o seguinte layout.
A – 7
B – 9,6,5,4,3,2,1 57 movimentos
C – 8
É óbvio que esses 57 movimentos devem seguir uma lógica. Na verdade, eles podem ser decompostos nas seguintes ações
Ação Número de movimentos 4 em B 1 3,2,1 (3 anéis) no top 4 em B 7 5 a A 1 4,3,2,1 (4 anéis) para A 15 6 a B 1 5,4,3,2,1 (5 anéis) para B em cima de 6 31 7 a A 1 Total 57
Passo 4 - mova 6,5....2,1 (6 anéis) para A em cima de 7. Isso precisa de 63 movimentos. Agora é possível colocar 8 em cima de 9 em B, o que significa um movimento adicional.
Então, neste Passo 4 há um total de 63+1 = 64 movimentos
Depois que isso é feito o layout é
A – 7,6,5,4,3,2,1
B – 9,8, 63+1=64 (Torre de Hanói I)
C –
Passo 5 – O passo final é mover 7,6,... 2,1 para colocar B no topo de 9,8 .
Para mover 7 anéis, 127 movimentos serão necessários.
Assim, os movimentos totais são 23+32+57+64+127= 303 movimentos mínimos necessários
- Layout inicial (145 movimentos mínimos necessários)
(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)
por Slb
2020-02-13 16:10:02
Gosto
Responder