Résolution d'une grille sudoku

Soyez le premier à donner votre avis sur cette source.

Snippet vu 6 621 fois - Téléchargée 18 fois

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

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

A voir également

Ajouter un commentaire

Commentaires

Messages postés
91
Date d'inscription
samedi 8 mars 2003
Statut
Membre
Dernière intervention
5 août 2010

LOL je met 1 parceque c'est drole.
0 Expert, 0 euristhique....
Messages postés
159
Date d'inscription
lundi 13 juin 2005
Statut
Membre
Dernière intervention
26 février 2009

C'est loin d'être un code "expert"...

D'autre part, le backtrakking pur est assez lourd, il est préférable d'utiliser certaines informations déjà disponibles pour résoudre certaines cases, avant de faire une supposition.

Voir ma source sur les sudoku.

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.