Problème des 8 reines

Soyez le premier à donner votre avis sur cette source.

Snippet vu 16 357 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
eldered
Messages postés
231
Date d'inscription
vendredi 21 mars 2003
Statut
Membre
Dernière intervention
22 avril 2007
 -
Salut,

Je n'ai pas télécharger ta source, mais si je comprend bien, elle permet à l'utilisateur de déplacer les reines sur le damier, puis qd il a placé les 8 reines, il a gagné ?

Il est ou l'exercice de style algorithmique ? Si tu donnais au moins toutes les solutions pour en placer 8, on pourrait parler d'algo, mais là, c'est plus de l'interface homme-machine.

Pour info : http://perso.wanadoo.fr/eddy.albert/sheets/pedag.htm
tu as le pb avec n reines et toutes ces solutions !

++ Ed.
Signaler
Clonk
Messages postés
278
Date d'inscription
mardi 22 janvier 2002
Statut
Membre
Dernière intervention
29 août 2006
 -
Nan eldered! sur un échiquier de 8*8, on essaye de place 8 reines pour qu'elles ne puissent pas se "bouffer" en un coup...
Ce problème est vieux comme le monde, c'est un cas d'école en informatique (jme le suis tapé 2 fois déjà)

Dis donc, tu veux pas essayer en n reines maintenant?
C tellement plus drôle ;)
Signaler
Clonk
Messages postés
278
Date d'inscription
mardi 22 janvier 2002
Statut
Membre
Dernière intervention
29 août 2006
 -
Rooo! Mais C même pas un générateur de solutions!!!
Bah alors? ;)
nan, C pas mal dans l'idée, mais le but du problème des n reines, C de générer toutes les solutions possibles!
Signaler
cs_khayyam
Messages postés
51
Date d'inscription
lundi 7 juin 2004
Statut
Membre
Dernière intervention
15 juillet 2005
 -
pour passer à n reines, c'est franchement pas beaucoup plus difficile. il suffit de changer les bornes et la taille du tableau. le générateur de solutions, ça sera pour la prochaine fois , si vous êtes sages.
Signaler
eldered
Messages postés
231
Date d'inscription
vendredi 21 mars 2003
Statut
Membre
Dernière intervention
22 avril 2007
 -
Clonk : J'ai bien compris que c'était avec 8 reines, mais justement, je lui reprochais de ne pas donner les solutions. Ensuite, il y a plusieurs résolutions à ce problème, c'est pour ça que c interessant de voir comment s'y est pris le programmeur ...

Khayyam : Alala, comment ça "c'est franchement pas beaucoup plus difficile" ??? Fais le qu'on rigole ^^ ... Lance ton algo pour un damier de 16*16 et on verra le temps qu'il mettra ! Le but de l'algorithme (en général) c'est d'optimiser le temps de calcul sans perdre la solution ... si tu ne prend pas se problème avec des principes de séparation (condamnée des branches de ton graphe ...), ton pc va souffrir !

Enfin ceci dit, il est vrai que c'est pas compliquer, mais faut le faire pour capter le truc !

++ Ed.
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)