Sudoku résolu en langage C [Fermé]

Signaler
Messages postés
3
Date d'inscription
lundi 3 avril 2006
Statut
Membre
Dernière intervention
31 mai 2006
-
 soumaya -
Si cela peut aider, vous trouverez le source pour résoudre les grilles de sudoku à :
http://www.i2i.fr/
Langage C. Méthode récursive. Mis à part la saisie, 25 lignes d'instruction suffisent.
A+

5 réponses

#include <iostream.h>
#include <conio.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <io.h>
#include <dos.h>

int joueur; //1 si oui 0 sinn(arbitre)
int oui=0; // un sudoku deja enregistré par l'arbitre ?
int SDK_a[9][9];
int SDK_j[9][9];
int SDK_s[9][9];
int SDK_copi[81]; // tableau ou on va stocker la matrice pour detecter les cases vides (reste inchangé)
int ind_1_cv; // var globale indice de la 1ere case vide ds le tableau copi

/***************************** Fct gestion curseur ****************************/
void curseur(int curseur_on)
{
int d,f;
union REGS rin,rout;
if(curseur_on) { d=3; f=4; } else { d=17; f=16; }
rin.h.ch=d;
rin.h.cl=f;
rin.h.ah=1;
int86(0x10,&rin,&rout);
}
//****************************** Fct BIENVENUE ******************************//
void bienvenue()
{
int l; clrscr(); curseur(0);
for(l=7;l<26;l++)
{ gotoxy(11,l); textbackground(11);cprintf(" ");}
gotoxy(11,7);textcolor(8); cprintf("Ú ¿");
gotoxy(11,25); cprintf("À Ù");

gotoxy(36,9); textcolor(1); cprintf("SU DO KU");
gotoxy(29,9); textcolor(4+128); cprintf("  "); gotoxy(46,9); cprintf("  ");
gotoxy(26,11); textcolor(9); cprintf(" Version beta / Realis‚ par:");
gotoxy(15,13); textcolor(8); cprintf("Badr BRIOUAL SA@d HAFFAR");

textbackground(0);textcolor(WHITE); delay(4000) ;
}
//*************************** Fct Msg pas solution ***************************//
void msg(char ch[])
{
clrscr(); curseur(0);
gotoxy(20,13);textcolor(14+128); cprintf("%s",ch);textcolor(15);
gotoxy(15,10);textbackground(2); cprintf(" ");
gotoxy(15,16);cprintf(" "); textbackground(0);
delay(1500);
}
/********************** Fct Suppression ac un backspace ***********************/
void suppression(int i, int j, int J, int I)
{ gotoxy(i+1,j);
printf("\b"); // on fait un backspace
printf(" "); // on remplace le caractere par un espace
printf("\b"); // on revient o debut
if(joueur) SDK_j[J][I]=0; else SDK_a[J][I]=0;
}
///////////////////////// Fct Affichage grille resolue /////////////////////////
void aff_sol()
{
int I,J, i,j; curseur(0);
for(I=0,i=9;I<=8;i+=4,I++)
for(J=0,j=25;J<=8;j+=4,J++)
{gotoxy(j,i); if (SDK_s[I][J]!=SDK_a[I][J]) {textcolor(WHITE);} else {textcolor(11);} cprintf("%d",SDK_s[I][J]);}
}
//********************************************
void affich_sdk_jr()
{
int I,J, i,j;
for(I=0,i=9;I<=8;i+=4,I++)
for(J=0,j=25;J<=8;j+=4,J++)
{gotoxy(j,i);if (SDK_a[I][J]==0) printf(" "); else {textcolor(11); cprintf("%d",SDK_a[I][J]); textcolor(WHITE); }}
}
//********************************************
void affich_erreurs()
{
int I,J, i,j;
for(I=0,i=9;I<=8;i+=4,I++)
for(J=0,j=25;J<=8;j+=4,J++)
{ gotoxy(j,i);
if (SDK_j[I][J]!=0)
{if (SDK_j[I][J]!=SDK_s[I][J] ) {textcolor(4); cprintf("%d",SDK_j[I][J]); textcolor(WHITE); }
else printf("%d",SDK_j[I][J]);}
}
}
//********************************************
void copier_tableau(int copie[81])
{
int i;
for (i=0; i<81; i++)
copie[i]=SDK_a[i/9][i%9];
}
//********************
void copier_tab(int SDK[9][9])
{ int i,j;
for(i=0;i<9;i++) // on remplie la matrice par des espaces (la comparaison)
for(j=0;j<9;j++)
SDK[i][j]=SDK_a[i][j];
}
//********************************************
int detect_1_case_vide(int h)
{
if (SDK_copi[h]) return detect_1_case_vide(h+1); // ce n'est pas la 1er case vide , n pass à la suivante
return h;
}
//********************************************
int detect_cv_suiv(int I)
{
if (SDK_copi[I]) return detect_cv_suiv(I+1); // ce n'est pas la case vide , n pass à la suivante
// condition nn verifiée dc sdk_copi[i]=0
return I;
}
//********************************************
int detect_cv_prec(int I)
{
if(SDK_copi[I]) return detect_cv_prec(I-1); // ce n'est pas la case vide , n pass à la suivante
// condition nn verifiée dc sdk_copi[i]=0
return I;
}
////////////////////// Fct Remplissage grille SDK ac des 0 /////////////////////
void remplissage_grille_zeros()
{ int J,I;
for(J=0;J<9;J++) // on remplie la matrice par des espaces (la comparaison)
for(I=0;I<9;I++)
SDK_a[J][I]=0;
}
/////////////////////////////// Fct ctrl region ////////////////////////////////
int ctrl_region(int SDK[9][9],int lig, int col, int val)
{
int lmin,lmax,cmin,cmax,l,c,ok=1;
lmin=lig/3*3; lmax=lmin+3;
cmin=col/3*3; cmax=cmin+3;

for(l=lmin; l<lmax && ok; l++)
for(c=cmin; c<cmax && (ok=(l==lig || c==col) || SDK[l][c]!=val); c++); //on compare pa si il sagi de la meme ligne ou la meme colene deja controlé

return ok; // ok=0 si l'element existe
}
////////////////////////// Fct ctrl lignes & colones ///////////////////////////
int ctrl_lignes_colones(int SDK[9][9], int J, int I, int val)
{
int x;
for(x=0; x<9 && SDK[J][x]!=val && SDK[x][I]!=val; x++);
return x==9; //si x==9 est vraie on retourne 1 (le chiffre k'on vt ajouter n'existe pas)
//sinon on retourne 0
}
/////////////////////////// Fct Resolvante du SUDOKU ///////////////////////////
int resoudre_SDK(int t)
{
int i,j; int icv; // icv indice case vide

if(t<81) // on a pa depasser la tailmle effective du tab sdk_copi
{
i=t/9; j=t%9;

while( (ctrl_lignes_colones(SDK_s,i,j,SDK_s[i][j]+1) && ctrl_region(SDK_s,i,j,SDK_s[i][j]+1))==0)
SDK_s[i][j]++;//on incrémente la valeur de la case tant qu'une valeur ne vérifie pas le test
SDK_s[i][j]++;//on incrémente la valeur car dans le test, on teste pour la valeur au dessus

if(i==(ind_1_cv/9) && j==(ind_1_cv%9) && SDK_s[i][j]==10) //si on est à la première case vide et qu'aucunes valeurs ne convient alors la grille est irrésolvable
{return 0;}

if(SDK_s[i][j]==10)//cas où aucune valeur n'est possible
{
SDK_s[i][j]=0;//on remet à 0 la case qui a atteint le max = 10
icv=detect_cv_prec(t-1); return resoudre_SDK(icv);
}
else {icv=detect_cv_suiv(t+1); return resoudre_SDK(icv); }
}
else return 1;
}
/****************************** Partie Arbitre *********************************/
void partie_arbitre()
{
textcolor(161); gotoxy(35,5); cprintf("Partie Arbitre"); textcolor(WHITE);
gotoxy(3,9); textcolor(38); cprintf("ÉÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍ»");
gotoxy(3,10);cprintf("º OPTIONS Du JEU º");
gotoxy(3,11);cprintf("ÈÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍͼ");

gotoxy(4,15); textcolor(53);cprintf("F10: Sauvegarder");

gotoxy(5,18); textcolor(29);cprintf("Echap: Quitter");textcolor(11);
}
/****************************** Partie joueur *********************************/
void partie_joueur()
{
textcolor(161); gotoxy(34,5); cprintf(" Partie Joueur"); textcolor(WHITE);
gotoxy(62,15); cprintf("ASSISTANCE:");
gotoxy(74,15);textcolor(RED);cprintf ("OFF");textcolor(WHITE);

gotoxy(3,8);textcolor(38);cprintf("ÉÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍ»");
gotoxy(3,9);cprintf("º REGLES DE JEU º");
gotoxy(3,10);cprintf("ÈÍÍÍÍÍÍÍÍÍÍÍÍÍÍͼ");

gotoxy(3,13); textcolor(4);cprintf(" Parcourir grille");
gotoxy(12,15); cprintf("");
gotoxy(11,16);cprintf("  ");
gotoxy(12,17); cprintf("");

gotoxy(3,20); textcolor(60);cprintf("Chiffres autoris‚s");
gotoxy(10,22); cprintf("1 2 3");
gotoxy(10,24); cprintf("4 5 6");
gotoxy(10,26); cprintf("7 8 9");

gotoxy(5,29); textcolor(53);cprintf("F2: Assistance");;
gotoxy(5,33); textcolor(53);cprintf("F3: Mes erreurs");
gotoxy(5,37); textcolor(29);cprintf("F5: Solutions");
gotoxy(5,41); textcolor(29);cprintf("Echap: Quitter");textcolor(11);
}
////////////////////////////////// Fct Grille //////////////////////////////////
void grille()
{
clrscr(); curseur(0); // masquer le curseur
textcolor(11);gotoxy(1,3); textbackground(17); cprintf(" Sudoku "); textbackground(0);

int l=7,c; textcolor(11);

if(joueur) partie_joueur(); else partie_arbitre();
while(l<=43)
{
for(c=24;c<59;)
{
gotoxy(c,l);textbackground(BLUE);cprintf("ÍÍÍ");textbackground(0);
if (l!=43) {gotoxy(c,l+4);cprintf("ÄÄÄ"); gotoxy(c,l+8);cprintf("ÄÄÄ");}
c=c+4;
}
l=l+12;
}
c=23;
while(c<=59)
{
for(l=8;l<42;)
{
gotoxy(c,l);textbackground(BLUE);cprintf("º"); gotoxy(c,l+1);cprintf("º"); gotoxy(c,l+2);cprintf("º"); textbackground(0);
if (c!=59) { gotoxy(c+4,l); cprintf("³"); gotoxy(c+8,l);cprintf("³");
gotoxy(c+4,l+1);cprintf("³");gotoxy(c+8,l+1);cprintf("³");
gotoxy(c+4,l+2);cprintf("³");gotoxy(c+8,l+2);cprintf("³");
}
l=l+4;
}
c=c+12;
}
for(c=27;c<59;)
{
if(c!=35 && c!=47){gotoxy(c,7);textbackground(BLUE);cprintf("Ñ");gotoxy(c,43);cprintf("Ï");}
else {gotoxy(c,7);cprintf("Ë");gotoxy(c,43);cprintf("Ê");}
c=c+4;
}
for(l=11;l<43;)
{ textbackground(BLUE);
if(l!=19 && l!=31) {gotoxy(23,l);cprintf("Ç");gotoxy(59,l);cprintf("¶");}
else {gotoxy(23,l);cprintf("Ì"); gotoxy(59,l);cprintf("¹");} textbackground(0);
l=l+4;
}
for(l=11;l<43;)
{
for(c=27;c<59;)
{
gotoxy(c,l); cprintf("Å"); gotoxy(c+4,l);cprintf("Å");
gotoxy(c,l+4); cprintf("Å"); gotoxy(c+4,l+4);cprintf("Å");
c=c+12;
}
l=l+12;
}
for(l=19;l<43;)
{
for(c=27;c<59;)
{
if (c!=35 && c!=47) {gotoxy(c,l);textbackground(BLUE);cprintf("Ø"); gotoxy(c+4,l);cprintf("Ø");c=c+8;}
else {gotoxy(c,l); cprintf("Î");textbackground(0); c=c+4;}
}
l=l+12;
}
c=35; textbackground(BLUE);
while(c!=59)
{
for(l=11;l<43;)
{
gotoxy(c,l);cprintf("×"); gotoxy(c,l+4);cprintf("×");
l=l+12;
}
c=c+12;
}
gotoxy(23,7);cprintf("É"); gotoxy(59,7);cprintf("»");
gotoxy(23,43);cprintf("È"); gotoxy(59,43);cprintf("¼");textcolor(WHITE);textbackground(0);
}

