Problème des 8 reines généralisé

Télécharger le projet
Commenter

Description

Ce code résoud le prob des huit reines d'une manière récursive, en utilisant deux 03 tableau
un pour marquer les colonnes, et les deux autres pour la diagonale gauche et droite.
Et ca en remarquant que les éléments de la diagonale gauche sont relié par la relation (ligne + colonne), et les éléments de la diagonale droite par la relation (N + (ligne - colonne)).

Source / Exemple : 


#include<dos.h>
#include<bios.h>
#include<stdlib.h>
#include<stdio.h>
#include<conio.h>
#include<graphics.h>
#define MAX_CASE 20

int vitesse = 1000;
int queen[(MAX_CASE-1)+1];
int col[(MAX_CASE-1)+1];
int dp[2*(MAX_CASE-1)+1];
int dn[2*(MAX_CASE-1)+1];
int n;
int nbr_sol;
int x = 10, y = 10;
char str[20];

void dessiner_reine(int, int);
void graphisme(int );
void placer(int);
void mettre(int, int);
void effacer(int, int);
int libre(int, int);
void dessiner(void);
void init(void);

int main()
{
clrscr();
printf("Entrez le nombre de reines:");
scanf("%d", &n);
init();
graphisme(n);
placer(n-1);
sprintf(str,"%d",nbr_sol);
outtextxy(x+n*30+10,y+n*30+10,str);
getch();
return 0;
}

void placer(int l)
{
   int c;
   for(c=0;c<n;c++)
      if(libre(l,c))
      { if(bioskey(2) == 27) exit(1);
	 mettre(l,c);
	 if(l==0) dessiner();
	 else placer(l-1);
	 effacer(l,c);
      }
}

void mettre(int l, int c)
{
   queen[l]=c;
   col[c]=-1;
   dp[l+c]=-1;
   dn[l-c+n-1]=-1;
}

void effacer(int l, int c)
{
   col[c]=0;
   dp[l+c]=0;
   dn[l-c+n-1]=0;
}

int libre(int l, int c)
{
   return((!col[c]) && (!dp[l+c]) && (!dn[l-c+n-1]));
}

void dessiner()
{
   int r;
   int c;
   nbr_sol++;
cleardevice();
graphisme(n);
for(r=n-1;r>=0;r--)
   {
      for(c=0;c<n;c++)
	 if(queen[r]==c){dessiner_reine(x+c*30, y +r*30);}
   }
delay(vitesse);
}

void init()
{
int grdriver=DETECT, grmode, err;

int i;
nbr_sol = 0;
for(i=0;i<n;i++) col[i]=0;
   for(i=0;i<2*n-2;i++) dp[i]=0, dn[i]=0;
initgraph(&grdriver, &grmode, "c:\\tc\\bgi");
}

void graphisme(int n)
{
setcolor(WHITE);
setfillstyle(SOLID_FILL, WHITE);

for(int i=0; i <= n; i++)
   line(x+i*30,y,x + i*30,y+n*30);
for(i=0; i <= n; i++)
    line(x, y+i*30, x+n*30, y+ i*30);
for(i=0; i<n; i=i+1)
   for(int j=i%2; j<n; j = j+2)
      floodfill(x+j*30+1, y+30*i+1,15);
}

void dessiner_reine(int x, int y)
{
setcolor(RED);
setfillstyle(SOLID_FILL, RED);
circle(x+16, y+16, 5);
floodfill(x+16,y+16,RED);
}
Télécharger le projet

Codes Sources

A voir également

S'inscrire maintenant

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.

Du même auteur (cs_Abdellah81)