Foros del Web » Programación para mayores de 30 ;) » Programación General »

[SOLUCIONADO] Analisis Problema de las 8 reinas (Bactraking)

Estas en el tema de Analisis Problema de las 8 reinas (Bactraking) en el foro de Programación General en Foros del Web. Hola amigos tengo un pequeño problema con el algoritmo de las 8 reinas..... Código PHP: <?php function  ocho_reinas ( $pos ,  $solucion ,  $diagonal_desc ,  ...
  #1 (permalink)  
Antiguo 29/11/2012, 06:57
Avatar de YeisonSoto  
Fecha de Ingreso: enero-2011
Ubicación: Cali, Colombia, Colombia
Mensajes: 116
Antigüedad: 9 años, 3 meses
Puntos: 4
Analisis Problema de las 8 reinas (Bactraking)

Hola amigos tengo un pequeño problema con el algoritmo de las 8 reinas.....

Código PHP:
<?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);
            
        }
         
  }
}

$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



los datos que arroja son los mismos hasta cierto punto comparandolos con los que muestra la ejecucion del algoritmo...(filas-->valores, Columnas--> indices del array)

- 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???

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
  #2 (permalink)  
Antiguo 29/11/2012, 13:35
 
Fecha de Ingreso: enero-2008
Mensajes: 201
Antigüedad: 12 años, 4 meses
Puntos: 39
Respuesta: Analisis Problema de las 8 reinas (Bactraking)

Al salir de la llamada recursiva el for continúa por donde se quedo, si i=2 seguira por i=3.
  #3 (permalink)  
Antiguo 29/11/2012, 21:21
Avatar de YeisonSoto  
Fecha de Ingreso: enero-2011
Ubicación: Cali, Colombia, Colombia
Mensajes: 116
Antigüedad: 9 años, 3 meses
Puntos: 4
Respuesta: Analisis Problema de las 8 reinas (Bactraking)

Cita:
Iniciado por _Ruben_ Ver Mensaje
Al salir de la llamada recursiva el for continúa por donde se quedo, si i=2 seguira por i=3.
Gracias amigo, tienes razon al llamar el metodo recursivamente i vuelve a cero, y las iteraciones quedan almacenadas en memoria, eso es lo que entiendo, para despues de terminar la recursion retomar esos pendientesss...
  #4 (permalink)  
Antiguo 30/11/2012, 18:52
Avatar de YeisonSoto  
Fecha de Ingreso: enero-2011
Ubicación: Cali, Colombia, Colombia
Mensajes: 116
Antigüedad: 9 años, 3 meses
Puntos: 4
Busqueda Respuesta: Analisis Problema de las 8 reinas (Bactraking)

El funcionamiento del problema ya lo tengo claro.......Pero ahora me surge otra duda

- Alguein sabe como puedo medir la eficiencia de este algoritmo(Notacion asintotica)?

Agradezco la ayuda que me puedan dar......

Etiquetas: analisis
Atención: Estás leyendo un tema que no tiene actividad desde hace más de 6 MESES, te recomendamos abrir un Nuevo tema en lugar de responder al actual.
Respuesta




La zona horaria es GMT -6. Ahora son las 18:13.