Solução Iterativa Para o Problema Da Torre De Hanói

Introdução

A resolução do quebra-cabeça Torre de Hanói é um problema conhecido na área da computação. A sua solução mais comum é um dos exemplos clássicos de recursão e bastante usada didaticamente para exemplificar algoritmos recursivos.

Nesse post de hoje iremos aprender como montar uma solução iterativa para o problema das torres. Essa solução parece ser a mais eficiente até hoje [7], sendo bastante rápida e concisa, porém um pouco “misteriosa” por envolver manipulação de bits.

Definição

Torre de Hanói

Torre De Hanói é um quebra-cabeça criado pelo matemático francês Edourd Lucas em 1883. Esse quebra-cabeça consiste de 3 hastes e n discos, inicialmente dispostos em ordem decrescente de tamanho na haste esquerda. O objetivo desse jogo é transferir os n discos da haste inicial para a haste mais a direita, seguindo as regras:

• Um disco deve ser movido de cada vez.
• Cada movimento consiste em retirar um disco do topo de uma haste e passar para o topo de outra haste.
• Um disco maior não deve ficar por cima de um disco menor.

Versões Online

Antes de mais nada, gostaria de dizer que há várias versões online da Torre de Hanói. A referência [2] contém uma dessas versões.

No decorrer desse tutorial sempre que possível tire suas dúvidas nas versões online.

Solução mínima geral [3]

Dado um número n de discos, é possível encontrar matematicamente o menor número de movimentos a serem feitos para solucionar o problema das torres. Obviamente você pode gastar um número maior de movimentos que o mínimo, porém é sempre útil encontrarmos uma solução mínima para um determinado problema.

O algoritmo abaixo, se seguido, garantirá a solução ótima, ou seja, o menor número de movimentos.

1. Mova o menor disco para a haste não recentemente visitada. Se for o primeiro movimento do jogo, mova o disco menor para a haste destino se o número de discos for ímpar, caso contrário, mova o disco menor para a haste auxiliar.
2. Mova o disco disponível (nesse ponto só há um movimento “legal” a ser feito)
3. Repita os passos 1 e 2 até resolver o problema.

Para verificar a validade desse algoritmo você pode fazer anotações para números pequenos de n (ex: n=3).

OBS: A “prova” de que esse algoritmo garante o menor número de movimentos não será vista aqui. Para mais informações consulte [3].

Versão Recursiva

A versão recursiva para esse problema é muito usada em cursos de computação como método didático para ensinar recursão. A seguir um roteiro mostrando como implementar esse problema de forma recursiva [2].

Primeiro, chamamos as três hastes origem, auxiliar e destino de ORI, AUX e DEST, respectivamente. Para resolver o problema, cedo ou tarde o disco inferior (= o primeiro de baixo pra cima) deverá ser movido de ORI para DEST. Nesse ponto, todos os discos restantes estarão empilhados em forma decrescente na haste auxiliar (veja esse fato na animação em [2]). Após mover o disco inferior de ORI para DEST, os discos restantes terão que ser movidos de AUX para DEST. Portanto, para um número n de discos, o problema parece ser resolvido se seguirmos esses passos:

1. Mova os n-1 discos do topo de ORI para AUX, usando DEST como auxiliar.
2. Mova o disco de baixo de ORI para DEST.
3. Mova os n-1 discos de AUX para DEST, usando ORI como auxiliar.

Baseando-se nisso, temos uma solução recursiva para o problema:

/* [hanoirecursivo.c]
 * Solução recursiva para o problema da
 * torre de hanoi.
 * 
 * [Compilação]
 * $ gcc -o hanoirecursivo hanoirecursivo.c
 *
 * [Execução]
 * ./hanoirecursivo 3
 *
 * Sendo 3 o número de discos.
 *
 */
#include <stdio.h>
#include <stdlib.h> /* for atoi() */

void hanoi(int n, char *from, char *temp, char *to) {
    if ( n == 0 ) return ;

    hanoi(n-1, from, to, temp) ;
    printf("Mova disco %d de %s para %s\n", n, from, to) ;
    hanoi(n-1, temp, from, to) ;
}

int main(int argc, char **argv) {
    int i ;
    if ( argc > 1 )
        i = atoi(argv[1]) ;
    else
        i = 3 ; /* padrão: três discos */

    hanoi(i, "A", "B", "C") ; /* ORI, AUX, DEST */

    return 0;
}

