1. Accueil
  2. Tous les snippets
  3. Snippets C / C++ / C++.NET
  4. Problème des 8 reines

Problème des 8 reines

Soyez le premier à donner votre avis sur cette source.

Snippet vu 16 903 fois - Téléchargée 29 fois

Commenter

Contenu du snippet

/*******jeu des huit reines sur un échiquier*********
le but est très simple : réussir à placer huit reines sur une damier sans qu'aucune d'elle
ne soit en échec avec une autre.

commandes :
HAUT - BAS - GAUCHE - DROITE pour déplacer le curseur sur le damier
ESPACE pour (dé)cocher une case
ESC pour quitter

se compile proprement sans warning sous devcpp 4.9.8.10
et pour ceux qui ne sauraient pas, il faut inclure conio.c au projet pour que la compilation
se déroule normalement.

nombre de reines limité à 19, taille de l'écran DOS oblige.

très bon exercice d'algorithme.*/

Source / Exemple : 


#include <stdio.h>
#include <conio.h>
#define ABS(a) (a>0)?a:(a==0)?1:-a 
typedef enum {faux, vrai} boolean;

short NB_REINES=0;

boolean verifier_reine (boolean t[19][19], char x, char y)
{
    char i;
    for (i=0; i<NB_REINES; i++)
        {
            if ((i!=x) && t[i][y]==vrai) // horizontale
                  return faux;            
   
      
            if ((i!=y) && t[x][i]==vrai)  // verticale
                  return faux;           
       
             
            if ((i!=0) && ((x+i)<=NB_REINES-1) && ((y+i)<=NB_REINES-1) && t[x+i][y+i]==vrai)     // diag haut droit
                  return faux;
      
       
            if ((i!=0) && ((x+i)<=NB_REINES-1) && ((y-i)>0) && t[x+i][y-i]==vrai)    // diag bas droit
                  return faux;                                     
       
       
            if ((i!=0) && ((x-i)>=0) && ((y+i)<=NB_REINES-1) && t[x-i][y+i]==vrai)    // diag haut gauche
                  return faux;                                     
        
                
            if ((i!=0) && ((x-i)>=0) && ((y-i)>=0) && t[x-i][y-i]==vrai)    // diag bas gauche
                  return faux;                                     
        }  
        
return vrai;    
}

boolean verifier_damier(boolean t[19][19])
{
    short i=0,j=0,k=0;
    
    for (j=0; j<NB_REINES; j++)
          for (k=0; k<NB_REINES; k++)
                if (t[j][k]==vrai)
                       {
                         i++;
                         if (verifier_reine(t,j,k)==faux)
                              return faux;                     
                                   
                       }            
if (i==NB_REINES) return vrai;    
else return faux;
}

void gagnee(void)
{
    char i;
    gotoxy(30, 10);
    printf("%c",201);
    for (i=0; i<9; i++)
        printf("%c", 205);
    printf("%c",187);
    gotoxy(30,11);
    printf("%c  Gagn%c  %c",186,130,186);
    gotoxy(30,12);
    printf("%c", 200);
    for (i=0; i<9; i++)
        printf("%c",205);
    printf("%c",188);
    gotoxy(70,25);
    getch();
    exit(0);    
}

void dessiner (void)
{
    gotoxy(1,4); clreol();
    char i,j;
    printf("%c",218);
    for (i=1; i<NB_REINES; i++)
        printf("%c%c%c%c", 196,196,196,194);
    printf("%c%c%c%c\n",196,196,196, 191);
        
    for (j=0; j<NB_REINES-1; j++)
        {
        
        for (i=0; i<NB_REINES; i++)
            printf("%c   ", 179);
        printf("%c\n%c",179,195);
       
        for (i=0; i<NB_REINES-1; i++)
                printf("%c%c%c%c", 196,196,196,197);
        printf("%c%c%c%c\n", 196,196,196,180);
        }    
    
    printf("");
    for (i=0; i<NB_REINES; i++)
            printf("%c   ", 179);
        printf("%c\n",179);
      
    printf("%c",192);
    for (i=1; i<NB_REINES; i++)
        printf("%c%c%c%c", 196,196,196,193);
    printf("%c%c%c%c\n                    ",196,196,196, 217);

    gotoxy(3,5);             
}

void titre(void)
{
    short i; 
    printf("%c",201);
    for (i=1;i<=78;i++) printf("%c",205);
        printf("%c",187);    printf("%c",186);
    printf("                  Probl%cme des huit reines sur l'%cchiquier                    ",138,130);
    printf("%c",186);   printf("%c",200);
    for (i=1;i<=78;i++) printf("%c",205);
        printf("%c\n",188); 
    return;
}

