Recuerdo que hace unos años me entretenía en clase rellenando las casillas de una especie de cuadrado mágico de 5 por 5 casillas en el que había que numerar todas las casillas siguiendo dos reglas simples:
- Si la casilla actual tiene un número n, es posible marcar como n+1 la casilla tres posiciones más arriba, a la izquierda, a la derecha o abajo si está libre.
- Si la casilla actual tiene un número n, es posible marcar como n+1 la casilla dos posiciones en diagonal a su nordeste, noroeste, sudeste o sudoeste si está libre.
El otro día estuve probando dos o tres veces y como no recordaba si tenía solución, dejé de intentarlo y probé a hacer un algoritmo que probase si encontraba alguna solución.
Se puede probar en este enlace de jsbin.
Aunque yo inicio el proceso a partir de la casilla 0 (la superior izquierda) y detengo el proceso cuando ha encontrado 20 soluciones (se trata de un proceso muy intensivo, especialmente para el navegador). Por ejemplo:
01-09-19-02-10 14-22-05-13-21 07-17-25-08-18 04-12-20-03-11 15-23-06-16-24
Y el código (simplificado):
function itera(board, pos, num) { if (salida>20) return; board[pos]= num++; if (num==26) return print_solution(board); if (board[pos+3]==null && pos%5<2) itera(board.slice(), pos+3, num); // comprueba horizontal +3 if (board[pos-3]==null && pos%5>2) itera(board.slice(), pos-3, num); // comprueba horizontal -3 if (board[pos-15]==null && pos>14) itera(board.slice(), pos-15, num); // comprueba vertical -15 if (board[pos+15]==null && pos<10) itera(board.slice(), pos+15, num); // comprueba vertical +15 if (board[pos-12]==null && pos%5>1 && pos>9) itera(board.slice(), pos-12, num); // comprueba diagonal NO -12 if (board[pos-8]==null && pos%5<3 && pos>9) itera(board.slice(), pos-8, num); // comprueba diagonal NE -8 if (board[pos+8]==null && pos%5>1 && pos<15) itera(board.slice(), pos+8, num); // comprueba diagonal SO +8 if (board[pos+12]==null && pos%5<3 && pos<15) itera(board.slice(), pos+12, num); // comprueba diagonal SE +12 } var board= []; for (var i=0; i<=24; i++) board[i]= null; // dim to 25 elements itera(board, 0, 1); // inicio proceso con tablero vacío y empezando en la casilla 0
0 comentarios:
Publicar un comentario