PrEDA: el problema del Salto del Caballo de ajedrez

php7-logoHoy traigo otro code-kata para practicar con estructuras de datos y algoritmos. El problema del caballo es un clásico problema matemático. Consiste en recorrer todas las casillas de un tablero de ajedrez sin repetirlas y a salto del caballo.

Esta vez, la forma más sencilla de abordarlo es simular el salto del caballo haciendo un árbol de posibles recorridos del caballo hasta conseguir llenar el tablero por completo. Es decir, partimos de una casilla, este será el nodo inicial del árbol. Entonces los hijos de cada nodo son los caminos posibles desde el nodo inicial hasta las casillas posibles siguientes. Si estamos en un tablero de 8×8, y hemos llegado a un nivel de ramificación de 64 quiere decir que hemos recorrido todas las casillas que hay. Entonces habríamos resuelto una de las soluciones.

La mejor forma de resolver este problema es por la estrategia de vuelta atrás. Es decir, se va ramificando mientras que el caballo va saltando. Si llega a una casilla en la que ya no tiene casillas a las que saltar se vuelve atrás, para entonces seguir ramificando por el resto de posibles caminos. Esto con una función recursiva queda bien sencillo.

Comienzo del programa

Para empezar a llamar al algoritmo tenemos que preparar el tablero. Ponemos el caballo en una casilla inicial, y llamamos al algoritmo para que resuelva el problema. Con esto:

define('N', 8);
define('TRACE', true);
define('WAITSECS', 1);
$GLOBALS['solutions'] = array();

$chessboard[N - 1] = array();
for ($i = 0; $i < N; ++$i) {
    for ($j = 0; $j < N; ++$j) {
        $chessboard[$i][$j] = 0;
    }
}
for ($i = 0; $i < N; ++$i) {
    for ($j = 0; $j < N; ++$j) {
        $chessboard[$i][$j] = 1;
        doHorseJump($chessboard);
        $chessboard[$i][$j] = 0;
    }
}

echo 'Finally found '.count($GLOBALS['solutions']).' solutions.'.PHP_EOL;

Lo principal del algoritmo

El esquema de vuelta atrás para este problema queda reducido a esto:

function doHorseJump($chessboard)
{
    if (TRACE) {
        echo '=================================>> jump!'.PHP_EOL;
    }
    if (isSolution($chessboard)) {
        writeToScreen($chessboard);
        $GLOBALS['solutions'][] = $chessboard;
    } else {
        foreach (possibleJumps($chessboard) as $posibleSolution) {
            doHorseJump($posibleSolution);
        }
    }
}

Es un algoritmo recursivo, que se llama a si mismo con cada posible salto. Va enumerando desde el 1 cada casilla por la que va saltando.

Los posibles saltos

Calcularlos a partir de la casilla numerada mayor (la actual). Esto es lo más trabajoso, pero es bastante simple. Queda de esta forma:

