Résolution d'une grille sudoku
Contenu du snippet
EMSI
Réalisé par le binôme:
Aziz ELAZHADI DOKALI
Mohamed BENNIS
Encadrer par:
Dr. BENHSAIN
La resolution d'un grille sudoku avec la technique de backtracking et la methode de tester les case avant
d'executé la fonction solution.
Cette methode traite aussi les combinaison qu'elles prendent beaucoup de temps par raport au autre combinaison
Réalisé par le binôme:
Aziz ELAZHADI DOKALI
Mohamed BENNIS
Encadrer par:
Dr. BENHSAIN
La resolution d'un grille sudoku avec la technique de backtracking et la methode de tester les case avant
d'executé la fonction solution.
Cette methode traite aussi les combinaison qu'elles prendent beaucoup de temps par raport au autre combinaison
Source / Exemple :
#include<Stdio.h>
#include<Conio.h>
#include<Ctype.h>
#include<Stdlib.h>
typedef struct{
int lg;
int cl;
int nbre_possible;
} Case;
Case Tabr[81];
int nr=0,trouve=0;
/*************************************************/
void Grille()
{
textbackground(15);
textcolor(0);
gotoxy(18,10); cprintf("ÉÍÍÍÍËÍÍÍÍËÍÍÍÍËÍÍÍÍËÍÍÍÍËÍÍÍÍËÍÍÍÍËÍÍÍÍËÍÍÍÍ»");
gotoxy(18,11); cprintf("º ³ ³ º ³ ³ º ³ ³ º");
gotoxy(18,12); cprintf("º ³ ³ º ³ ³ º ³ ³ º");
gotoxy(18,13); cprintf("ÌÄÄÄÄÅÄÄÄÄÅÄÄÄÄÎÄÄÄÄÅÄÄÄÄÅÄÄÄÄÎÄÄÄÄÅÄÄÄÄÅÄÄÄĹ");
gotoxy(18,14); cprintf("º ³ ³ º ³ ³ º ³ ³ º");
gotoxy(18,15); cprintf("º ³ ³ º ³ ³ º ³ ³ º");
gotoxy(18,16); cprintf("ÌÄÄÄÄÅÄÄÄÄÅÄÄÄÄÎÄÄÄÄÅÄÄÄÄÅÄÄÄÄÎÄÄÄÄÅÄÄÄÄÅÄÄÄĹ");
gotoxy(18,17); cprintf("º ³ ³ º ³ ³ º ³ ³ º");
gotoxy(18,18); cprintf("º ³ ³ º ³ ³ º ³ ³ º");
gotoxy(18,19); cprintf("ÌÍÍÍÍÎÍÍÍÍÎÍÍÍÍÎÍÍÍÍÎÍÍÍÍÎÍÍÍÍÎÍÍÍÍÎÍÍÍÍÎÍÍÍ͹");
gotoxy(18,20); cprintf("º ³ ³ º ³ ³ º ³ ³ º");
gotoxy(18,21); cprintf("º ³ ³ º ³ ³ º ³ ³ º");
gotoxy(18,22); cprintf("ÌÄÄÄÄÅÄÄÄÄÅÄÄÄÄÎÄÄÄÄÅÄÄÄÄÅÄÄÄÄÎÄÄÄÄÅÄÄÄÄÅÄÄÄĹ");
gotoxy(18,23); cprintf("º ³ ³ º ³ ³ º ³ ³ º");
gotoxy(18,24); cprintf("º ³ ³ º ³ ³ º ³ ³ º");
gotoxy(18,25); cprintf("ÌÄÄÄÄÅÄÄÄÄÅÄÄÄÄÎÄÄÄÄÅÄÄÄÄÅÄÄÄÄÎÄÄÄÄÅÄÄÄÄÅÄÄÄĹ");
gotoxy(18,26); cprintf("º ³ ³ º ³ ³ º ³ ³ º");
gotoxy(18,27); cprintf("º ³ ³ º ³ ³ º ³ ³ º");
gotoxy(18,28); cprintf("ÌÍÍÍÍÎÍÍÍÍÎÍÍÍÍÎÍÍÍÍÎÍÍÍÍÎÍÍÍÍÎÍÍÍÍÎÍÍÍÍÎÍÍÍ͹");
gotoxy(18,29); cprintf("º ³ ³ º ³ ³ º ³ ³ º");
gotoxy(18,30); cprintf("º ³ ³ º ³ ³ º ³ ³ º");
gotoxy(18,31); cprintf("ÌÄÄÄÄÅÄÄÄÄÅÄÄÄÄÎÄÄÄÄÅÄÄÄÄÅÄÄÄÄÎÄÄÄÄÅÄÄÄÄÅÄÄÄĹ");
gotoxy(18,32); cprintf("º ³ ³ º ³ ³ º ³ ³ º");
gotoxy(18,33); cprintf("º ³ ³ º ³ ³ º ³ ³ º");
gotoxy(18,34); cprintf("ÌÄÄÄÄÅÄÄÄÄÅÄÄÄÄÎÄÄÄÄÅÄÄÄÄÅÄÄÄÄÎÄÄÄÄÅÄÄÄÄÅÄÄÄĹ");
gotoxy(18,35); cprintf("º ³ ³ º ³ ³ º ³ ³ º");
gotoxy(18,36); cprintf("º ³ ³ º ³ ³ º ³ ³ º");
gotoxy(18,37); cprintf("ÈÍÍÍÍÊÍÍÍÍÊÍÍÍÍÊÍÍÍÍÊÍÍÍÍÊÍÍÍÍÊÍÍÍÍÊÍÍÍÍÊÍÍÍÍ");
textbackground(15);
}
/*************************************************/
void MSG_ERON()
{
int i,j;
textbackground(4);
for(i=23;i<26;i++)
for(j=22;j<60;j++)
{
gotoxy(j,i);
cprintf(" ");
}
textcolor(15);
gotoxy(23,24);
cprintf("Cette grille n'admet pas de solution");
textbackground(1);
}
/*************************************************/
void Cadre_Page()
{
int i,j;
textbackground(0);
textcolor(15);
for(i=1;i<50;i++)
for(j=1;j<81;j++)
{
gotoxy(j,i);
if(i==1||i==49)
cprintf("Í");
else if(j==1||j==80)
cprintf("º");
}
gotoxy(1,1); cprintf("É");
gotoxy(80,1); cprintf("»");
gotoxy(1,49); cprintf("È");
gotoxy(80,49);cprintf("");
}
/*************************************************/
void titres(void)
{
textcolor(6);
gotoxy(20,3);
cprintf(" Ecole Marocaine des Sciences de l'Ing?nieur");
gotoxy(37,6);
textcolor(6+BLINK);
cprintf(" SUDOKU ");
gotoxy(2,7);textcolor(WHITE);cprintf("______________________________________________________________________________");
gotoxy(2,41);textcolor(WHITE);cprintf("______________________________________________________________________________");
gotoxy(10,47);textcolor(15);cprintf(">> Voir solution (V/v)");
gotoxy(50,47);textcolor(15);cprintf(">> Quitter le jeu (Esc)");
}
/*************************************************/
int Controle_Oui(void)
{
char c;
do
{
c=getch();
}while(c!='O'&&c!='o'&&c!='N'&&c!='n'&&c!=27);
return c=='O'||c=='o';
}
/*************************************************/
int Verification(int Mat[][9],int i,int j,int element)
{
int k,a,b,x,y;
x=(i/3)*3;
y=(j/3)*3;
for(k=0;k<9;k++) // test sur la ligne
if( element==Mat[i][k] && j!=k )
return 0;
for(k=0;k<9;k++) // test sur la colone
if( element==Mat[k][j] && i!=k )
return 0;
for(a=x;a<x+3;a++) // test sur la r?gion
for(b=y;b<y+3;b++)
if( element==Mat[a][b] && (a!=i||b!=j) )
return 0;
return 1;
}
/*************************************************/
void Remplissage_Elements_Base(int Mat[][9])
{
int i;
for(i=0;i<nr;i++)
{
gotoxy(21+Tabr[i].cl*5,11+Tabr[i].lg*3);
textcolor(8);
cprintf("%d",Mat[Tabr[i].lg][Tabr[i].cl]);
}
gotoxy(25,44);
textcolor(4);
cprintf(">> Voir d'autres solutions (O/o)");
}
/*************************************************/
int Remplissage(int Mat[][9])
{
int i,j,lg1,cl1,erreur=0;
textcolor(15);
for(i=0,lg1=11;i<9;i++,lg1+=3)
for(j=0,cl1=21;j<9;j++,cl1+=5)
if(Mat[i][j])
{
if( !Verification(Mat,i,j,Mat[i][j]) )
{
textcolor(12);
erreur=1;
}
else
textcolor(0);
gotoxy(cl1,lg1);
cprintf("%d",Mat[i][j]);
}
return erreur;
}
/*************************************************/
int Possibilite(int Mat[][9],int i,int j,int T[])
{
int k,n=0;
for(k=1;k<10;k++)
if( Verification(Mat,i,j,k) )
T[n++]=k;
return n;
}
/*************************************************/
int Position_Case(int Mat[][9],Case Tabv[])
{
int T[9],i,j,n=0;
for(i=0;i<9;i++)
for(j=0;j<9;j++)
if(!Mat[i][j])
{
Tabv[n].lg=i;
Tabv[n].cl=j;
Tabv[n++].nbre_possible=Possibilite(Mat,i,j,T);
}
else
{
Tabr[nr].lg=i;
Tabr[nr++].cl=j;
}
return n;
}
/*************************************************/
int Tri_Insertion(Case Tabv[],int n)
{
int i,j,b;
Case C;
for(i=1;i<n;i++)
{
C=Tabv[i];
j=i-1;
b=0;
while(!b&&j>=0)
{
if( C.nbre_possible<Tabv[j].nbre_possible )
Tabv[j+1]=Tabv[j--];
else
b=1;
}
Tabv[j+1]=C;
}
return 0;
}
/*************************************************/
int Solution(int Mat[][9],Case Tab[],int N,int i)
{
int T[9],j,n;
if(i<N)
{
n=Possibilite(Mat,Tab[i].lg,Tab[i].cl,T);
j=0;
while(j<n)
{
Mat[Tab[i].lg][Tab[i].cl]=T[j++];
if( Solution(Mat,Tab,N,i+1) )
return 1;
}
Mat[Tab[i].lg][Tab[i].cl]=0;
return 0;
}
else
{
trouve=1;
Remplissage(Mat);
Remplissage_Elements_Base(Mat);
return !Controle_Oui();
}
}
/*************************************************/
void gestion()
{
int Mat[9][9]={0};
Case Tabv[81];
int i=0,j=0,cl,lg,nv,ok;
char c;
gotoxy(cl=21,lg=11);
do{
c=getch();
if(!c)
{c=getch();
switch(c)
{
case 72://haut
i--;
lg-=3;
(lg<11)?lg=35,i=8:lg;
break;
case 75://gauche
j--;
cl-=5;
(cl<21)?cl=61,j=8:cl;
break;
case 77://droite
j++;
cl+=5;
(cl>61)?cl=21,j=0:cl;
break;
case 80://bas
i++;
lg+=3;
(lg>37)?lg=11,i=0:lg;
break;
}}
gotoxy(cl,lg);
if(c==83 || c==8){
cprintf(" ");
Mat[i][j]=0;
Remplissage(Mat);
gotoxy(cl,lg);
}
if(c=='v'||c=='V')
{ if( !Remplissage(Mat) )
{
nv=Position_Case(Mat,Tabv);
Tri_Insertion(Tabv,nv);
ok=Solution(Mat,Tabv,nv,0);
if(trouve)
{
if(!ok)
{ gotoxy(32,9);
textcolor(4);
cprintf("\tSolutions termin?es\a");
do{ }while( Controle_Oui() );
}
}
else
{
gotoxy(18,44);
MSG_ERON();
do{ }while( Controle_Oui() );
}
}
else
{
gotoxy(18,44);
gotoxy(80,44);cprintf("º");
MSG_ERON();
do{ }while( Controle_Oui() );
}
}
if(c>='1'&&c<='9')
{
Mat[i][j]=c-'0';
Remplissage(Mat);
gotoxy(cl,lg);
}
}while(c!=27&&c!='V'&&c!='v');
}
//****************** fonction principale *****************//
void main()
{
textbackground(0);
clrscr();
Cadre_Page();
titres();
Grille();
gestion();
}
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.