RÉSOLUTION D'UNE GRILLE SUDOKU

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