Problème de n dames
Contenu du snippet
programme qui resout le problème de n dame.
/*** probléme de n-dames ***/
/*** crée par blackbird ***/
//Le but du problème des n dames (parfois appelé à tort problème
//des huit reines), est de placer huit dames d'un jeu
//d'échecs sur un échiquier de n×n cases
//sans que les dames ne puissent se menacer mutuellement, conformément
//aux règles du jeu d'échecs (la couleur des pièces étant ignorée.)
//Par conséquent, deux dames ne devraient
//jamais partager la même rangée, colonne, ou diagonale
/*******************************************************************/
- /
/*** probléme de n-dames ***/
/*** crée par blackbird ***/
//Le but du problème des n dames (parfois appelé à tort problème
//des huit reines), est de placer huit dames d'un jeu
//d'échecs sur un échiquier de n×n cases
//sans que les dames ne puissent se menacer mutuellement, conformément
//aux règles du jeu d'échecs (la couleur des pièces étant ignorée.)
//Par conséquent, deux dames ne devraient
//jamais partager la même rangée, colonne, ou diagonale
/*******************************************************************/
Source / Exemple :
/*******************************************************************/
/*** probléme de n-dames ***/
/*** crée par blackbird ***/
//Le but du problème des n dames (parfois appelé à tort problème
//des huit reines), est de placer huit dames d'un jeu
//d'échecs sur un échiquier de n×n cases
//sans que les dames ne puissent se menacer mutuellement, conformément
//aux règles du jeu d'échecs (la couleur des pièces étant ignorée.)
//Par conséquent, deux dames ne devraient
//jamais partager la même rangée, colonne, ou diagonale
/*******************************************************************/
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#include <ctype.h>
#include <windows.h>
#define vrai 1
#define faux 0
FILE *Fichier;
int **Damier;
char Buf[1];
void Affiche (int Dim ) {
int ParcourLigne,ParcourColonne;
for (ParcourLigne=0;ParcourLigne<Dim;ParcourLigne++)
{
for (ParcourColonne=0;ParcourColonne<Dim;ParcourColonne++) {
_itoa(Damier[ParcourLigne][ParcourColonne],Buf,10);
fputs(Buf,Fichier);
fputs("\t",Fichier);
printf("%d\t",Damier[ParcourLigne][ParcourColonne]);
}
fputs("\n",Fichier);
printf("\n");
}
}
void Init(int Dim) {
int ParcourLigne,ParcourColonne;
for (ParcourLigne=0;ParcourLigne<Dim;ParcourLigne++)
for(ParcourColonne=0;ParcourColonne<Dim;ParcourColonne++)
Damier[ParcourLigne][ParcourColonne] = 0;
}
//
//fonction qui vérifie si on peut poser une dame à la
//position Ligne,Colonne en regardant les colonnes vers la
//gauche.
//
int PeutPoser(int Ligne, int Colonne,int Dim){
int ParcourLigne,ParcourColonne,ok;
ok = vrai;
ParcourColonne=Colonne-1;
ParcourLigne=Ligne;
while(ParcourColonne>=0 && ok) {
if (Damier[ParcourLigne][ParcourColonne]) ok= faux;
ParcourColonne--;
}
ParcourLigne=Ligne-1;
ParcourColonne=Colonne-1;
while(ParcourLigne>=0 && ParcourColonne>=0 && ok) {
if (Damier[ParcourLigne][ParcourColonne]) ok = faux;
ParcourLigne--;
ParcourColonne--;
}
ParcourLigne=Ligne+1;
ParcourColonne=Colonne-1;
while(ParcourLigne<Dim && ParcourColonne>=0 && ok) {
if (Damier[ParcourLigne][ParcourColonne]) ok = faux;
ParcourLigne++;
ParcourColonne--;
}
return ok;
}
//
//
//fonction qui essaye mettre une dame dans la colonne "Colonne"
//si on peut on passe au colonne suivant par appel recusive, sinon
//on cherche une position dans la colonne précédente.
//lorsque on pose une dame dans une case, on teste toutes les
//possibilités dans la colonne suivante
//
int Positionner(int Colonne, int Dim){
int ParcourLigne,NbreSolutions=0;
if (Colonne==Dim ) {
Affiche(Dim);
printf("\n");
fputs("\n",Fichier);
return 1;
}
//
//Mettre la dame dans une ligne du colonne
//
for (ParcourLigne=0;ParcourLigne<Dim;ParcourLigne++)
if (PeutPoser(ParcourLigne,Colonne,Dim))
{
Damier[ParcourLigne][Colonne]=vrai;
NbreSolutions+=Positionner(Colonne+1,Dim);
Damier[ParcourLigne][Colonne]=faux;
}
return NbreSolutions;
}
//
int main(){
int TailleDamier,AllocLigne, NbreSolutions = 0;
int Rep;
LARGE_INTEGER Debut,Fin,Frequence;
double Duree;
printf("********************************Probl%cme de n-dame******************************\n\n\n",138);
printf("Donner la dimension du damier \n");
scanf("%d",&TailleDamier);
//
//allocation dynamique
//
Damier = malloc(TailleDamier*sizeof(int*));
if (Damier == NULL) {
printf("ERREUR allocation mémoire%c !!!\n",130);
exit(EXIT_FAILURE);
}
else {
for (AllocLigne = 0;AllocLigne<TailleDamier;AllocLigne++) {
Damier[AllocLigne] =malloc(TailleDamier*sizeof(int));
if (Damier[AllocLigne] == NULL) {
printf("ERREUR allocation mémoire%c !!!\n",130);
exit(EXIT_FAILURE);
}
}
QueryPerformanceFrequency(&Frequence);
QueryPerformanceCounter(&Debut);
if( (Fichier = fopen( "Solutions.txt", "w+" )) != NULL )
{
printf( "Fichier ouvert...\n");
Init(TailleDamier);
//
//on commence par la colonne 0
//
NbreSolutions = Positionner(0,TailleDamier);
///
_itoa(NbreSolutions,Buf,10);
fputs(Buf,Fichier);
fputs(" Solutions\n",Fichier);
printf("%d solutions\n",NbreSolutions);
printf("Vous trouvez les solutions dans le fichier 'Solutions.txt' \n");
printf("0 --> position vide \n");
printf("1 --> position occup%ce par une dame \n",130);
fputs("0 --> position vide \n",Fichier);
fputs("1 --> position occupée par une dame \n\n",Fichier);
QueryPerformanceCounter(&Fin);
Duree = 1000.0 * (Fin.QuadPart-Debut.QuadPart)/Frequence.QuadPart;
printf("\nEx%ccut%c en %0.3f secondes.\n",130,130,Duree/1000);
}
else
printf( "Erreur d'ouverture du fichier \n");
fclose(Fichier);
//
//Désalloaction mémoire
//
for (AllocLigne = 0;AllocLigne<TailleDamier;AllocLigne++)
free(Damier[AllocLigne]);
free(Damier);
//
}
printf("\n\nTaper sur Entr%ce pour continuer.\nTaper sur une autre pour quitter\n\n\n",130);
Rep = _getch();
if (__toascii(Rep) == 13) {system("cls");main();}
else exit(EXIT_SUCCESS);
}
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.