O programa acima resolve de forma ótima o problema da torre de hanói:

$ ./hanoirecursivo 3
Mova disco 1 de A para C
Mova disco 2 de A para B
Mova disco 1 de C para B
Mova disco 3 de A para C
Mova disco 1 de B para A
Mova disco 2 de B para C
Mova disco 1 de A para C

$ ./hanoirecursivo 4
Mova disco 1 de A para B
Mova disco 2 de A para C
Mova disco 1 de B para C
Mova disco 3 de A para B
Mova disco 1 de C para A
Mova disco 2 de C para B
Mova disco 1 de A para B
Mova disco 4 de A para C
Mova disco 1 de B para C
Mova disco 2 de B para A
Mova disco 1 de C para A
Mova disco 3 de B para C
Mova disco 1 de A para B
Mova disco 2 de A para C
Mova disco 1 de B para C
$ ./hanoirecursivo 3 | wc -l
7
$ ./hanoirecursivo 4 | wc -l
15

Total de passos

De acordo com a solução recursiva, podemos montar uma equação de recorrência para esse problema:

T0 = 0
T(n) = 2*T(n-1) + 1

A função T(n) recebe um n (quantidade de discos) de entrada e retorna o número mínimo de movimentos necessários para movimentar todos os discos da haste origem até o destino.

Em [2] vemos como expandir essa equação a fim de encontrarmos uma fórmula fechada para ela:

f(n) = 2^n - 1

Sabendo disso, a quantidade mínima de movimentos para resolver o problema com n=3 discos é:

f(3) = 2^3 - 1
          = 8 - 1
          = 7

E para n=4:

f(4) = 2^4 - 1
          = 16 - 1
          = 15

Com isso comprovamos que a saída do programa hanoirecursivo foi correta (veja as duas últimas linhas da saída do programa).

OBS: A explicação das fórmulas apresentadas está além do escopo desse post. Para mais detalhes, veja referência [2].

Soluções Iterativas

Soluções iterativas são aquelas que resolvem um problema sem usar recursão, usando laços de repetição e em alguns casos, estruturas de dados, como pilha, fila, árvore, etc. No caso da torre de Hanói, a solução recursiva é muito mais intuitiva do que suas soluções iterativas, pois essas últimas necessitam de uma análise especial nas movimentações dos discos. Nesse post irei apresentar uma solução iterativa que utiliza os bits de um certo número k para gerar as movimentações. Essa solução não é única para o problema e existem outras, como podemos ver no link da wikipédia em [1].

A solução iterativa misteriosa

De acordo com [7] existe uma solução um tanto que misteriosa para resolução do problema da torre de hanói: todos os movimentos mínimos entre os discos estão “escondidos” na representação binária de um número.

O código

O seguinte código resolve o quebra-cabeça da torre de Hanói iterativamente:

/*
 * [hanoiterativo.c]
 * Resolve o quebra-cabeçaa da torre de Hanoi
 * de modo iterativo.
 *
 * [Compilação]
 * $ gcc -o hanoiterativo hanoiterativo.c
 *
 * [Execução]
 * $ ./hanoiterativo 3
 *
 * Sendo 3 o número de discos.
 */
#include <stdio.h>
#include <stdlib.h> /* for atoi() */

int main(int argc, char **argv) {
    int n = 3 ;
    int from, to, k ;

    if ( argc > 1 ) n = atoi(argv[1]) ;

    for(k=1; k < (1 << n); k++) {
        /* obtem haste origem */
        from = (k&(k-1))%3 ;

        /* obtem haste destino */
        to   = ((k|(k-1))+1)%3 ;

        /* descreve o movimento */
        printf("Mova disco de %d para %d\n", from, to) ;
    }

    return 0;
}

A saída do programa, para n=3 será:

$ ./hanoiterativo 3
Mova disco de 0 para 2
Mova disco de 0 para 1
Mova disco de 2 para 1
Mova disco de 0 para 2 (***)
Mova disco de 1 para 0
Mova disco de 1 para 2
Mova disco de 0 para 2

Considere, por enquanto, as hastes numeradas como 0, 1, 2 ao invés de “A”, “B” e “C” como abordado anteriormente.

Bem, observando o código percebemos que a mágica toda é feita usando manipulação de bits. Primeiro vemos que a condição do laço for é dada por (1<<n), que nada mais é que 2^n. Dessa forma o loop  itera por 2^n – 1 vezes, que na verdade é o número mínimo de movimentos para n discos.

