Accueil > > > PROBLÈME DE N DAMES
PROBLÈME DE N DAMES
Information sur la source
Description
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
/************************************** *****************************/
Source
- /*******************************************************************/
- /*** 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);
-
-
- }
-
-
/*******************************************************************/
/*** 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);
}
Sources du même auteur
Sources de la même categorie
Commentaires et avis
Discussions en rapport avec ce code source dans le forum
Jeu de dames - Min max [ par lacerto84 ]
Salut tout le monde,Je commence en C++ et je souhaiterais réaliser un jeu.J'ai donc choisi de faire un jeu de dames avec IA.J'ai fait des recherches e
algo du jeu de dames [ par lesaleas ]
je suis étudiante et je dois programmer un jeu de dames je m'y connait rien, aidez moi s'il vous plait!!!!! léa
URGENT Jeu de dames en C [ par ledawa ]
Bonjour je cherche un code source en language C d'un jeu de dames pouvant etre exécuté en mode terminal sous Xterm(Linux). Merci pour votre aide
Algorithme d'un jeu de dames simplifié [ par PRUNE87 ]
Bonjour, Je recherche l'algorithme (programme principal + fonction/procédure d'un jeu de dames simplifié dont voici la règle: "L'ordinateur demande
|
Derniers Blogs
[TECHDAYS2012] OUI J'Y SERAI![TECHDAYS2012] OUI J'Y SERAI! par JeremyJeanson
Bonsoir, Certes, je l'annonce avec un peu de retard, mais je serai effectivement au Techdays demain. Comme l'an dernier, je participerai au programme ATE (Ask The Expert). Si vous avez des questions Workflow, WCF, AppFabric ou plus généralement .net, n'hé...
Cliquez pour lire la suite de l'article par JeremyJeanson TFS INTEGRATION TOOLS - SUIVI DES SYNCHRONISATIONS AVEC REPORTING SERVICESTFS INTEGRATION TOOLS - SUIVI DES SYNCHRONISATIONS AVEC REPORTING SERVICES par vfabing
Afin de s'assurer du bon fonctionnement des différentes synchronisations effectuées par les TFS Integration Tools, 2 rapports sont présents dès l'installation. Il suffit alors d'effectuer les manipulations suivantes pour pouvoir les visualiser : Loca...
Cliquez pour lire la suite de l'article par vfabing CSS CONTENT STATE SELECTORS (PERSONNAL DRAFT)CSS CONTENT STATE SELECTORS (PERSONNAL DRAFT) par FREMYCOMPANY
Bonjour à tous, Je viens de publier une proposition comprenant 5 pseudo-classes pour le CSS Working Group ayant trait à l'état de chargement d'un élément (ex: IMG,VIDEO,AUDIO,OBJECT pour l'HTML.). Si le c½ur vous en dit, vous pouvez retrouver cette p...
Cliquez pour lire la suite de l'article par FREMYCOMPANY MBA : POURQUOI FAIRE ET COMMENT LE CHOISIR ?MBA : POURQUOI FAIRE ET COMMENT LE CHOISIR ? par ROMELARD Fabrice
Formation initiale Durant la formation, le découpage classique est le suivant (je donnerai les équivalences Suisse lorsque je les connaîtrais) : Ecole primaire jusqu'au Collège : Formation générale permettant d'obtenir les méthodes...
Cliquez pour lire la suite de l'article par ROMELARD Fabrice Y'A DES ERREURS QUI PEUVENT RENDRE LE DéVELOPPEUR VIOLENTY'A DES ERREURS QUI PEUVENT RENDRE LE DéVELOPPEUR VIOLENT par Aleks
Quand on a ce genre d'erreur sans log :
Et bas on a juste envie de choper le gas de Microsoft qu'a développé ça et lui foutre des baffes de Coboye ! ...
Cliquez pour lire la suite de l'article par Aleks
Forum
RE : ARBRE BINAIRERE : ARBRE BINAIRE par pacotheking
Cliquez pour lire la suite par pacotheking
Logiciels
Academy System (17.2.1.0)ACADEMY SYSTEM (17.2.1.0)Logiciel de gestion des établissements.
- élèves/étudiants (inscription, dossier, absence...)
-... Cliquez pour télécharger Academy System Easy-Planning (1.0.0.1)EASY-PLANNING (1.0.0.1)Basé sur les mêmes principes que MyPlanning, Easy-Planning permet de créer des plannings sous la ... Cliquez pour télécharger Easy-Planning COLLECTOR PLUS (3.00B)COLLECTOR PLUS (3.00B)COLLECTOR PLUS version 3.00B est un logiciel utilisant une base de données alimentée par :
- L... Cliquez pour télécharger COLLECTOR PLUS PONAMEDIA PREMIUM - HELLLOOO FLASH DEMO (V7.4)PONAMEDIA PREMIUM - HELLLOOO FLASH DEMO (V7.4)PONAMEDIA TV DEVIENS HELLLOOO FLASH
LA TV SUR VOTRE ORDINATEUR.
Toute une plateforme Multi... Cliquez pour télécharger PONAMEDIA PREMIUM - HELLLOOO FLASH DEMO LettresFaciles 2011 (8.0.0.1)LETTRESFACILES 2011 (8.0.0.1)LettresFaciles est un logiciel facilitant la création et la rédaction de lettres types.
Son inte... Cliquez pour télécharger LettresFaciles 2011
|