| Ver tema anterior :: Ver siguiente tema | | Autor | Mensaje |
|---|
YeisonSoto
Registrado: 28 Nov 2012
Mensajes: 2
|  Publicado: 28/11/2012 8:38 pm | | | Título: Analisis Problema de las 8 reinas (Bactraking) |
| Hola amigos tengo un pequeño problema con el algoritmo de las 8 reinas.....
| Código: | <?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???
Algortimo .
Descarga
Prueba .
Descarga
Espero que me puedan ayudar...
Gracias... |
| | Volver arriba | |  | rir3760
Registrado: 01 Oct 2004
Mensajes: 7517
Ubicación: Mexico
| | Publicado: 29/11/2012 7:45 am | | | Título: |
| 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 |
| | Volver arriba | | | YeisonSoto
Registrado: 28 Nov 2012
Mensajes: 2
| | Publicado: 29/11/2012 8:34 am | | | Título: |
| | 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.... |
| | Volver arriba | | | | manuel_venezuela
Registrado: 02 Mar 2011
Mensajes: 41
Ubicación: venezuela
| | Publicado: 04/12/2012 12:49 pm | | | Título: Re: Analisis Problema de las 8 reinas (Bactraking) |
| | Código: |
#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");
}
}
|
|
| | Volver arriba | | | manuel_venezuela
Registrado: 02 Mar 2011
Mensajes: 41
Ubicación: venezuela
| | Publicado: 04/12/2012 12:50 pm | | | Título: Re: Analisis Problema de las 8 reinas (Bactraking) |
| ese es el codigo en c...si de algo te sirve..
te desplegan todas las soluciones posibles... |
| | Volver arriba | | | | |
| No puede crear mensajes
No puede responder temas
No puede editar sus mensajes
No puede borrar sus mensajes
No puede votar en encuestas
|
|
| |
F.A.Q.
Conéctese para revisar sus mensajes