/*******************************Fct ctrl_touches ******************************/
char ctrl_touche()
{
char c; int cp;
do{ // Boucle de contr“le des touches autoris‚es
cp=0;
fflush(stdin); c=getch();
if(c==0) {c=getch();cp=1;} // on s'assure k'il sagit bien des codes ascii des fleches
}while( ( (c!=80&&c!=72&&c!=75&&c!=77&&(c!=60||!joueur)&&(c!=61||!joueur)&&(c!=63||!joueur) ) || !cp) && (!isdigit(c)||c=='0') && c!=27 && c!=8);
return c;
}
/******************************************************************************/
void stock_valeur_grille(int SDK[9][9],int i,int j,int J,int I,int v)
{
gotoxy(i,j); printf("%d",v);
SDK[J][I]=v; gotoxy(i,j); curseur(1);
}
////////////////////////////// partie traitement ///////////////////////////////
void manipulation(int *J,int *I,int *j,int *i,char c,int *A)
{ int N;
switch(c) //Etude des cas (monter,d‚scendre,aller a droite ou a gauche)
{
case 80 : *j=*j+4;(*J)++; if(*j>41) {*j=9;*J=0;}gotoxy(*i,*j); curseur(1);break;
case 72 : *j=*j-4;(*J)--; if(*j<9) {*j=41;*J=8;}gotoxy(*i,*j); curseur(1);break;
case 77 : *i=*i+4;(*I)++; if(*i>57) {*i=25;*I=0;}gotoxy(*i,*j); curseur(1);break;
case 75 : *i=*i-4;(*I)--; if(*i<25) {*i=57;*I=8;}gotoxy(*i,*j); curseur(1); break;
case 8 : suppression(*i,*j,*J,*I); break;
case 27 : break;
case 63 : copier_tab(SDK_s); ind_1_cv=detect_1_case_vide(0);
N=resoudre_SDK(ind_1_cv); if(N) aff_sol(); else msg(" Cette Grille n'a pas de solution "); break;
case 61 : copier_tab(SDK_s); ind_1_cv=detect_1_case_vide(0); N=resoudre_SDK(ind_1_cv);
affich_erreurs(); gotoxy(*i,*j); curseur(1);break;
case 60 : (*A)++;
if((*A)%2==0) // aide activ‚e
{gotoxy(74,15);textcolor(GREEN);cprintf("ON "); gotoxy(*i,*j);}
else
{gotoxy(74,15);textcolor(RED);cprintf("OFF"); gotoxy(*i,*j);}textcolor(WHITE); break;
default : if((*A)%2==0) // aide activ‚e
{
if(joueur)
{ if (ctrl_lignes_colones(SDK_j,*J,*I,c-'0') && ctrl_region(SDK_j,*J,*I,c-'0') )
stock_valeur_grille(SDK_j,*i,*j,*J,*I,c-'0');
else printf("\a");}
else
{ if( ctrl_lignes_colones(SDK_a,*J,*I,c-'0') && ctrl_region(SDK_a,*J,*I,c-'0') )
stock_valeur_grille(SDK_a,*i,*j,*J,*I,c-'0');
else printf("\a");}
}/*aide desactiv‚e*/
else stock_valeur_grille(SDK_j,*i,*j,*J,*I,c-'0');break;
}
}
//************************** Le Menu deroulant ********************************/
void menu_deroulant(char *v_menu[],int taille_menu,int *pos)
{
int i,cp; char c; clrscr();
do{
for(i=0;i<taille_menu;i++) //Boucle de r‚affichage du menu
{gotoxy(15*(i+1),10*i+10);
if(*pos==i) {textbackground(4);textcolor(14);}cprintf("%10s",v_menu[i]);textcolor(WHITE); textbackground(0); }

do{ // Boucle de contr“le des touches autoris‚es
cp=0;c=getch();
if(c==0) {c=getch();cp=1;}
} while( ((c!=80 && c!=72)|| !cp)&& c!=13 );

switch(c) //Etude des cas (monter ou d‚scendre)
{
case 80 : (*pos)++; if(*pos>taille_menu - 1) *pos=0;break;
case 72 : (*pos)--; if(*pos<0) *pos=taille_menu - 1;break;
}
}while( c!=13);
}
//////////////////////////////// Fct MENU SUDOKU ///////////////////////////////
void menu()
{
char c,*menu[]={" Charger/Jouer "," Creer une grille "," Quitter "};
int position_menu=0;
do{
clrscr(); curseur(0);
menu_deroulant(menu,3,&position_menu);
curseur(1); fflush(stdin);clrscr();
switch(position_menu)
{
case 0 : char c; int A=1; //A boolienne de l'aide
int i=25,j=9 ,J=0, I=0; //i,j indice curseur //I,J indices matrice
if(oui)
{
joueur=1; grille();copier_tab(SDK_j);
affich_sdk_jr(); gotoxy(i,j); curseur(1);
do{
c=ctrl_touche();
manipulation(&J,&I,&j,&i,c,&A);
}while( c!=27);
} else msg(" Auccune grille enregistr‚e "); break;
case 1 : A=0; joueur=0; i=25,j=9 ,J=0, I=0;
remplissage_grille_zeros(); //on remplie la matrice ac des zeros
grille(); gotoxy(i,j); curseur(1);
do{
fflush(stdin); c=ctrl_touche();
manipulation(&J,&I,&j,&i,c,&A);
}while( c!=27); copier_tableau(SDK_copi); oui=1; break;
}
} while(position_menu!=2);
}
/////////////////////////////////// Fct main ///////////////////////////////////
void main()
{
bienvenue();// message de la bienvenue
menu(); //le menu deroulant
}
16
Merci

Quelques mots de remerciements seront grandement appréciés. Ajouter un commentaire

CCM 65492 internautes nous ont dit merci ce mois-ci

bonsoir
est ce que vous avez le code du jeu fubuki svp?
merci
j'aimerais avoir l'algorithme corrigé du jeu sudoku pour m'entrainer aux exams...
Messages postés
3
Date d'inscription
vendredi 15 septembre 2006
Statut
Membre
Dernière intervention
16 septembre 2006

bjr eske tu peux menvoyet la procedure k tu as utilisé pour le problème de sudocu
merci
Bonjour j'aurai voulu avoir le programme complet du jeu de sudoku en langage c
bonjour,je voudrais avoir selmen le traitement du control ligne et control colones du probléme du sudoku svp le plus vite possibl,autre traitement sera le bienvenu.merci bcp
Messages postés
15
Date d'inscription
dimanche 27 juillet 2008
Statut
Membre
Dernière intervention
26 septembre 2008

slt
désolé,c'est ou~ le source?