Observando a saída do programa acima, percebemos que alguns padrões aparecem. Por exemplo, repare que as linhas acima e abaixo da linha central (marcada com asteriscos) são iguais, com a única diferença na ordem em que aparecem. Isso é uma consequência direta do algoritmo recursivo, pois nenhuma operação aritmética é feita nele, somente permutações das hastes.

O que as operações bit a bit do último código fazem é exatamente isso: Geram resultados que “imitam” perfeitamente os movimentos da torre de Hanói. A tabela seguinte mostra os valores para os primeiros 7 valores de k:

+---+------------------+-----------------+
|k  | (k & (k-1)) % 3  | (k | (k-1)) % 3 |
+---+------------------+-----------------+
|1  |    0 % 3 = 0     |    2 % 3 = 2    |
+---+------------------+-----------------+
|2  |    0 % 3 = 0     |    4 % 3 = 1    |
+---+------------------+-----------------+
|3  |    2 % 3 = 2     |    4 % 3 = 1    |
+---+------------------+-----------------+
|4  |    0 % 3 = 0     |    8 % 3 = 2    |
+---+------------------+-----------------+
|5  |    4 % 3 = 1     |    6 % 3 = 0    |
+---+------------------+-----------------+
|6  |    4 % 3 = 1     |    8 % 3 = 2    |
+---+------------------+-----------------+
|7  |    6 % 3 = 0     |    8 % 3 = 2    |
+---+------------------+-----------------+

Agora veja novamente a saída do programa hanoirecursivo, para n = 3:

$ ./hanoirecursivo 3 | tr ABC 012 # tr troca A por 0, B por 1 e C por 2
Mova disco 1 de 0 para 2
Mova disco 2 de 0 para 1
Mova disco 1 de 2 para 1
Mova disco 3 de 0 para 2
Mova disco 1 de 1 para 0
Mova disco 2 de 1 para 2
Mova disco 1 de 0 para 2

Repare que a sequência de movimentos (0, 2), (0, 1), (2, 1), …, (0, 2) é a mesma representada pelas expressões bit-a-bit vistas na tabela acima.

Prova

A seguir uma prova de que as expressões bit-a-bit geram, de fato, a sequência de movimentos do problema da torre de Hanói. Tudo dito aqui pode ser conferido na referência [5].

1) Nomeação das hastes

As três hastes são nomeadas como 0, 1, 2 para n ímpar e como 0, 2, 1 para n par, dessa maneira a haste final sempre será a 2 e o movimento inicial de 0 para 2. Em alguns casos, a haste do meio pode ser considerada final, em outros não, pois muitos algoritmos só consideram a haste 2 como final (vide [2]). Em geral, pense que a haste final não depende do algoritmo, mas somente dos “nomes” das próprias hastes.

2) Obtendo as hastes a partir de k

Considere k como o movimento de algum disco. Sabemos que para n=3 discos, temos no total 7 movimentos e com isso, o k varia de 1 a 7.

É fácil notar que para k ímpar o disco número 1 é que se movimenta e esse movimento é descrito pela sequência 0->2->1->0 para n ímpar e por 0->1->2->0 para n par. Em termos de k, o disco 1 se move da haste (k-1)%3 para a haste (k+1)%3, independente do n.

Para k par, podemos ter discos ímpares ou pares se movimentando. Para discos ímpares, eles sempre se movem da haste (k+2)%3 para a haste (k+4)%3. Os discos pares se movimentam em ordem inversa, ou seja, da haste (k+4)%3 para a haste (k+2)%3.

Bem, relembrando as propriedades do módulo, vemos que (k-1)%3 é igual a (k+2)%3, pois -1 e +2 representam o mesmo valor no conjunto Z3 = {0,1,2} (ambos representam o elemento +2, pois -1%3=2 e 2%3=2). Por esse mesmo motivo, constatamos que (k+1)%3 é igual a (k+4)%3.

Logo, encontramos algo mais geral que pode ser reformulado da seguinte maneira:

Para todo k: Para j ímpar, o movimento é de (k-1)%3 para (k+1)%3
             Para j par, o movimento é de (k+1)%3 para (k-1)%3

sendo j o identificador de um disco qualquer.

Podemos mostrar que essa propriedade se mantém apenas observando a saída do programa hanoirecursivo.

