8 reines sur un échiqier

Soyez le premier à donner votre avis sur cette source.

Vue 7 028 fois - Téléchargée 253 fois

Description

Je debute en programation C
j ai fait un petit programme en C sur la console qui permet d afficher les 92 possibilités de poser 8 reines sur un echiquier (8*8)
c est une procedure dit de "backtrack" qui permet de faire des essais puis revenir en arriere quand on se trompe.

Source / Exemple :


/*
Comment poser 8 reines sur un echiquier de 8*8

D'apés un exercice du livre:    "Pratiquez l intelligence artificielle"
de
Jean Pascal AUBERT
Richard SCHOMBERG
edition EYROLLES 1984

Fédéric Fabry 05/11/2010
Quito equateur

 t[9][9] je ne travaille pas avec les zeros.
 j ai fais ce programme avec Code::Blocks svn 6647 sur Ubuntu 10.4
 c est mon premier programme en C
 je debute depuis un mois en programmation

 t[9][9] je ne travaille pas avec les zeros. ( j ai tenté de porter ce programme sur Code::Blocks windows 7 mais ca ne reagi pas pareil si le tableau est t[8][8]
                                              je ne suis pas assez bon pour comprendre pourquoi)

abscisse                                        i
ordonnée                                        j

 1/1 1/2 1/3 1/4 1/5 1/6 1/7 1/8
 2/1 2/2 2/3 2/4 2/5 2/6 2/7 2/8
 3/1 3/2 3/3 3/4 3/5 3/6 3/7 3/8
 4/1 4/2 4/3 4/4 4/5 4/6 4/7 4/8
 5/1 5/2 5/3 5/4 5/5 5/6 5/7 5/8
 6/1 6/2 6/3 6/4 6/5 6/6 6/7 6/8
 7/1 7/2 7/3 7/4 7/5 7/6 7/7 7/8
 8/1 8/2 8/3 8/4 8/5 8/6 8/7 8/8

 les positions des reines sont stockées dans    f[9]
 je ne travaille pas avec les zeros.

  • /
#include <stdio.h> #include <stdlib.h> //declaration des fonctions void Initialisation(int(*t)[9],int(*f)); void Calcul(int(*t)[9],int(*f)); void Reine(int(*t)[9],int i,int j ,int p); void Affichage(int(*t)[9]); //debut des fonctions void Initialisation (int(*t)[9],int(*f)) //Initialisation de la zone memoire { int i,j,k; for (i=1;i<=8;i++) { for (j=1;j<=8;j++) { t[i][j]=0; } } for (k=1;k<=8;k++) { f[k]=0; } } void Calcul(int (*t)[9],int (*f)) { int i=0,j=1,k=0,p=0; debut: { if (k==92) { return; //Il n'y a que 92 possibilités (je fais confiance a la litterature et le programme ne va pas plus loin et il faut bien sortir de la boucle) } if (j>=9) //Si on sort de l echiquier { k=k+1; //Compteur de solution printf("Solution num %d \n",k); Affichage (t); //On affiche la solution j=8; //On reviens a la derniere ligne i=f[8]; //On reviens a la derniere reine posée t[i][j]=0; //On efface la reine p=-1; //On passe le parametre qui efface la reine Reine(t,i,j,p); //On efface les impossibilités de la reine i=f[8]+1; //On passe a la position suivante goto rech; //On va rechercher si la pose d'une reine est possible ( c est sur que non mais bon! ) } else { rech: //Debut de la recherche de la pose d une reine { if (t[i][j]==0 && i!=0 && j!=0) //Si on peut poser une reine { t[i][j]=1; //On pose la reine f[j]=i; //On enregistre la position de la reine p=1; //On passe le parametre qui affiche les impossibilites de la reine Reine(t,i,j,p); //On trace les impossibilites de pose d'un reine i=0; //On reinitialise le curseur de colonne j=j+1; //On passe a la ligne suivante goto debut; //On va rechercher sur la prochaine ligne } if (t[i][j]!=0 && i>=8) //Si on ne peut pas poser de reine et qu on arrive en bout de ligne { j=j-1; //On revient a la ligne précédente i=f[j]; //On revient a la reine de la ligne t[i][j]=0; //On efface la reine p=-1; //On passe le parametre qui efface les impossibilites de la reine Reine(t,i,j,p); //On efface les impossibilites de pose d'un reine i=i+1; //On passe a la colonne suivante goto rech; //On va rechercher si la pose d'une reine est possible } i=i+1; //On passe a la colonne suivante goto rech; //On va rechercher si la pose d'une reine est possible } } } } void Reine (int (*t)[9],int i,int j,int p) //Fabrique les horizontales et les verticales interdites pour la pose d'une reine (p=1) ou les efface (p=-1) { int x,y,z,a,b; for(y=-1;y<=1;y++) { for (x=-1;x<=1;x++) { if(((x*y)+x+y)==0) { continue; } else { for (z=1;z<9;z++) { a=i+y*z; b=j+x*z; if (a<0 || a>8 || b<0 || b>8) { continue; } else { t[a][b]=t[a][b]-p; //si p=1 on trace l'impossibilité de pose de reine sinon p=-1 on efface la reine ainsi que ses imposssibilité de pose } } } } } } void Affichage(int(*t)[9]) //Affiche en mode console le damier { int i,j; for (j=1;j<=8;j++) { for (i=1;i<=8;i++) { if (t[i][j]<0) { putchar('*'); //Affiche les impossibilités de pose de reine } else { if (t[i][j]>0) { putchar('R'); //Affiche le R de reine } else { putchar('-'); //Affiche les possibilités de pose de reine } } } printf("\n"); } } /*Programe principal*/ int main() { int t[9][9],f[9]; Initialisation(t,f); Calcul(t,f); return 0; }

Conclusion :


Je suis a la recherche de commentaire car j apprend tout seul avec une litterature mal adapté.

Je ne suis pas content de ma fonction Calcul dont je pense qu elle pourait etre scindée en plusieur fonctions.
Mais les passages de paramètre m inquiette un peu.

Il faut prendre ce programme pour ce qu il est : juste mon premier programme en C.

Codes Sources

Ajouter un commentaire Commentaires
Messages postés
122
Date d'inscription
lundi 16 décembre 2002
Statut
Membre
Dernière intervention
15 février 2011

Bonjour,

Je vois bien que tu es débutant, néanmoins le code est une horreur ! je te conseille fortement d'essayer de le recoder sans les goto et sans le k==92. De plus les 8 reines, est un excellent exercice de récursivité, tu devrais essayer de le faire de cette façon. Bon courage et si tu as besoin d'aide n'hésite pas a poser des questions.
Messages postés
5
Date d'inscription
mercredi 21 juillet 2010
Statut
Membre
Dernière intervention
11 décembre 2011

Bonjour
Je pense avoir mal compris le système de passage de paramètre d un tableau qu'il soit a une dimension ou plusieurs.
Effectivement le int*t[9] peut être remplacé par int*t.

Je comprend pourquoi les goto n ont plus la cote:
sur les langages moderne la notion de fonction ou d'encapsulation permet de penser autrement (fonction ou méthode) mais sur les automates industriels plus proche de l'assembleur, ca fonctionne encore.

Je vous remercie pour vos commentaires.

(demain j'essai le code de yannikator)(super idée mais irréalisable pour moi tout seul)
Messages postés
23
Date d'inscription
mardi 23 octobre 2007
Statut
Membre
Dernière intervention
10 novembre 2012

Bon comme j'étais aussi intéressé par le résultat, j'ai pas résisté de mettre le résultat dans un fichier ^_^.

Pour ceux que ça intéresse :
void saveResult(int(*t)[9]){

FILE *file;
int i,j;
static int tagg = FALSE;

if(tagg == FALSE)
{if((file fopen("C:\\result.txt","w")) NULL)
{printf("Probleme creation fichier...");return;}
}
else
{if((file fopen("C:\\result.txt","a+")) NULL)
{printf("Probleme MAJ fichier...");return;}
}

for (j=1;j<=8;j++)
{
for (i=1;i<=8;i++)
{
if (t[i][j]<0)
{
fputc('*',file);
}
else
{
if (t[i][j]>0)
{
fputc('R',file); //Affiche le R de reine
}
else
{
fputc('-',file); //Affiche les possibilités de pose de reine
}
}
}
/*fprintf(file,"%s",CHARRIOT);*/
fputs(CHARRIOT,file);
}
fprintf(file,"%s%s","--------",CHARRIOT);
fprintf(file,"%s%d%s%s","---",tagg,"---",CHARRIOT);
fprintf(file,"%s%s%s","--------",CHARRIOT,CHARRIOT);
tagg++;
fclose(file);
}

Sans oublié les define:
#define FALSE 0;
#define CHARRIOT "\n" /*retour charriot...*/

A+
Messages postés
23
Date d'inscription
mardi 23 octobre 2007
Statut
Membre
Dernière intervention
10 novembre 2012

Salut,

J'aime beaucoup l'algo, je trouve la méthode étonnante et très ancienne. Ce qui reflète bien la référence bibliographique auquel tu fais référence. Car les goto sont très dépréciés de nos jours, même si ils sont parfois indispensable.
Cependant je serais curieux de savoir si tu peux me dire qu'est-ce que tu fais quand tu déclare tes paramètres avec int (*t)[9], un simple int *t n'aurait pas été plus simple en tant que débutant...
Sinon l'algo je le trouve très intéressant... J'avais jamais pensé comme ça.

A+
Messages postés
473
Date d'inscription
mercredi 7 août 2002
Statut
Membre
Dernière intervention
10 juin 2015

ça dépend, quand je travaillais en vb, j'utilisait des tableaux de base 1. En C j'utilise uniquement des tableaux de base 0.
Fondamentalement, ca ne change pas les données du problème.
Afficher les 7 commentaires

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 (fredericfabry)