Algoritmia - Analisis Problema de las 8 reinas (Backtracking)

   
Vista:

Analisis Problema de las 8 reinas (Backtracking)

Publicado por Yeison Soto yeison.soto@hotmail.es (1 intervención) el 29/11/2012 04:56:44
Hola amigos tengo un pequeño problema con el algoritmo de las 8 reinas.....


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
<?php
 
function ocho_reinas($pos, $solucion, $diagonal_desc, $diagonal_asc) {
 
 if($pos > 7){ //Validación para saber si ha terminado de recorrer todas las posibles soluciones.
 
 echo "{";
	 foreach($solucion as $i =>$j ){ //Recorre el Array de soluciones para mostrarlas.
 
	 echo "".$j.",";
 
		 if($i==7){
		 echo "}";
			echo "<br>";
		 }
	 }
}
 else {
 
     for ($i = 0; $i < 8; $i++) { //Recorremos las filas
 
 
         if(!in_array($i, $solucion) AND !in_array(($pos+$i), $diagonal_asc) AND !in_array(($pos-$i), $diagonal_desc) ) {
		 //Entra , si esa casilla no está amenazada!
 
 
             $diagonal_asc[$pos] = $pos+$i; //diagonal ascendente.
             $diagonal_desc[$pos] = $pos-$i; //diagonal descendente.
 
             $solucion[$pos] = $i;	//Se guarda una posición valida.
 
 
	    ocho_reinas($pos+1, $solucion, $diagonal_desc, $diagonal_asc);
 
        }
 
		echo "<br>i f ".$i,"<br>";
     }
 
  }
}
 
 
 
$pos = 0; //Posicion inicial
 
$solucion = Array();//posibles soluciones.
$diagonal_desc = Array();//diagonales descendentes 
$diagonal_asc = Array();//diagonales ascendentes .
 
 
ocho_reinas($pos, $solucion, $diagonal_desc, $diagonal_asc);//Se llama al metodo de la lógica de las reinas.
 
 
 
?>



He hecho la prueba de escritorio



y los datos que arroja son los mismos hasta cierto punto que muestra la ejecucion del algoritmo...

- Tengo una duda, como funciona el la parte recursiva del lagortmo?, es decir c por ejemplo cuando la i del for va en 1 y se cumple la condicion if(!in_array($i, $solucion)....), al llamar mi metodo recursivamente, el for continua con su ietraccion normalmente? es decir sigue con i =2, i=3... y asi sucesivante, o vuelve a iniciar en 0???

-Donde se aplica el abctrakin en este algoritmo?

espero que me puedan ayudar...

Gracias...

Algortimo http://squadronsuicida.99k.org/Reinas/Reinas.php.
Descarga http://squadronsuicida.99k.org/Reinas/Reinas.txt
Prueba http://squadronsuicida.99k.org/Reinas/Reinas_Prueba.php.
Descarga http://squadronsuicida.99k.org/Reinas/Reinas_Prueba.txt
Valora esta pregunta
Me gusta: Está pregunta es útil y esta claraNo me gusta: Está pregunta no esta clara o no es útil
0
Responder