Eleazan Source

8 reinas en PHP

Ya sé.. hace tiempo (mucho) que no actualizo el blog. Pero hoy me ha dado por hacerlo

Resulta, que hoy, me han propuesto por ahí, hacer el algoritmo de las 8 reinas en php. Y me ha picado el gusanillo, y lo he hecho. En realidad, dudo q sea difícil encontrar el algoritmo por ahí, pero, ¡prometo que no lo he buscado!

Primero, ante todo.. ¿en que consiste eso de 8 reinas? Bueno, es un simple problema, en el que te plantea, en un tablero de ajedrez (8x8), colocar 8 reinas sin que se amenacen entre ellas. Básicamente, una reina amenaza en 4 direcciones

·

· La fila

· La columna

· La diagonal descendente

· La diagonal ascendente

Teniendo en cuenta esto,  el planteamiento seria el siguiente:

El tablero constará de 8 columnas (del 0 al 7) y 8 filas (del 0 al 7). Debido a que no pueden coincidir dos reinas en la misma columna, nos proporciona una ventaja para plantearlo. Podemos crear un vector (array) $solucion, en el que las claves (del 0 al 7) sean las columnas, y así podemos guardar la fila en el valor de la columna, generando un sistema de coordenadas sencillo. Es decir, si tengo que solucion es (6,4,2,0,5,7,1,3) (que es una de las 92 posibles soluciones) significará que en la columna 0, fila 6, tendré una reina, en 1,4 otra... etc.

Una vez aclarado esto, sólo recalcar que, lo que me ha costado ha sido, encontrar la forma de comprobar la diagonal. Al final, me he dado cuenta de que las diagonales descendentes, si haces columna - fila, siempre te va a dar el mismo resultado (único para cada diagonal) y en las ascendentes, columna + fila. Así pues, usaremos dos vectores más (diagonal_descendente y diagonal_ascendente) y en ellos, guardaremos, el la columna correspondiente, el valor de la diagonal que ocupan.

Ahora, para plantear la función, tendremos en cuenta que necesitaremos saber en que posición nos encontramos, para poder dar por finalizada esa rama (puesto que seguiremos buscando soluciones!), y llevar un pequeño control. Básicamente, pasaremos 4 parámetros: La columna/posicion, el vector de solucion, vector de diagonal descendente, y vector de diagonal ascendente. Primero comprobaremos que no hemos llenado el vector de solucion (en caso de q lo hayamos llenado, ya tenemos una solucion!). Si no está lleno, comprobamos que no la amenaze ninguna reina (es decir, no existe, dentro de solucion, ningun valor igual que el suyo, ni dentro de diagonal_descendente ningun valor de su diagonal descendente, ni dentro de diagonal ascendente ningun valor de su diagonal ascendente). En caso de que no exista en ningun vector previo, estaremos ante una posicion potencialmente válida, asiq, la guardamos en el vector, y procedemos a llamar a la funcion para columna+1. Vamos, backtracking.

Ale, sin enrollarme más, paso a escribir el código:

<?php

function ocho_reinas($pos, $solucion, $diag_descendente, $diag_ascendente) {

 if($pos > 7) //Se han encontrado 8 elementos, es válido!
 echo print_solucion($solucion);

 else {
     //Aun no estamos en la última posicion, buscamos una válida!
     for ($i = 0; $i < 8; $i++) { //Recorremos las filas
         if(!in_array($i, $solucion) AND !in_array(($pos-$i), $diag_descendente) AND !in_array(($pos+$i), $diag_ascendente)) {
             //Esta casilla no está amenazada!
             $diag_ascendente[$pos] = $pos+$i; //Guardamos el valor de la diagonal ascendente
             $diag_descendente[$pos] = $pos-$i; //Guardamos el valor de la diagonal descendente
             $solucion[$pos] = $i;
             ocho_reinas($pos+1, $solucion, $diag_descendente, $diag_ascendente);
        }

     }
  }

}

function print_solucion($solucion) {

 $ns = array_flip($solucion);
 ksort($ns);

 echo '<table border=1>';
 foreach ($ns as $fila => $columna) {
     echo '<tr>';

     for ($i=0; $i<8; $i++) {
         echo '<td width="15px" height="15px">';
         if($i == $columna) echo '*';
         echo '</td>';
     }
     echo '</tr>';
 }
 echo '</table><br>';

}

Esa sería la función principal (junto con la de imprimir un tablero en html!), y para llamarla se haría algo así:

<?php

$pos = 0; //Posicion inicial: 0;
$solucion = Array();
$diag_descendente = Array();
$diag_ascendente = Array();

ocho_reinas($pos, $solucion, $diag_descendente, $diag_ascendente);

?>

Y como resultado, tendríais algo así:

*
						*
				*
							*
	*
			*
					*
		*

Y eso es todo