Problema del salto del caballo en Javascript

El problema del salto de caballo (en inglés knight’s tour problem) es un problema clásico de uso de marcha atrás (backtracking) en la programación y es sencillo de realizar en cualquier código, en éste momento usaremos Javascript para ejemplificar el caso.

Fuente de imagen: https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/uncategorized/knight-tour

Introducción

Consiste en armar una secuencia de movimientos de un caballo en un tablero de ajedrez, de modo que el caballo visita cada casilla solo una vez. Si el caballo termina en una casilla que el caballo ya tocó en forma anterior, nos regresamos a la posición anterior buscando otro camino. Si el camino ya no tiene opciones, regresamos otra posición más y así hasta intentar recorrer el tablero nuevamente, buscando crear un camino único por todo el tablero.

El problema del salto del caballo es el problema matemático de encontrar el recorrido del caballero. Crear un programa para encontrar un recorrido de un caballo es un problema común para a los estudiantes de informática. Las variaciones del problema del recorrido del caballero incluyen tableros de ajedrez de diferentes tamaños que los habituales 8 × 8, así como tableros irregulares (no rectangulares).

El problema del recorrido del caballero es una instancia del problema más general del camino hamiltoniano en la teoría de grafos. El problema de encontrar el recorrido de un caballero cerrado es igualmente una instancia del problema del ciclo hamiltoniano.

Código del salto de caballo

Aquí mostramos el código del salto o recorrido de caballo en Javascript, éste código se encuentra en Github y tiene licencia MIT.

/**
 @param {number[][]} chessboard
 @param {number[]} position
 @return {number[][]}
 */
 function getPossibleMoves(chessboard, position) {
 // Generate all knight moves (even those that go beyond the board).
 const possibleMoves = [
 [position[0] - 1, position[1] - 2],
 [position[0] - 2, position[1] - 1],
 [position[0] + 1, position[1] - 2],
 [position[0] + 2, position[1] - 1],
 [position[0] - 2, position[1] + 1],
 [position[0] - 1, position[1] + 2],
 [position[0] + 1, position[1] + 2],
 [position[0] + 2, position[1] + 1],
 ];
 // Filter out all moves that go beyond the board.
 return possibleMoves.filter((move) => {
 const boardSize = chessboard.length;
 return move[0] >= 0 && move[1] >= 0 && move[0] < boardSize && move[1] < boardSize;
 });
 } 
 /**
 @param {number[][]} chessboard
 @param {number[]} move
 @return {boolean}
 */
 function isMoveAllowed(chessboard, move) {
 return chessboard[move[0]][move[1]] !== 1;
 } 
 /**
 @param {number[][]} chessboard
 @param {number[][]} moves
 @return {boolean}
 */
 function isBoardCompletelyVisited(chessboard, moves) {
 const totalPossibleMovesCount = chessboard.length ** 2;
 const existingMovesCount = moves.length;
 return totalPossibleMovesCount === existingMovesCount;
 } 
 /**
 @param {number[][]} chessboard
 @param {number[][]} moves
 @return {boolean}
 */
 function knightTourRecursive(chessboard, moves) {
 const currentChessboard = chessboard;
 // If board has been completely visited then we've found a solution.
 if (isBoardCompletelyVisited(currentChessboard, moves)) {
 return true;
 }
 // Get next possible knight moves.
 const lastMove = moves[moves.length - 1];
 const possibleMoves = getPossibleMoves(currentChessboard, lastMove);
 // Try to do next possible moves.
 for (let moveIndex = 0; moveIndex < possibleMoves.length; moveIndex += 1) {
 const currentMove = possibleMoves[moveIndex];
 // Check if current move is allowed. We aren't allowed to go to
 // the same cells twice.
 if (isMoveAllowed(currentChessboard, currentMove)) {
   // Actually do the move.
   moves.push(currentMove);
   currentChessboard[currentMove[0]][currentMove[1]] = 1;
 // If further moves starting from current are successful then
   // return true meaning the solution is found.
   if (knightTourRecursive(currentChessboard, moves)) {
     return true;
   }
 // BACKTRACKING.
   // If current move was unsuccessful then step back and try to do another move.
   moves.pop();
   currentChessboard[currentMove[0]][currentMove[1]] = 0;
 }
 }
 // Return false if we haven't found solution.
 return false;
 } 
 /**
 @param {number} chessboardSize
 @return {number[][]}
 */
 export default function knightTour(chessboardSize) {
 // Init chessboard.
 const chessboard = Array(chessboardSize).fill(null).map(() => Array(chessboardSize).fill(0));
 // Init moves array.
 const moves = [];
 // Do first move and place the knight to the 0x0 cell.
 const firstMove = [0, 0];
 moves.push(firstMove);
 chessboard[firstMove[0]][firstMove[0]] = 1;
 // Recursively try to do the next move.
 const solutionWasFound = knightTourRecursive(chessboard, moves);
 return solutionWasFound ? moves : [];
 } 

Conclusiones

El problema del salto de caballo es uno de los ejemplos clásicos de backtracking, que requiere prueba y error hasta encontrar un camino buscando entre todas las alternativas. Es un problema de fuerza bruta, sin embargo es la inspiración para el desarrollo de la solución de varios tipos de problemas en donde existen varias rutas, por ejemplo las rutas de transporte con menor tráfico.