PrEDA: el juego de las Torres de Hanói

Hoy traigo otro enigma matemático resuelto a modo de code-kata, un rompecabezas llamado las Torres de Hanói. El juego consiste en tres torres compuestas por discos que se apilan de forma decreciente, de forma que los discos de abajo siempre son mayores que los de arriba. Con cada movimiento sólo podemos mover un disco. Y tenemos que conseguir mover todos los discos que inicialmente están todos en la torre A a la torre B.

Haciendo ensayos, pruebas, partiendo de casos fáciles a más difíciles se puede establecer una estrategia por la cual se van moviendo todos los discos. Este problema bien conocido en computación se resuelve mediante la estrategia de divide y vencerás. Dividiendo el problema inicial, todos los discos en una torre, en subproblemas cada vez más sencillos y fáciles de abordar.

Se trata de un algoritmo recursivo. Cuyo caso base es mover un sólo disco. Si no estamos moviendo un sólo disco se subdivide en 2 problemas y se mueve un disco.

Preparando la torres

Creamos las tres Torres de Hanói, y ponemos todos los discos en la torre A:

<?php

define('NUMBER_OF_DISCS', 20);
define('TRACE', true);
define('TIME_TO_WAIT', 1);
$GLOBALS['towers'] = array();
$GLOBALS['towers']['A'] = array();
$GLOBALS['towers']['B'] = array();
$GLOBALS['towers']['C'] = array();
for ($i = NUMBER_OF_DISCS; $i >= 1; --$i) {
    array_push($GLOBALS['towers']['A'], $i);
}
$GLOBALS['movements'] = 0;

El algoritmo

A priori, es bastante complicado de ver la estrategia, pero con el código se verá fácilmente:

writeToScreen();

hanoi(NUMBER_OF_DISCS, $GLOBALS['towers']['A'], $GLOBALS['towers']['B'], $GLOBALS['towers']['C']);

echo 'FINAL TOWERS!'.PHP_EOL;
writeToScreen();
echo 'NUMBER OF MOVEMENTS DONE: '.$GLOBALS['movements'].PHP_EOL;

// N, origen, destino , auxiliar
function hanoi($N, &$A, &$B, &$C)
{
    if (TRACE) {
        echo '==============>> HANOI! N='.$N.PHP_EOL;
        sleep(TIME_TO_WAIT);
    }
    if ($N == 1) {
        //echo 'Pasar disco de A a B'.PHP_EOL;
        array_push($B, array_pop($A));
        if (TRACE) {
            echo '--> MOVING DISC!'.PHP_EOL;
            writeToScreen();
            sleep(TIME_TO_WAIT);
        }
        ++$GLOBALS['movements'];
    } else {
        hanoi($N - 1, $A, $C, $B);
        //echo 'Pasar disco de A a B'.PHP_EOL;
        array_push($B, array_pop($A));
        if (TRACE) {
            echo '--> MOVING DISC!'.PHP_EOL;
            writeToScreen();
            sleep(TIME_TO_WAIT);
        }
        ++$GLOBALS['movements'];
        hanoi($N - 1, $C, $B, $A);
    }
}

function writeToScreen()
{
    foreach ($GLOBALS['towers'] as $key => $value) {
    echo $key.'>>';
    foreach ($value as $element) {
        echo str_pad($element, 3, ' ', STR_PAD_BOTH);
    }
    echo PHP_EOL;
    }
}

He marcado en negrita lo principal del algoritmo. El resto del código es auxiliar. Unas líneas clave son el pop y push de las colas, es decir, de las torres:

array_push($B, array_pop($A));

Este código saca de la torre $A el disco de arriba y lo pone arriba en la torre $B.

Jugando

Si todo va bien, podemos poner este script en un fichero de PHP, y ejecutarlo desde línea de comandos. Tenemos que ver algo parecido a esto:

Todos discos estaban inicialmente en la torre A y se han movido a la torre B en alrededor de un millón de movimientos. Este algoritmo tiene un coste de 2^N donde N es el número de discos. En este caso, con 20 discos, tenemos 2^20=1048575 movimientos..

Para más información me remito a la Wikipedia que está muy bien explicado: https://es.wikipedia.org/wiki/Torres_de_Han%C3%B3i