|
Trouver une ressource
Vous ne trouvez pas de réponse à votre problème ? Alors posez la question dans le forum. Souvenez-vous qu'il n'y a jamais de question bête, mais rester dans l'ignorance parce que l'on n'ose pas poser une question, ça c'est une erreur !
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
Sources en rapport avec celle ci
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
|
Téléchargements
Logiciels à télécharger sur le même thème :
|