Necesito poner 8 reinas en un tablero de ajedrez en C
Joselyn
15 de Noviembre del 2004
Hola , le cuento q soy nueva y necesito con urgencia ayuda : tengo q hacer un programa en C , consiste en poner 8 reinas en una tablero de ajedrez sin q ninguna se mate, uno tiene q ingresar la primera posicion de la primera reina por ejemplo en la posicion (3,5). De antemano muchas gracias y espero me puedan ayudar.
Ricardo
15 de Noviembre del 2004
Pucha, si que estamos de mala suerte, esa solucion salio publicada en una revista de los 80s ZX Spectrum y en Basic, como la tenia en fotocopias, hace ya años la pase a C, el programa tiene un algoritmo que no entiendo. Bueno lastima, perdi el fuente, tengo solo el ejecutable, y la fotocopia esta en Lima, ahora estoy en Chile y si tiene mas de un mes para esperar te lo envio, aunque sea para satisfacer la curiosidad, pero eso si, debes de scribirme para hacerme acordar
other
15 de Noviembre del 2004
Se trata de un programa clásico de algorítmica.
Depende de con la eficiencia con la que quieras resolverlo tendrás que hacer unas u otras podas.
La idea es hacer "backtracking", es decir, prueba y error.
Haz esto:
-Una matríz de 8x8 de booleanos (1 hay reina, 0 no hay reina)
-Una función que compruebe si una reina está en una posición incorrecta (pasas la matriz y la posición y comprueba que no ataca/está siendo atacada... es facil.
-Una función recursiva que reciba varios parametros... seria algo así.
bool funcion(int colocadas, bool matriz[8][8], int fila)
{
if (colocadas=8)
return 1;
if(fila>=8 )
fila=0
for (int i =0; i<8;i++)
if (!atacada(matriz,fila,i) )
{
matriz[fila][i]=1;
if(funcion(colocadas+1,matriz,fila+1))
return 1 ;
matriz[fila][i]=0;
}
return 0;
}
Esto lo acabo de hacer ahora mismo. Es un poco dificil de ver al principio. La idea es que si puede colocar una reina en un sitio, la coloca y se llama a si misma. Si el resultado es 1 (la siguiente función y sicesivas pudieron colocarla) entonces todo está terminado, si es 0 (no se peude colocar desde esa posición) cambia la reina de sitio (a la siguiente casilla) y vuelve a intentarlo. Si no puede colocar en ninguna de las 8 casillas de la fila, entonces devuelve 0 para que el que la yamó haga los cambios pertinentes.
Si tienes cualquier duda, contacta con [email protected]
Depende de con la eficiencia con la que quieras resolverlo tendrás que hacer unas u otras podas.
La idea es hacer "backtracking", es decir, prueba y error.
Haz esto:
-Una matríz de 8x8 de booleanos (1 hay reina, 0 no hay reina)
-Una función que compruebe si una reina está en una posición incorrecta (pasas la matriz y la posición y comprueba que no ataca/está siendo atacada... es facil.
-Una función recursiva que reciba varios parametros... seria algo así.
bool funcion(int colocadas, bool matriz[8][8], int fila)
{
if (colocadas=8)
return 1;
if(fila>=8 )
fila=0
for (int i =0; i<8;i++)
if (!atacada(matriz,fila,i) )
{
matriz[fila][i]=1;
if(funcion(colocadas+1,matriz,fila+1))
return 1 ;
matriz[fila][i]=0;
}
return 0;
}
Esto lo acabo de hacer ahora mismo. Es un poco dificil de ver al principio. La idea es que si puede colocar una reina en un sitio, la coloca y se llama a si misma. Si el resultado es 1 (la siguiente función y sicesivas pudieron colocarla) entonces todo está terminado, si es 0 (no se peude colocar desde esa posición) cambia la reina de sitio (a la siguiente casilla) y vuelve a intentarlo. Si no puede colocar en ninguna de las 8 casillas de la fila, entonces devuelve 0 para que el que la yamó haga los cambios pertinentes.
Si tienes cualquier duda, contacta con [email protected]
pau
15 de Noviembre del 2004
Hola a todos, la solucion al problesma de las 8 reinas en un tablero esta en la siguiente direccion:
http://ima.udg.es/Docencia/03-04/3105IG0003/index.html
a l'apartat d'exercicis
espero que us serveixi.
http://ima.udg.es/Docencia/03-04/3105IG0003/index.html
a l'apartat d'exercicis
espero que us serveixi.
Roberto Martel
15 de Noviembre del 2004
Por favor Ricardo ayudame con este programa estoy en 3 curso de colegio y necesito presentar este proyecto para poder dar el examen final, por favor ayudame en eso
juan sebastian
15 de Noviembre del 2004
joselyn te cuento que estoy en el mismo ejercicio y aun no lo he podido resolver, te agradeceria que si ya te enviaron la respuesta me la devolvieras a mi correo
[email protected]
mil gracias
[email protected]
mil gracias
Andres Felipe Sanchez Quintero
15 de Noviembre del 2004
Si no te sirve escriveme que cualquier cosa yo te ayudo ok
#include <stdio.h> //printf()
#include <conio.h> //getch(), Gotoxy()
#include <iostream.h> //cout
#include <graphics.h>
#include <DOS.h> //adornos
#define boolean int
#define TRUE 1
#define FALSE 0
int c,f;//coordenadas de primera reina
void ventana(int t);//declaracion de funcion de ventana de avisos
boolean q;//resultado de operacion
void Board()
{
int dis,mod,error;//variables detectar grafico
int x,a,b,y;
detectgraph(&dis,&mod);//Detecta grafico
initgraph(&dis,&mod,"(**):\TC\bgi"); //Directorio de graficos
error = graphresult();//Si sale algun error lo imprime en pantalla
if(error)
{printf("%s",grapherrormsg(error));}//Imprime el error
ventana(1);//llama a ventana de mensajes al usuario
rectangle(1,1,639,479); // 1rentangulo de pantalla
rectangle(3,3,637,477); // 2rectangulo de pantalla
for(a=1,x=0;a<5;a++){ // dibuja la cuadricula chesboard
x=40+x;
y=x+40;
setfillstyle(1,8); // stilo al relleno de los cuadro
bar(70,x,110,y);
bar(150,x,190,y); // Solo pinta cuadros blanco, para que los
bar(230,x,270,y); // negro si ya estan por el fondo de la pantalla
bar(310,x,350,y);
x=x+40; //
y=x+40; //
bar(30,x,70,y); //
bar(110,x,150,y); //
bar(190,x,230,y); //
bar(270,x,310,y); //
}
rectangle(30,40,350,360); //cuadro del ajedrez
setcolor(8);//color para columna y filas
outtextxy(45,30,"0");outtextxy(20,55,"0");
outtextxy(85,30,"1");outtextxy(20,95,"1");
outtextxy(125,30,"2");outtextxy(20,135,"2"); //numeros de columnas y filas
outtextxy(170,30,"3");outtextxy(20,180,"3");
outtextxy(210,30,"4");outtextxy(20,215,"4");
outtextxy(250,30,"5");outtextxy(20,255,"5");
outtextxy(290,30,"6");outtextxy(20,295,"6");
outtextxy(327,30,"7");outtextxy(20,335,"7");
setcolor(15);//restablecer color a blanco para lo demas
rectangle(400,40,600,360);//cuadro de soluciones
line(400,80,600,80);//Linea de soluciones
outtextxy(435,58,"S O L U C I O N");
outtextxy(430,90,"Columna");
outtextxy(530,90,"Fila");
}
void ventana(int t)//ventana de mensajes
{
setfillstyle(1,7);//estilo para fondo de ventana
bar3d(180,290,400,190,2,1);//dibuja cuadro de ventana
setfillstyle(1,2);//estilo para fondo de titulo
bar(180,205,400,190);//dibuja cuadro de titulo
outtextxy(260,193,"A V I S O");//Texto de titulo
if(t==1){//condicion para el tipo de aviso 1:preguntas 2: No hay solucion
setcolor(6);
outtextxy(220,80,"B I E N V E N I D O S");
setcolor(4);
outtextxy(290,110,"A L");
setcolor(1);
outtextxy(130,140,"P R O B L E M A D E L A S 8 R E I N A S");
setcolor(15);
outtextxy(40,350,"Andres Felipe Sanchez Q");
outtextxy(400,350,"Karen Eliana Botero O");
gotoxy(30,16);cout<<"DIGITE FILA: ";//pregunta fila
cin>>f;//recoje dato de fila
gotoxy(30,16);cout<<"DIGITE COLUMNA: ";//pregunta columna
cin>>c;//recoje dato de columna
cleardevice();//limpia pantalla
}else{setcolor(BLUE);//no hay solucion, y cambio color de texto
outtextxy(230,240,"> NO HAY SOLUCION <");}//texto
if(f>7 || c>7){ventana(1);}//condicion para prevenir error de digitacion
}
void dibujar(int x,int y) //fichas
{
if(x==c){
setfillstyle(1,6); // estilo al relleno del cuadro reina Digitada
bar((x*40)+30,(y*40)+40,(x*40)+70,(y*40)+80);}//Pone el cuadro
setfillstyle(SOLID_FILL, LIGHTBLUE); //color de fichas
pieslice((x*40)+50,(y*40)+60,2,360,10); //poner Base fichas
setfillstyle(SOLID_FILL, YELLOW);
pieslice((x*40)+50,(y*40)+60,2,360,5);
gotoxy(68,(x*2)+8);cout<<y;//Inserta el numero de Fila
gotoxy(58,(x*2)+8);cout<<x;//inserta el numero de Columna
setcolor(2);//Color al Texto Verde
outtextxy(200,400,"Acomodando Reinas.......");//Inserta Texto
sound(200);delay(100);nosound();delay(400); //retardo y sonido
setcolor(0);//Color al Texto Negro
outtextxy(200,400,"Acomodando Reinas.......");//Si lo ponemos lo quitamos por el color
}
void buscar(int i,int col[], boolean fila[], boolean dgn[], boolean dgi[])
{
int j;
j = 0;//indice de fila
q = FALSE;//variable de respuesta
do {//bucle
if(i!=c){//condicion para la columna en que esta digitada la reina
if (fila[j] && dgn[i+j] && dgi[7+i-j]) {//validacion si no hay nada en fila,y diagonales
col[i] = j; fila[j] = dgn[i+j] = dgi[7+i-j] = FALSE;//pone la reina
if (i<7) { //Dice que no hay nada en ese columna
buscar(i+1,col,fila,dgn,dgi);//Recursividad o pasa a otra columna
if (!q)//anterior no cuadra
fila[j] = dgn[i+j] = dgi[7+i-j] = TRUE;//borrar reina
} else q = TRUE; /* encuentra la solucion */ }
}else buscar(i+1,col,fila,dgn,dgi);//Pasa a otra columna
j++;//contador
} while (!q && j<8);//condicion
}
int main(void)//principal
{
int i;//contador
char e;//Variable para preguntar salida
int col[8];//Columna
boolean fila[8],dgn[15], dgi[15];//Filas, Diagonal Normal e inversa
for (i = 0; i < 8; i++) fila[i] = TRUE;//Blanquea todas las filas
for (i = 0; i < 15; i++) dgn[i] = dgi[i] = TRUE;//blanquea diagonales
Board(); //hacer el tablero
col[c] = f; fila[f] = dgn[c+f] = dgi[7+c-f] = FALSE;//inserte la reina digitada
buscar(0,col,fila,dgn,dgi); //la busqueda
if(q){//condicion para sabar si hay posiciones
for (i = 0; i < 8; i++){//envia coordenadas para dibujar fichas
dibujar(i,col[i]);}//envia coordenadas para dibujar fichas
}else {ventana(2);}//llama a ventana de mensajes para usuarios
setcolor(5);//Color al Texto
//gotoxy(10,28);cout<<"Desea Salir (s/n)"<<flush;//Desea seguir
//gotoxy(28,28);cin>>e;//Coje la respuesta
outtextxy(100,400,"Para repetir precione S, Para Salir precione Cualquier tecla");
e = getch();//toma el valor de la tecla pulsada anteriormente
if(e=='s',e=='S'){main();}//si es no vuelve a ejecutar elprograma haciendo con main
closegraph();//cerrar grafico
return 0;
}
#include <stdio.h> //printf()
#include <conio.h> //getch(), Gotoxy()
#include <iostream.h> //cout
#include <graphics.h>
#include <DOS.h> //adornos
#define boolean int
#define TRUE 1
#define FALSE 0
int c,f;//coordenadas de primera reina
void ventana(int t);//declaracion de funcion de ventana de avisos
boolean q;//resultado de operacion
void Board()
{
int dis,mod,error;//variables detectar grafico
int x,a,b,y;
detectgraph(&dis,&mod);//Detecta grafico
initgraph(&dis,&mod,"(**):\TC\bgi"); //Directorio de graficos
error = graphresult();//Si sale algun error lo imprime en pantalla
if(error)
{printf("%s",grapherrormsg(error));}//Imprime el error
ventana(1);//llama a ventana de mensajes al usuario
rectangle(1,1,639,479); // 1rentangulo de pantalla
rectangle(3,3,637,477); // 2rectangulo de pantalla
for(a=1,x=0;a<5;a++){ // dibuja la cuadricula chesboard
x=40+x;
y=x+40;
setfillstyle(1,8); // stilo al relleno de los cuadro
bar(70,x,110,y);
bar(150,x,190,y); // Solo pinta cuadros blanco, para que los
bar(230,x,270,y); // negro si ya estan por el fondo de la pantalla
bar(310,x,350,y);
x=x+40; //
y=x+40; //
bar(30,x,70,y); //
bar(110,x,150,y); //
bar(190,x,230,y); //
bar(270,x,310,y); //
}
rectangle(30,40,350,360); //cuadro del ajedrez
setcolor(8);//color para columna y filas
outtextxy(45,30,"0");outtextxy(20,55,"0");
outtextxy(85,30,"1");outtextxy(20,95,"1");
outtextxy(125,30,"2");outtextxy(20,135,"2"); //numeros de columnas y filas
outtextxy(170,30,"3");outtextxy(20,180,"3");
outtextxy(210,30,"4");outtextxy(20,215,"4");
outtextxy(250,30,"5");outtextxy(20,255,"5");
outtextxy(290,30,"6");outtextxy(20,295,"6");
outtextxy(327,30,"7");outtextxy(20,335,"7");
setcolor(15);//restablecer color a blanco para lo demas
rectangle(400,40,600,360);//cuadro de soluciones
line(400,80,600,80);//Linea de soluciones
outtextxy(435,58,"S O L U C I O N");
outtextxy(430,90,"Columna");
outtextxy(530,90,"Fila");
}
void ventana(int t)//ventana de mensajes
{
setfillstyle(1,7);//estilo para fondo de ventana
bar3d(180,290,400,190,2,1);//dibuja cuadro de ventana
setfillstyle(1,2);//estilo para fondo de titulo
bar(180,205,400,190);//dibuja cuadro de titulo
outtextxy(260,193,"A V I S O");//Texto de titulo
if(t==1){//condicion para el tipo de aviso 1:preguntas 2: No hay solucion
setcolor(6);
outtextxy(220,80,"B I E N V E N I D O S");
setcolor(4);
outtextxy(290,110,"A L");
setcolor(1);
outtextxy(130,140,"P R O B L E M A D E L A S 8 R E I N A S");
setcolor(15);
outtextxy(40,350,"Andres Felipe Sanchez Q");
outtextxy(400,350,"Karen Eliana Botero O");
gotoxy(30,16);cout<<"DIGITE FILA: ";//pregunta fila
cin>>f;//recoje dato de fila
gotoxy(30,16);cout<<"DIGITE COLUMNA: ";//pregunta columna
cin>>c;//recoje dato de columna
cleardevice();//limpia pantalla
}else{setcolor(BLUE);//no hay solucion, y cambio color de texto
outtextxy(230,240,"> NO HAY SOLUCION <");}//texto
if(f>7 || c>7){ventana(1);}//condicion para prevenir error de digitacion
}
void dibujar(int x,int y) //fichas
{
if(x==c){
setfillstyle(1,6); // estilo al relleno del cuadro reina Digitada
bar((x*40)+30,(y*40)+40,(x*40)+70,(y*40)+80);}//Pone el cuadro
setfillstyle(SOLID_FILL, LIGHTBLUE); //color de fichas
pieslice((x*40)+50,(y*40)+60,2,360,10); //poner Base fichas
setfillstyle(SOLID_FILL, YELLOW);
pieslice((x*40)+50,(y*40)+60,2,360,5);
gotoxy(68,(x*2)+8);cout<<y;//Inserta el numero de Fila
gotoxy(58,(x*2)+8);cout<<x;//inserta el numero de Columna
setcolor(2);//Color al Texto Verde
outtextxy(200,400,"Acomodando Reinas.......");//Inserta Texto
sound(200);delay(100);nosound();delay(400); //retardo y sonido
setcolor(0);//Color al Texto Negro
outtextxy(200,400,"Acomodando Reinas.......");//Si lo ponemos lo quitamos por el color
}
void buscar(int i,int col[], boolean fila[], boolean dgn[], boolean dgi[])
{
int j;
j = 0;//indice de fila
q = FALSE;//variable de respuesta
do {//bucle
if(i!=c){//condicion para la columna en que esta digitada la reina
if (fila[j] && dgn[i+j] && dgi[7+i-j]) {//validacion si no hay nada en fila,y diagonales
col[i] = j; fila[j] = dgn[i+j] = dgi[7+i-j] = FALSE;//pone la reina
if (i<7) { //Dice que no hay nada en ese columna
buscar(i+1,col,fila,dgn,dgi);//Recursividad o pasa a otra columna
if (!q)//anterior no cuadra
fila[j] = dgn[i+j] = dgi[7+i-j] = TRUE;//borrar reina
} else q = TRUE; /* encuentra la solucion */ }
}else buscar(i+1,col,fila,dgn,dgi);//Pasa a otra columna
j++;//contador
} while (!q && j<8);//condicion
}
int main(void)//principal
{
int i;//contador
char e;//Variable para preguntar salida
int col[8];//Columna
boolean fila[8],dgn[15], dgi[15];//Filas, Diagonal Normal e inversa
for (i = 0; i < 8; i++) fila[i] = TRUE;//Blanquea todas las filas
for (i = 0; i < 15; i++) dgn[i] = dgi[i] = TRUE;//blanquea diagonales
Board(); //hacer el tablero
col[c] = f; fila[f] = dgn[c+f] = dgi[7+c-f] = FALSE;//inserte la reina digitada
buscar(0,col,fila,dgn,dgi); //la busqueda
if(q){//condicion para sabar si hay posiciones
for (i = 0; i < 8; i++){//envia coordenadas para dibujar fichas
dibujar(i,col[i]);}//envia coordenadas para dibujar fichas
}else {ventana(2);}//llama a ventana de mensajes para usuarios
setcolor(5);//Color al Texto
//gotoxy(10,28);cout<<"Desea Salir (s/n)"<<flush;//Desea seguir
//gotoxy(28,28);cin>>e;//Coje la respuesta
outtextxy(100,400,"Para repetir precione S, Para Salir precione Cualquier tecla");
e = getch();//toma el valor de la tecla pulsada anteriormente
if(e=='s',e=='S'){main();}//si es no vuelve a ejecutar elprograma haciendo con main
closegraph();//cerrar grafico
return 0;
}