$ ./hanoirecursivo 3 | tr ABC 012
Mova disco 1 de 0 para 2  # k=1, j=1 (ímpar) move de (1-1)%3=0 para (1+1)%3=2
Mova disco 2 de 0 para 1  # k=2, j=2 (par)   move de (2+1)%3=0 para (2-1)%3=0
Mova disco 1 de 2 para 1  # k=3, j=1 (ímpar) move de (3-1)%3=2 para (3+1)%3=1
Mova disco 3 de 0 para 2  # k=4, j=3 (ímpar) move de (4-1)%3=0 para (4+1)%3=2
Mova disco 1 de 1 para 0  # k=5, j=1 (ímpar) move de (5-1)%3=1 para (5+1)%3=0
Mova disco 2 de 1 para 2  # k=6, j=2 (par)   move de (6+1)%3=1 para (6-1)%3=2
Mova disco 1 de 0 para 2  # k=7, j=1 (ímpar) move de (7-1)%3=0 para (7+1)%3=2

3) Relação entre k e j

Agora vamos encontrar uma relação entre k e j. Antes de tudo, tenha em mente que:

2^(2i + 1) % 3 = 2 (ou seja: 2^ímpar % 3 = 2)
2^(2i)     % 3 = 1 (ou seja: 2^par   % 3 = 1)

Assim, definimos os movimentos feitos para um dado disco j como:

Para i>=0,

Para j ímpar, ou seja j=2i - 1, temos:
     Da haste: (k-1)%3 = (k-2^(j-1))%3
     Para a haste: (k+1)%3 = (k+2^(j-1))%3

Para j par, ou seja j=2i + 2, temos:
     Da haste: (k+1)%3 = (k-2)%3 = (k-2^(j-1))%3
     Para a haste: (k-1)%3 = (k+2)%3 = (k+2^(j-1))%3

Derivamos as hastes para j ímpar impondo que 2^(j-1) %3 seja igual a 1 (2^par %3 = 1). Para j par, temos que considerar que (k+1)%3 = (k-2)%3, pois +1 e -2 tem o mesmo módulo 3. O 2, então, é substituído por 2^(j-1)%3 (2^ímpar %3 = 2), como observado nas propriedades de módulo 3.

Por fim, chegamos em algo importante: o movimento de um disco j qualquer é sempre descrito da seguinte maneira:

Para a dupla (k, j), o movimento de um disco j é descrito
da haste (k - 2^(j-1))%3 para a haste (k + 2^(j-1))%3

Os valores devem vir em dupla, pois um k define exatamente um j e vice-versa. Por exemplo, para n=3 sabemos que o disco j=3, no passo k=4 do algoritmo, se move de (4 – 2^2)%3=0 para (4 + 2^2)%3=2.

4) As operações bit-a-bit

Considere a forma binária de k e suponha um z, tal que:

z = número máximo de zeros mais à direita de k na base binária

ex: k=4=100, z=2
    k=5=101, z=0
    k=6=110, z=1

Definido z, agora vamos observar as operações lógicas vistas no código iterativo. A operação k&(k-1) zera o bit 1 menos significativo de k. Veja:

Para k=5   k&(k-1) = 0101 & 0100 = 0100 = 4
     k=12  k&(k-1) = 1100 & 1011 = 1000 = 8

Curiosamente podemos definir essa operação em termos de z, como sendo:

k&(k-1) = k - 2^z

ex: k=5=0101, z=0, k - 2^z = 5-2^0 = 5-1 = 4 = 0100
    k=12=01100, z=2, k - 2^z = 12-2^2 = 12-4 = 8 = 1000

Compare esses resultados com os anteriores. Outra curiosidade é que a operação k|(k-1) também pode ser definida em termos de z, assim:

k|(k-1) = k + 2^z - 1

Ou seja:

k=5=0101, z=0:
    k|(k-1) = 5|4 = 0101|100 = 101 = 5
    k + 2^z = 5 + 2^0 - 1 = 5
k=8=1000, z=3:
    k|(k-1) = 8|7 = 1000|0111 = 1111 = 15
    k + 2^z = 8 + 2^3 - 1 = 15

Caso tenha dúvidas, verifique você mesmo a veracidade dessas relações com alguns valores de k.

5) Movimentos a partir das operações lógicas

Esse é o último passo da prova. Aqui relacionamos os movimentos definidos em 3) com as operações lógicas em 4).

Sabemos que dado um par (k, j) podemos encontrar o movimento como sendo:
de (k - 2^(j-1)) % 3 para (k + 2^(j-1)) %3. Definindo j = z+1, temos então:

