Hoy 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:
