Problema de las 8 Reinas para C#

Estado
Cerrado para nuevas respuestas

Thot

Nuevo Miembro
Miembro
#1
Por favor, si alguien puede ayudarme con el siguiente programa para aplicación de consola de C#:

Hacer un programa que imprima 8 reinas en un tablero de ajedrez, con la condición de que ninguna de ellas se amenace.

Cualquier ayuda se los voy a agredecer muchisimo.
 

rob1104

Super Moderador
Super Moderador
#2
Te dejo el algoritmo:
El problema de las ocho reinas
Continuamos con problemas relacionados con el ajedrez. El problema que ahora se plantea es claramente, como se verá, de vuelta atrás. Se recomienda intentar resolverlo a mano.
Se trata de colocar ocho reinas sobre un tablero de ajedrez, de tal forma que ninguna amenace (pueda comerse) a otra. Para los que no sepan ajedrez deben saber que una reina amenaza a otra pieza que esté en la misma columna, fila o cualquiera de las cuatro diagonales.
La dificultad que plantea este problema es la representación de los datos. Se puede utilizar un array bidimensional de tamaño 8x8, pero las operaciones para encontrar una reina que amenace a otra son algo engorrosas y hay un truco para evitarlas. La solución aquí expuesta vuelve a ser tomada de Wirth (ver Bibliografía).
Es lógico que cada reina debe ir en una fila distinta. Por tanto, en un array se guarda la posición de cada reina en la columna que se encuentre. Ejemplo: si en la tercera fila hay una reina situada en la quinta columna, entonces la tercera posición del array guardará un 5. A este array se le llamará col.
Hace falta otro array que determine si hay puesta una reina en la fila j-ésima. A este array se le llamará fila.
Por último se utilizan dos arrays más para determinar las diagonales libres, y se llamarán diagb y diagc.
Para poner una reina se utiliza esta instrucción:
Insertar CODE, HTML o PHP:
col[i] = j ; fila[j] = diagb[i+j] = diagc[7+i-j] = FALSE;
Para quitar una reina esta otra:
Insertar CODE, HTML o PHP:
fila[j] = diagb[i+j] = diagc[7+i-j] = TRUE;
Se considera válida la posición para este caso:
Insertar CODE, HTML o PHP:
if (fila[j] && diagb[i+j] && diagc[7+i-j])
entonces proceder ...
A continuación se expone el código completo en C. Se han utilizado tipos enumerados para representar los valores booleanos.
Insertar CODE, HTML o PHP:
#include <stdio.h>

enum bool {FALSE, TRUE};
typedef enum bool boolean;

void ensayar(int i, boolean *q, int col[], boolean fila[], boolean diagb[], boolean diagc[]);

int main(void)
{
  int i;
  boolean q;

  int col[8];
  boolean fila[8],diagb[15], diagc[15];

  for (i = 0; i < 8; i++) fila[i] = TRUE;
  for (i = 0; i < 15; i++) diagb[i] = diagc[i] = TRUE;

  ensayar(0,&q,col,fila,diagb,diagc);
  if (q) {
    printf("\nSolucion:");
    for (i = 0; i < 8; i++) printf(" %d", col[i]);
  } else printf("\nNo hay solucion");

  return 0;
}

void ensayar(int i, boolean *q, int col[], boolean fila[], boolean diagb[], boolean diagc[])
{
  int j;

  j = 0;
  *q = FALSE;
  do {
    if (fila[j] && diagb[i+j] && diagc[7+i-j]) {
      col[i] = j; fila[j] = diagb[i+j] = diagc[7+i-j] = FALSE;
      if (i < 7) { /* encuentra solucion? */
        ensayar(i+1,q,col,fila,diagb,diagc);
        if (!*q)
          fila[j] = diagb[i+j] = diagc[7+i-j] = TRUE;
      } else *q = TRUE; /* encuentra la solucion */
    }
    j++;
  } while (!*q && j < 8);
}
Por último, se deja al lector que implemente un procedimiento que encuentre todas las soluciones. Si se desea complicar más entonces se puede pedir que encuentre todas las soluciones distintas, es decir, aquellas que no sean rotaciones o inversiones de otras soluciones.
Ahora que se conoce el método general, puede hacerse extensible a múltiples piezas simultáneamente.
Ya te toca a ti implementarlo en C#

Saludos
 
Estado
Cerrado para nuevas respuestas
Arriba Pie