(k - 2^(j-1)) % 3 = (k - 2^z) % 3
                  = (k&(k-1)) % 3

(k + 2^(j-1)) % 3 = (k + 2^z) % 3
                  = ((k|(k-1))+1)%3
(cqd)

Com isso provamos que, dado um k, podemos encontrar “dentro de seus bits” a movimentação de um disco j. Veja que as operações bit-a-bit estão em função de k e por isso não sabemos dizer qual disco está sendo movido. Entretanto, como definimos j = z+1, podemos facilmente encontrar esse disco.

Abaixo, o código final que mostra a solução iterativa da torre de Hanói usando os conceitos demonstrados nesse post:

/*
 * [hanoiterativofinal.c]
 * Resolve o quebra-cabeça da torre de Hanói
 * de modo iterativo.
 *
 * [Compilação]
 * $ gcc -o hanoiterativofinal hanoiterativofinal.c
 *
 * [Execução]
 * $ ./hanoiterativofinal 3
 *
 * Sendo 3 o número de discos.
 */
#include <stdio.h>
#include <stdlib.h> /* for atoi() */

/* Para que a solução final esteja sempre
 * em C, devemos definir os nomes das hastes
 * de acordo com a paridade de n.
 */
char *nomehastepar[] = {"A", "C", "B"} ;
char *nomehasteimpar[] = {"A", "B", "C"} ;

/* Apontará para os nomes corretos. */
char **nomehaste ;

/* A operação de encontrar o valor de z se chama
 * `count trailing zeroes', e pode ser escrita
 * como:
 */
int ctz(int k) {
    int z = 0;

    if(k) { /* aqui k é sempre maior que 1 */
        while((k&1) == 0) {k=k>>1; z++;}
    }

    return z ;
}

/* Descreve o movimento */
void movedisco(int k, int from, int to) {
    printf("Mova disco %d de %s para %s\n", ctz(k)+1, nomehaste[from], nomehaste[to]) ;
} 

int main(int argc, char **argv) {
    int n = 3 ;
    int from, to, k ;

    if ( argc > 1 ) n = atoi(argv[1]) ;

    /* Para n ímpar */
    if ( n & 1 ) nomehaste = nomehasteimpar ;
    else nomehaste = nomehastepar ; /* para n par */

    for(k=1; k < (1 << n); k++) {
        /* obtém haste origem */
        from = (k&(k-1))%3 ;

        /* obtém haste destino */
        to   = ((k|(k-1))+1)%3 ;

        /* descreve o movimento */
        movedisco(k, from, to) ;
    }

    return 0;
}

Conclusão

Torre de Hanói é um problema clássico na computação cuja solução mais comum envolve o uso da recursão. Observando os padrões criados pelas movimentações dos discos, foi possível elaborar um conjunto de premissas que nos levaram a uma solução iterativa, um pouco que misteriosa, pois tudo que precisávamos (disco movido e descrição do movimento) estava “escondido” nos bits do identificador do movimento. Podemos provar que a solução iterativa de fato é uma alternativa viável como solução, e no fim do post fomos capazes de criar um código para essa solução iterativa.

Referências

[1] Tower of Hanoi, by Wikipedia (Acessado em: Maio/2012)
http://en.wikipedia.org/wiki/Tower_of_Hanoi

[2] Tower of Hanoi, by Cut The Knot (Acessado em: Maio/2012)
http://www.cut-the-knot.org/recurrence/hanoi.shtml

[3] Tower Of Hanoi & Reve Puzzles, by William McCann (Acessado em: Maio/2012)
http://cs.nyu.edu/courses/summer07/G22.2340-001/Presentations/McCann.pdf

[4] Tower of Hanoi, by Wolfram MathWorld (Acessado em: Maio/2012)
http://mathworld.wolfram.com/TowerofHanoi.html

[5] The “mysterious” TH algorithm explained, by M. Kolar (Acessado em: Maio/2012)
http://hanoitower.mkolar.org/moves.html

[6] How does this work? Weird Towers of Hanoi Solution, by stackoverflow (Acessado em: Maio/2012)
http://stackoverflow.com/questions/2209860/how-does-this-work-weird-towers-of-hanoi-solution

[7] The shortest and “mysterious” TH algorithm, by M. Kolar (Acessado em: Maio/2012)
http://hanoitower.mkolar.org/shortestTHalgo.html