int main()
{  
    unsigned char c,d,a,b;
    boolean gagne=faux;
    char x=0, y=0;
    unsigned char nb_reines=0, nb_reines_ok=0;
        
    titre();
    char rep[2];
    
    gotoxy(1,4);
    printf("tu veux combien de reines ?");
    fgets(rep, 3, stdin);
    
    while ((sscanf(rep, "%d", &NB_REINES)!=1) && ((NB_REINES<=0) || (NB_REINES>19)))
        {gotoxy(1,4);
         printf("tu veux combien de reines ?");
         fgets(rep, 3, stdin); 
        }     
    NB_REINES=ABS(NB_REINES);
    
        
    boolean tab [19][19]={0};        
        
    dessiner();    // en fonction de NB_REINES

    //moteur
    while (!gagne)
        {
        c=getch();
        switch (c)
            {
               case 224: //mouvement
               {
               d=getch();    
               switch(d)
                    {
                    case 72: // haut
                        {
                        if (wherey()!=5)    
                             {gotoxy(wherex(), wherey()-2);
                              y--;
                             }
                        break;
                        }        
                    case 80: // bas
                        {
                        if (wherey()!=2*NB_REINES+3)    
                             {gotoxy(wherex(), wherey()+2);
                              y++;
                             }       
                        break;
                        }        
                    case 77: //droite
                        {
                        if (wherex()!=-1+4*NB_REINES)
                             {gotoxy(wherex()+4, wherey());
                              x++;
                             }  
                        break;
                        }        
                    case 75: // gauche
                        {
                        if (wherex()!=3)    
                             {gotoxy(wherex()-4, wherey());
                              x--;
                             }  
                        break;
                        }      
                    }    
                    break;
                }
                case 27: //quit
                { 
                    return 0;
                    break;
                }  
                case 32: //mettre une X
                {        
                    if (tab[x][y]==faux)
                        {printf("X");
                         tab[x][y]=vrai;
                         
                         if (verifier_damier(tab)==vrai)
                              {gagnee();
                               gagne==vrai;
                              }     
                        }     
                    else 
                        {printf(" ");
                         tab[x][y]=faux;                         
                         
                         if (verifier_damier(tab)==vrai)
                              {gagnee();
                               gagne==vrai;
                              } 
                        
                        }
                             
                    gotoxy(wherex()-1, wherey());    
                    break;
                }
        
             /*a=wherex(); b=wherey();
             gotoxy(1,40); printf("%d %d",a, b);
             gotoxy(a,b);  */                
        
        } //switch c  
    }   // while 
    getchar();
    return 0;
}

Conclusion :


voilà, j'ai ajouté la possibilité de choisir le nombre de reines à placer.
et j'ai corrigé une bourde algorithmique immonde.
en espérant que personne n'avait vu cette affreuse bourde ! ;-)

A voir également

Ajouter un commentaire Commentaires
Signaler
Messages postés
1
Date d'inscription
samedi 17 janvier 2009
Statut
Membre
Dernière intervention
10 octobre 2010
et c'est tres long comme code!
Signaler
Messages postés
231
Date d'inscription
vendredi 21 mars 2003
Statut
Membre
Dernière intervention
22 avril 2007
Wé, c'est pas du rapide ! C'est bourrin, mais bon, c instructif !

++ Ed.
Signaler
Messages postés
3006
Date d'inscription
dimanche 14 avril 2002
Statut
Membre
Dernière intervention
31 décembre 2008
grmbl... viens d'écrire un algo de recherche en profondeur d'abord avec un minimum d'optimisations logiques etc en C++, et dès que je lui demande une résolution pour un échiquier de genre 13*13 il lui fait 25 secondes O_o bon, y a 80 000 solutions (dont je supprime la moitié dès le début en n'acceptant que des reines sur la première moitié de la première ligne, parce que sinon après tu génères toutes les symétries, c'est idiot). c'est qd même super lent! 8 reines ça met entre 0 et 15 ms ...
Signaler
Messages postés
43
Date d'inscription
mardi 30 mars 2004
Statut
Membre
Dernière intervention
7 octobre 2006
ouep c kler ke c un probleme classique ;)
encore un probleme super facile à résoudre en Prolog
pour ceux qui voudraient connaitre les méthodes de résolution avec description type : "génère et teste", "simple retour-arrière", "anticipation/noeud", "anticipation/noeud + échec d'abord"
c'est ici : http://www710.univ-lyon1.fr/~csolnon/Site-PPC/e-miage-ppc-som.htm

ya aussi comparaison de la vitesse d'execution des algos exemple :
http://www710.univ-lyon1.fr/~csolnon/Site-PPC/session4/e-miage-ppc-sess4.htm#grd6
Signaler
Messages postés
3006
Date d'inscription
dimanche 14 avril 2002
Statut
Membre
Dernière intervention
31 décembre 2008
oué oué, okok, mais je comprends pas, ... comme disais je sais plus qui, un algo est sensé résoudre un problème pour un programmeur qui préfère se casser la tête sur la rédaction de l'algo que sur le problème qu'on lui demande de résoudre ^^

écrire une interface pour que l'humain puisse se taper la recherche tout seul, c'est une insulte à la flemmardise des programmeurs! ;)
Afficher les 11 commentaires
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_khayyam)