Analisis Problema de las 8 reinas (Bactraking)

Responder
Mensaje
Autor
YeisonSoto
Mensajes: 2
Registrado: 28/11/2012 8:35 pm

Analisis Problema de las 8 reinas (Bactraking)

#1 Mensaje por YeisonSoto » 28/11/2012 8:38 pm

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

Código: Seleccionar todo

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


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


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


Espero que me puedan ayudar...

Gracias...

Avatar de Usuario
rir3760
Mensajes: 7553
Registrado: 01/10/2004 11:00 pm
Ubicación: Mexico

#2 Mensaje por rir3760 » 29/11/2012 7:45 am

Hola

Bienvenido a los foros. Por favor lee sus reglas, muevo el tema al foro apropiado: PHP.

Un saludo
C retains the basic philosophy that programmers know what they are doing; it only requires that they state their intentions explicitly.
--
Kernighan & Ritchie, The C programming language

YeisonSoto
Mensajes: 2
Registrado: 28/11/2012 8:35 pm

#3 Mensaje por YeisonSoto » 29/11/2012 8:34 am

rir3760 escribió:Hola

Bienvenido a los foros. Por favor lee sus reglas, muevo el tema al foro apropiado: PHP.

Un saludo
Gracias, lo tendré en cuenta....

manuel_venezuela
Mensajes: 41
Registrado: 02/03/2011 7:54 am
Ubicación: venezuela

Re: Analisis Problema de las 8 reinas (Bactraking)

#4 Mensaje por manuel_venezuela » 04/12/2012 12:49 pm

Código: Seleccionar todo

#include<stdio.h>
#include<math.h>

enum bool {FALSE,TRUE};
typedef enum bool boolean;
#define N 8


boolean buenSitio (int k,int x[]);
void colocarReinas(int k,int x[]);
void escribir(int x[]);
int main()
{
	int vector[N],i;

	for(i=1;i<=N;i++)
		vector[i]=0;

	colocarReinas(1,vector);
system("pause");
				
		//printf("%d\n",buenSitio(i,vector));
}

boolean buenSitio (int k,int x[])
{
	int i;boolean amenaza;
	i=1;
	amenaza=FALSE;

	while(i<k  && !amenaza)
	{
		if(x[i]==x[k]  || abs(x[i]-x[k])==abs(i-k))
			amenaza=TRUE;
		else
			i=i+1;

	
	}
	return !amenaza;

}

void colocarReinas(int k,int x[])
{

int i;
for(i=1;i<=N;i++){
		x[k]=i;

	if(buenSitio(k,x))
	{
		if(k==N)
			escribir(x);

		else
			colocarReinas(k+1,x);
		}

	}
}

void escribir(int x[])
{

	int i;

	for(i=1;i<=N;i++){
		
		printf("%d",x[i]);
		if(i==N)
		printf("\n");	
	}
}

manuel_venezuela
Mensajes: 41
Registrado: 02/03/2011 7:54 am
Ubicación: venezuela

Re: Analisis Problema de las 8 reinas (Bactraking)

#5 Mensaje por manuel_venezuela » 04/12/2012 12:50 pm

ese es el codigo en c...si de algo te sirve..
te desplegan todas las soluciones posibles...

Responder

¿Quién está conectado?

Usuarios navegando por este Foro: No hay usuarios registrados visitando el Foro y 1 invitado