function possibleJumps($chessboard)
{
    $i = currentI($chessboard);
    $j = currentJ($chessboard);
    if (TRACE) {
        writeToScreen($chessboard);
        echo 'C $i='.$i.', $j='.$j;
    }
    $possibleJumps = array();

    // move up left
    if (TRACE) {
        echo '.';
    }
    if ($i - 1 >= 0 and $j - 2 >= 0 and $chessboard[$i - 1][$j - 2] == 0) {
        $possibleJumps['A'] = $chessboard;
        $possibleJumps['A'][$i - 1][$j - 2] = $chessboard[$i][$j] + 1;
        if (TRACE) {
            echo '^';
        }
    }
    // move up right
    if (TRACE) {
        echo '.';
    }
    if ($i + 1 < N and $j - 2 >= 0 and $chessboard[$i + 1][$j - 2] == 0) {
        $possibleJumps['B'] = $chessboard;
        $possibleJumps['B'][$i + 1][$j - 2] = $chessboard[$i][$j] + 1;
        if (TRACE) {
            echo '^';
        }
    }
    // move right up
    if (TRACE) {
        echo '.';
    }
    if ($i + 2 < N and $j - 1 >= 0 and $chessboard[$i + 2][$j - 1] == 0) {
        $possibleJumps['C'] = $chessboard;
        $possibleJumps['C'][$i + 2][$j - 1] = $chessboard[$i][$j] + 1;
        if (TRACE) {
            echo '^';
        }
    }
    // move rigth down
    if (TRACE) {
        echo '.';
    }
    if ($i + 2 < N and $j + 1 < N and $chessboard[$i + 2][$j + 1] == 0) {
        $possibleJumps['D'] = $chessboard;
        $possibleJumps['D'][$i + 2][$j + 1] = $chessboard[$i][$j] + 1;
        if (TRACE) {
            echo '^';
        }
    }
    // move down right
    if (TRACE) {
        echo '.';
    }
    if ($i + 1 < N and $j + 2 < N and $chessboard[$i + 1][$j + 2] == 0) {
        $possibleJumps['E'] = $chessboard;
        $possibleJumps['E'][$i + 1][$j + 2] = $chessboard[$i][$j] + 1;
        if (TRACE) {
            echo '^';
        }
    }
    // move down left
    if (TRACE) {
        echo '.';
    }
    if ($i - 1 >= 0 and $j + 2 < N and $chessboard[$i - 1][$j + 2] == 0) {
        $possibleJumps['F'] = $chessboard;
        $possibleJumps['F'][$i - 1][$j + 2] = $chessboard[$i][$j] + 1;
        if (TRACE) {
            echo '^';
        }
    }
    // move left down
    if (TRACE) {
        echo '.';
    }
    if ($i - 2 >= 0 and $j + 1 < N and $chessboard[$i - 2][$j + 1] == 0) {
        $possibleJumps['G'] = $chessboard;
        $possibleJumps['G'][$i - 2][$j + 1] = $chessboard[$i][$j] + 1;
        if (TRACE) {
            echo '^';
        }
    }
    // move left up
    if (TRACE) {
        echo '.';
    }
    if ($i - 2 >= 0 and $j - 1 >= 0 and $chessboard[$i - 2][$j - 1] == 0) {
        $possibleJumps['H'] = $chessboard;
        $possibleJumps['H'][$i - 2][$j - 1] = $chessboard[$i][$j] + 1;
        if (TRACE) {
            echo '^';
        }
    }

    if (TRACE) {
        if (count($possibleJumps) == 0) {
            echo ' found 0 possible ways doing backtrack!'.PHP_EOL;
        } else {
            echo ' found '.count($possibleJumps).' possible ways!'.PHP_EOL;
        }
        sleep(WAITSECS);
    }

   return $possibleJumps;
}

El resto de funciones

Necesitamos unas funciones auxiliares:

function isSolution($chessboard)
{
    for ($i = 0; $i < N; ++$i) {
        for ($j = 0; $j < N; ++$j) {
            if ($chessboard[$i][$j] == 0) {
                return false;
            }
        }
    }

    return true;
}

function writeToScreen($chessboard)
{
    for ($j = 0; $j < N; ++$j) {
        for ($i = 0; $i < N; ++$i) {
            echo str_pad($chessboard[$i][$j], 3, ' ', STR_PAD_BOTH);
        }
        echo PHP_EOL;
    }

    return true;
}

function currentI($chessboard)
{
    $currentI = 0;
    $jumpNumber = 0;
    for ($j = 0; $j < N; ++$j) {
        for ($i = 0; $i < N; ++$i) {
            if ($chessboard[$i][$j] > $jumpNumber) {
                $jumpNumber = $chessboard[$i][$j];
                $currentI = $i;
            }
        }
    }

    if (TRACE) {
        echo 'CurrentI = '.$currentI.PHP_EOL;
    }

    return $currentI;
}

function currentJ($chessboard)
{
    $currentJ = 0;
    $jumpNumber = 0;
    for ($j = 0; $j < N; ++$j) {
        for ($i = 0; $i < N; ++$i) {
            if ($chessboard[$i][$j] > $jumpNumber) {
                $jumpNumber = $chessboard[$i][$j];
                $currentJ = $j;
            }
        }
    }

    if (TRACE) {
        echo 'CurrentJ = '.$currentJ.PHP_EOL;
    }

    return $currentJ;
}

Todo junto

Si todo el código lo ponemos en un .php y lo ejecutamos desde línea de comandos veremos algo parecido a esto:

PrEDA horse jumping

Compartir..

Dejar un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *