FELIPE
09 de Diciembre del 2003

programa k acomoda 8 reinas en un tablero de ajedrez, la primera acomodada por el usuario, agradesco k me ayuden por k es el trabajo final y le he hechao cabeza y no me sale.

Ari
09 de Diciembre del 2003

Por favor, si lla tienes la respuesta de las 8 reinas enviamelas, te lo agradecere mucho, porque tambienes mi travajo final y tengo que entregarlo hoy mismo.

josuth
09 de Diciembre del 2003

Hola

Hace tiempo tuve que implementar el mismo problema, perdí el código pero la idea es la siguiente:

Fijate que para que dos reinas no se amenacen no pueden estar en la misma fila/columna, es decir en cada columna sólo puede haber una reina. Eso nos lleva a que puede representarse el tablero como un array de 8 casillas (no hace falta una matriz 8x8), cada casilla representa una columna y el valor de cada casilla va de 1 a 8 que representa la fila.

Con esta estructura cada casilla contendrá el número de la fila donde se situa la reina de esa columna.

Lo que tienes que hacer es generar todos los valores posibles de manera que no se amenacen diagonalmente. Fijate también que puedes desechar combinaciones, pues el array no puede tener dos casillas con el mismo valor, porque eso significaría que están en la misma fila.

Es un problema de ramificación y poda típico. Puedes buscar en libros de algoritmia porque es fácil que lo encuentres resuelto, aunque sea en seudocódigo.

Espero haberte ayudado, un saludo

kecambas
09 de Diciembre del 2003

#include <stdio.h> /* printf () */
#include <conio.h> /* getch () */

/* Macros: */

#define BOOLEAN int
#define TRUE 1
#define FALSE 0

/* Variables globales: */

BOOLEAN acertado;

int posiciones_en_columna[8];
BOOLEAN reina_en_fila[8];
BOOLEAN reina_en_diagonal_normal[15];
BOOLEAN reina_en_diagonal_inversa[15];

#define c(i) posiciones_en_columna[(i)-1]
/* rango de índice: 1..8 */
#define f(i) reina_en_fila[(i)-1]
/* rango de índice: 1..8 */
#define dn(i) reina_en_diagonal_normal[(i)+7]
/* rango de índice: -7..7 */
#define di(i) reina_en_diagonal_inversa[(i)-2]
/* rango de índice: 2..16 */

/* Prototipos de las funciones: */

void proceso (void);
void ensayar (int i);

/* Definiciones de las funciones: */

void main (void)
{
clrscr();
printf ("nnPROBLEMA DE LAS OCHO REINAS:n ");
proceso ();
printf ("nnPulsa cualquier tecla para finalizar. ");
getch ();
}

void proceso (void)
{
register int i,j;

for (i = 1; i <= 8; i++)
f (i) = TRUE;
for (i = 2; i <= 16; i++)
di (i) = TRUE;
for (i = -7; i <= 7; i++)
dn (i) = TRUE;

ensayar (1);

if (acertado)
for (printf ("nnLA SOLUCION ES:nn"), i = 1; i <= 8; i++)
{
for (j = 1; j <= 8; j++)
printf ("%2d", c (j) == i ? 1 : 0);
printf ("n");
}
else
printf ("nnNO HAY SOLUCION.n");
}

void ensayar (int i)
{
int j = 0;

do
{
j++;
acertado = FALSE;
if (f (j) && di (i + j) && dn (i - j))
{
c (i) = j;
f (j) = di (i + j) = dn (i - j) = FALSE;
if (i < 8)
{
ensayar (i + 1);
if (! acertado)
f (j) = di (i + j) = dn (i - j) = TRUE;
}
else
acertado = TRUE;
}
} while (! acertado && j != 8);
}