29 enero, 2009

Cinco por cinco

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:

  1. 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.
  2. 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

Publicar un comentario en la entrada

Últimos links en indiza.com