CodeS-SourceS est hébergé par Frontier.fr

Ce site au démarrage

begin process at 2012 05 27 17:53:07

Accueil Codes Tutoriels Forum Livres Emploi Services Connexion

Trouver un code source :

dans

[ Dernières recherches ]

Accueil >

PROBLÈME DES 8 REINES

Information sur la source

Note :
Aucune note

Catégorie :Jeux Niveau :Débutant Date de création :17/06/2004 Date de mise à jour :18/06/2004 16:00:27 Vu :12 995

Auteur : khayyam

Ecrire un message privé

Site perso

Commentaire sur cette source (11)

Ajouter un commentaire et/ou une note

Description

Cliquez pour voir la capture en taille normale

/*******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

#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;
}

#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 ! ;-)

Sources du même auteur

CRÉATION DE LABYRINTHE POUR POVRAY

ÉCRITURE DE LABYRINTHE

PONG EN OPENGL

RÉSOLUTION DE SYSTÈMES D'ÉQUATIONS LINÉAIRES

DÉCRYPTER VIGENERE AVEC OU SANS LA CLEF

Toutes les sources de khayyam

Sources de la même categorie

JEU DES CARTES par eapaceinfo

PROGRAMME DE JEU DE MPT par KerizGarmm

JEUX SERPENT par antho974

PENDU EN SDL par Damsou91

STATE MACHINE MODIFICATION MATH BUCKHAM par billybones79

Toutes les sources de la catégorie Jeux

Commentaires et avis

Commentaire de eldered le 18/06/2004 10:01:04

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.

Commentaire de Clonk le 18/06/2004 11:46:58

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 ;)

Commentaire de Clonk le 18/06/2004 11:49:55

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!

Commentaire de khayyam le 18/06/2004 11:51:45

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.

Commentaire de eldered le 18/06/2004 13:10:09

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.

Commentaire de khayyam le 18/06/2004 16:06:34

ça y est, j'ai mis un nombre de reines customizable. le prog se révèle instantané (ou presque) même lorsqu'il y a beaucoup de reines.

j'ai aussi corrigé une affreuse bourde algorithmique.

évidemment, ce qui pourrait le ralentir considérablement, ce serait de faire afficher toutes les solutions pour un damier 16*16.

Commentaire de Kirua le 18/06/2004 18:42:03

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! ;)

Commentaire de StanOfSky le 18/06/2004 22:39:22

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

Commentaire de Kirua le 18/06/2004 22:43:51

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 ...

Commentaire de eldered le 18/06/2004 23:01:20

Wé, c'est pas du rapide ! C'est bourrin, mais bon, c instructif !

++ Ed.

Commentaire de willti2s le 10/10/2010 21:34:21

et c'est tres long comme code!

Ajouter un commentaire

Nos sponsors

Derniers Blogs

IMAGINE CUP 2012, MAKE A SIGN EN FINALE par junarnoalg

KINECT 1.5 IS OUT ! par Vko

LES ACTUALITéS DE LA SEMAINE SUR C2I.FR (14 MAI - 20 MAI) par richardc

REACTIVE EXTENSIONS : CONSOMMER DES SERVICES AVEC RX PARTIE 3, LES PIèGES à éVITER par Groc

SHAREPOINT BLOG SITE, PROBLèME D'ARCHIVES par junarnoalg

Forum

MATRICE TEMPLATE par hjr2610

SUPERVISION DE LA BATTERIE par romanticgirl

RE : OPENCV ET INTERFACE GRAPHIQUE VISUAL STUDIO par buno

RE : SAC A DOS par hadjkaddour

OPENCV ET INTERFACE GRAPHIQUE VISUAL STUDIO par ssaif

Côté IT

Offres d'emploi

Formations Video

Appels d'offres

Realisation d-une version 2 d-un site e-commerce existant sous prestashop-REPUBLICATION
Budget : 5 000€
Recherche Infogerance Serveur Debian Linux
Budget : 1 800€
Creation d-un site vitrine avec MagentO
Budget : 2 000€

Logiciels

sDEVIS-FACTURES vlPRO (8.1.0.3)
SDEVIS-FACTURES VLPRO (8.1.0.3)

sDEVIS-FACTURES vlPRO a été mis au point pour les particuliers, créateurs, entrepreneurs, artisa...

Cliquez pour télécharger sDEVIS-FACTURES vlPRO
974 Application Server (12.2.4.6)
974 APPLICATION SERVER (12.2.4.6)

Développez de puissantes applications dans un environnement de 'cloud computing', clusterisé, séc...

Cliquez pour télécharger 974 Application Server
vPicture (1.4.2.1)
VPICTURE (1.4.2.1)

Avec vPicture, hébergez vos images facilement et rapidement. vPicture est un utilitaire simple, ...

Cliquez pour télécharger vPicture
Easy-Planning (2.2.1.6)
EASY-PLANNING (2.2.1.6)

Easy-Planning permet de créer des plannings sous la représentation de diagrammes et est adapté au...

Cliquez pour télécharger Easy-Planning
COM-BACKUP (2.0)
COM-BACKUP (2.0)

COM-BACKUP est un logiciel de sauvegarde qui permet de planifier les sauvegardes de vos dossiers ...

Cliquez pour télécharger COM-BACKUP