Resolution d'un sudoku en utilisant le backtracking

Télécharger le projet
Commenter

Description

Programme récursif qui résout n'importe qu'elle grille de SUDOKU si cette dernière admet une solution.
Montre les étapes de résolution de la grille, dénombre les possibilités pour chaque étape, et prévient du choix courant, pour un éventuel Backtracking si il s'avère qu'on ait fait le mauvais choix.
Il détecte les fausses grilles (une FAUSSE GRILLE n'admet pas de solution).
Il corrige les grilles erronées (faute de frappe) en faisant ce qui suit :
- Si une ligne contient un chiffre en double, on garde le chiffre le plus à gauche
- Si une colonne contient un chiffre en double, on garde le chiffre le plus en haut
- Si une région un chiffre en double, on garde le chiffre le plus en haut à gauche

ci-joint vous trouverez quelque fichier de test, contenant des grilles pour le tester, mais vous pouvez,éventuellement, créer vos grille en mettant chaque grille dans un fichier texte.

Exemple : (voir diagonale <-grille)
9 0 0 0 0 0 0 0 0
0 8 0 0 0 0 0 0 0
0 0 7 0 0 0 0 0 0
0 0 0 6 0 0 0 0 0
0 0 0 0 5 0 0 0 0
0 0 0 0 0 4 0 0 0
0 0 0 0 0 0 3 0 0
0 0 0 0 0 0 0 2 0
0 0 0 0 0 0 0 0 1

Pour lancer le programme : ./SUDOKU chemin_suivi_du_nom_de_la_grille_à_resoudre

Vous trouverez aussi un makefile, dans le cas où il faudrait recompiler pour générer un nouvel exécutable (make sudoku).

Source / Exemple : 


/**********************************************************\
		|   Resolution d'un SUDOKU en Utilisant le BACKTRACKING    |
		|                                                          |
		|   N.B.:Tout les types qui sont definis dans ce source    |
		|        commencent par une Majuscule			   |
		|        Les constantes sont ecrites en MAJUSCULE	   |
		\**********************************************************/
#include <stdio.h>
#include <stdlib.h>

#define E_OK			  0 /* TOUT VA POUR LE MIEU */
#define E_MAUVAISE_LIGNE	  1 /* LIGNE HORS L'INTERVAL [0,8] */
#define E_MAUVAISE_COLONE	  2 /* COLONE HORS L'INTERVAL [0,8] */
#define E_NUM_EXIST		  3 /* NUM EXISTE DEJA SUR LA MÊME LIGNE,COLONE,OU RÉGION */
#define E_RESOLU		  4 /* GRILLE RESOLUE */
#define E_POSSIBILITES_MANQUANTES 5 /* !!! FAUSSE GRILLE !!! */
#define T_MAX 			  9 /* DIMENSION DE LA GRILLE */
typedef unsigned short CodeCase;

int grille[T_MAX][T_MAX];/* * Matrice qui va contenir la grille aprés lecture du fichier, 


                      
  •  ainsi que le val_retourat final apres resolution dans le cas où

    •                   
  •  la grille n'est pas fausse

    •                   
  • /

/**


     
  •  Fonction qui lit une grille à partir d'un fichier txt

    •  
  • /

void lire_grille(char * chemin) { 
	int i,j;
	FILE * source;
	source = fopen(chemin,"r");
	for (i = 0; i < T_MAX; i++)
	{
		for(j= 0; j < T_MAX; j++)
		{
			fscanf(source,"%d",&grille[i][j]);
		}
	}
	fclose(source);
}

/**


     
  •  Fonction qui initialise toutes les cases la matrice T_MAXxT_MAX representant la grille à 0

    •  
  • /

void zero_matrice( int a[T_MAX][T_MAX] ) {
	int ligne, col;
	for ( ligne = 0; ligne < T_MAX; ligne++ )
		for ( col = 0; col < T_MAX; col++ ) a[ligne][col] = 0;
}
/**


     
  •  Crée un mask à partir d'un des numéros de la grille passé en parametre

    •  
  •  puis l'applique à la grille contenant les CodeCases equivallents à chacun

    •  
  •  des composants, en faisant un OU (OR) logique bit par bit avec l'ancienne

    •  
  •  valeur contenue dans la case p[ligne][col]

    •  
  • /

void set_possible( CodeCase p[T_MAX][T_MAX], int ligne, int col, int num ) {
	CodeCase mask;
	mask = 1 << ( num - 1 );
	p[ligne][col] |= mask;
}
/**


     
  •  Crée un mask à partir d'un des numéros de la grille passé en parametre

    •  
  •  puis l'applique à la grille contenant les CodeCases equivallents à chacun

    •  
  •  des composants, en faisant un ET (AND) logique bit par bit avec l'ancienne

    •  
  •  valeur contenue dans la case p[ligne][col] et le complement à un du mask 

    •  
  •  calculé

    •  
  • /

void set_impossible( CodeCase p[T_MAX][T_MAX], int ligne, int col, int num ) {
	CodeCase mask;
	mask = 1 << ( num - 1 );
	p[ligne][col] &= ~mask;
}
/**


     
  •  Calcul un mask à partir d'un numéro passé en parametre pour faire un ET logique

    •  
  •  entre ce dernier et le CodeCase p[ligne][col] ainsi on peut savoir si la case

    •  
  •  (ligne,col) de la grille peut prendre la valeur num (on retourne 1) 

    •  
  •                                                ou pas(on retourne 0)

    •  
  • /

int est_possible(CodeCase p[T_MAX][T_MAX], int ligne, int col, int num ) {
	CodeCase mask;
	mask = 1 << ( num - 1 );
	if ( p[ligne][col] & mask ) return( 1 );
	return ( 0 );
}
/**


     
  •  fonction qui retourne le nombre de possiblilité que peut prendre la case

    •  
  •  p[ligne][col], ce qui correspond au poid binaire, 

    •  
  •  N.B. On travaille sur la partie basse des 2 octets

    •  
  • /

int poidbinaire( CodeCase p[T_MAX][T_MAX], int ligne, int col ) {
	CodeCase mask;
	int compt;
	compt = 0;
	mask = 1 << 8;	
	while( mask ) 
	{
	 if ( mask & p[ligne][col] ) compt++;
	 mask >>= 1;
	}
	return( compt );
}
/**


     
  •  Regles des Candidats double appliquée aux lignes

    •  
  • /

void l_candidat_double(CodeCase p[T_MAX][T_MAX]) 
{
  int i, j, k, l, cpt;
  CodeCase tmp;
  for (i = 0 ; i < T_MAX ; i++) {
    for (l = 0 ; l < T_MAX  ; l++) {
      cpt = 0; // initialisation du compteur
      tmp = 0;  // contiendra la valeur de la case qui n'autorise que 2 valeurs
      /* Si la case n'autorise que 2 valeurs */
      if ( poidbinaire(p,i,l) == 2 ) {
        tmp = p[i][l]; // on sauve la valeur de la case
        for ( j = l ; j < T_MAX  ; j++)
          if ( p[i][j] == tmp )
            cpt++; // on incrémente le compteur si un case n'autorise que les 2 même valeurs
      }
      /* Si il n'y a que 2 cases n'autirisant les 2 même valeurs */
      if ( cpt == 2 ) {
        for (k = 0; k < T_MAX  ; k++) {
          /* On entre dans la condition if uniquement si la valeur de la case va être modifée */
          if ( (p[i][k] != tmp) && (p[i][k] != (p[i][k] & ~tmp)) ) {
            p[i][k] &= ~tmp; // on interdit les valeurs aux autres cases du bloc
          }
        }
      }
    }
  }
}
/**


     
  •  Regles des Candidats double appliquée aux colones

    •  
  • /

void c_candidat_double(CodeCase p[T_MAX][T_MAX]) 
{
  int i, j, k, l, cpt;
  CodeCase tmp;
  for (i = 0 ; i < T_MAX ; i++) {
    for (l = 0 ; l < T_MAX  ; l++) {
      cpt = 0; // initialisation du compteur
      tmp = 0;  // contiendra la valeur de la case qui n'autorise que 2 valeurs
      /* Si la case n'autorise que 2 valeurs */
      if ( poidbinaire(p,l,i) == 2 ) {
        tmp = p[l][i]; // on sauve la valeur de la case
        for ( j = i ; j < T_MAX  ; j++)
          if ( p[l][j] == tmp )
            cpt++; // on incrémente le compteur si un case n'autorise que les 2 même valeurs
      }
      /* Si il n'y a que 2 cases n'autirisant les 2 même valeurs */
      if ( cpt == 2 ) {
        for (k = 0; k < T_MAX  ; k++) {
          /* On entre dans la condition if uniquement si la valeur de la case va être modifée */
          if ( (p[l][k] != tmp) && (p[l][k] != (p[l][k] & ~tmp)) ) {
            p[l][k] &= ~tmp; // on interdit les valeurs aux autres cases du bloc
          }
        }
      }
    }
  }
}
/**


     
  •  Regles des Candidats double appliquée aux Régions

    •  
  • /

void r_candidat_double(CodeCase p[9][9]) 
{
  int i, j, k, l, cpt, r_ligne_debut, r_col_debut;
  CodeCase tmp;
  for ( i = 0 ; i < r_ligne_debut + 3; i++ ) {
     for ( l = 0; l < r_col_debut + 3; l++ ) {
		r_ligne_debut = (int)(i/3)*3;
		r_col_debut = (int)(l/3)*3;
		cpt = 0; // initialisation du compteur
		tmp = 0; // contiendra la valeur de la case qui n'autorise que 2 valeurs
		/* Si la case n'autorise que 2 valeurs */
	        if ( poidbinaire(p,i,l) == 2 ) {
        		tmp = p[i][l]; // on sauve la valeur de la case
        		for ( j = l ; j < l+3  ; j++)
          			if ( p[i][j] == tmp )
            			cpt++; // on incrémente le compteur si une case n'autorise que les 2 même valeurs
      		}
      /* Si il n'y a que 2 cases n'autirisant les 2 même valeurs */
      if ( cpt == 2 ) {
        for (k = 0; k < r_col_debut ; k++) {
          /* On entre dans la condition if uniquement si la valeur de la case va être modifée */
          if ( (p[i][k] != tmp) && (p[i][k] != (p[i][k] & ~tmp)) ) {
            p[i][k] &= ~tmp; // on interdit les valeurs aux autres cases du bloc
          }
        }
      }
    }
  }
}
/**


     
  •  fonction qui remplit la grille p[T_MAX][T_MAX] avec le code equivalents aux num.

    •  
  •  c'est sur cette nouvelle grille que se feront toutes les operations

    •  
  •  quand on trouve le bon num correspondant à une case ,

    •  
  •  on met le CodeCase qui lui correspondant à 0 

    •  
  • /

void figure_possibles( int a[T_MAX][T_MAX], CodeCase p[T_MAX][T_MAX] ) {
	int ligne, col;
	int num;
	int i;
	int carre_ligne, carre_col;
	int carre_ligne_debut, carre_col_debut;

	for ( ligne = 0; ligne < T_MAX; ligne++ )
		for ( col = 0; col < T_MAX; col++ )
		{
			p[ligne][col] = 0;
			for ( num = 1; num <= T_MAX; num++ )
				set_possible( p, ligne, col, num );
		}

	for ( ligne = 0; ligne < T_MAX; ligne++ )
		for ( col = 0; col < T_MAX; col++ )
		{
			num = a[ligne][col];
			
			if (num == 0) continue;
			
			for ( i = 1; i <= T_MAX; i++ )
				set_impossible( p, ligne, col, i );

			for ( i = 0; i < T_MAX; i++ )
				set_impossible( p, ligne, i, num );

			for ( i = 0; i < T_MAX; i++ )
				set_impossible( p, i, col, num );

			carre_ligne_debut = (int)(ligne/3)*3;/** 


    							      
  •  si ligne dans l'interval [0,2] alors carre_ligne_debut <- 0

    • 						 	      
  •  si ligne dans l'interval [3,5] alors carre_ligne_debut <- 3

    • 		                                              
  •  si ligne dans l'interval [6,8] alors carre_ligne_debut <- 6

    • 					      		      
  • /

			carre_col_debut = (int)(col/3)*3;/* de meme pour carre_col_debut */

			for ( carre_ligne = carre_ligne_debut; carre_ligne < carre_ligne_debut + 3; carre_ligne++ )
				for ( carre_col = carre_col_debut; carre_col < carre_col_debut + 3; carre_col++ )
					set_impossible( p, carre_ligne, carre_col, num );
		}
}
/**


     
  •  Affichage de la grille

    •  
  • /

void afficher_matrice( int a[T_MAX][T_MAX] ) {
	int ligne, col;
	CodeCase p[T_MAX][T_MAX];
	figure_possibles( a, p );
	printf("\033[1;33m\033[40m ------ ------ ------ \033[0m\n");// Bordure superieure de la grille
	for ( ligne = 0; ligne < T_MAX; ligne++)
	{       
		for ( col = 0; col < T_MAX; col++ )
		{	
			if (col == 0) printf("\033[1;33m\033[40m|\033[0m");// Bordure Gauche de la grille
			if ( a[ligne][col] )
				printf( " %d", a[ligne][col] );
			else
				printf( "  " );
			if ((col+1)%3 == 0) printf("\033[1;33m\033[40m|\033[0m");// Separateur vertical des Régions
		}
		printf( "\n" );
		if ((ligne+1)%3 == 0) printf("\033[1;33m\033[40m ------ ------ ------ \033[0m\n");//Separateur horizontal des Régions
	}
	printf( "\n" );
}
/**


     
  •  met la la case(ligne,col) de la grille temporaire "a" à num

    •  
  •  verifie que ligne appartient à l'interval [0,8]

    •  
  •  que col appartient à l'interval [0,8], aussi si la case contient 

    •  
  •  déjà cette valeur

    •  
  • /

int set_case_grille( int a[T_MAX][T_MAX], int ligne, int col, int num ) {
	int i;
	int carre_ligne, carre_col;
	int carre_ligne_debut, carre_col_debut;

	if (( ligne < 0 ) || ( ligne > 8 )) return( E_MAUVAISE_LIGNE );

	if (( col < 0 ) || ( col > 8 )) return ( E_MAUVAISE_COLONE );

	for ( i = 0; i < T_MAX; i++ )
		if ( num == a[ligne][i] ) return ( E_NUM_EXIST );

	for ( i = 0; i < T_MAX; i++ )
		if ( num == a[i][col] ) return ( E_NUM_EXIST );

	carre_ligne_debut = (int)(ligne/3)*3; /**


    					       
  •  si ligne dans l'interval [0,2] alors carre_ligne_debut <- 0

    • 					       
  •  si ligne dans l'interval [3,5] alors carre_ligne_debut <- 3

    • 					       
  •  si ligne dans l'interval [6,8] alors carre_ligne_debut <- 6

    • 					       
  • /

	carre_col_debut = (int)(col/3)*3; /* de meme pour carre_col_debut */
	
	for ( carre_ligne = carre_ligne_debut ; carre_ligne < carre_ligne_debut + 3; carre_ligne++ )//
		for ( carre_col = carre_col_debut; carre_col < carre_col_debut + 3; carre_col++ )   // Verification d'une région pour savoir si le num
			if ( num == a[carre_ligne][carre_col] ) return( E_NUM_EXIST );		    // passé en parametre appartient ou pas à cette région
												    //
	a[ligne][col] = num;// Les 3 Conditions de bases sont remplies -> on met "num" dans grille(ligne,col)
	return( E_OK );
}
/**


     
  •  Fait une copie de la grille lue à partir d'un fichier dans une autre grille "a[T_MAX][T_MAX]"

    •  
  •  Cela permet de verifier qu'il n'y a pas d'erreur de saisie dans le fichier txt qui

    •  
  •  contient la grille.

    •  
  •  Ce qu'on qualifie d'erreur de saisie, c'est une rededanse d'un numéro sur la même ligne,

    •  
  •  la même colone, ou d'une même région. Si c'est le cas on enleve celui ou ceux qui est/sont

    •  
  •  le plus à gauche et le plus en bas, car la lecture de la grille se fait de haut en bas 

    •  
  •  et de gauche à droite

    •  
  • /

int charger_grille( int a[T_MAX][T_MAX], int grille[T_MAX][T_MAX] )
{
	int ligne, col;
	int val_retour;
	zero_matrice(a);
	for ( ligne = 0; ligne < T_MAX; ligne++ )
		for ( col = 0; col < T_MAX; col++ )
			if ( grille[ligne][col] ) // Si grille(ligne,col) != 0
			{	
				val_retour = set_case_grille( a, ligne, col, grille[ligne][col] );
				if ( E_OK != val_retour )
				{
					printf( "La case(%d,%d)contenant %d a provoqué l'erreur %d.\n",ligne, col, grille[ligne][col], val_retour );
					return( val_retour );
				}
			}
	return( E_OK );
}
/**


     
  •  Retourne le Min(des possiblilites) entre tous les CodeCases

    •  
  • /

int trouver_plus_petit( CodeCase p[T_MAX][T_MAX], int *p_ligne, int *p_col )
{
	int	ligne, col;
	int	compt;
	int	plus_petit_possible;

	plus_petit_possible = 10;
	for ( ligne = 0; ligne < T_MAX; ligne++ )
		for ( col = 0; col < T_MAX; col++ )
		{
			compt = poidbinaire( p, ligne, col );
			if (( compt ) && ( compt < plus_petit_possible ))
			{
				plus_petit_possible = compt;


    				
  • p_ligne = ligne;

    • 				
  • p_col = col;

			}
		}
	if ( plus_petit_possible > T_MAX )
		plus_petit_possible = 0;
		
	return( plus_petit_possible );
}
/**


     
  •  Fonction recursive qui s'occupe de la résolution du SUDOKU, renvoie : 

    •  
  •        E_OK == "0" encas d'erreur

    •  
  •  	 E_POSSIBLILITES_MANQUANTES == "5" si la grille est fausse

    •  
  • 	 E_RESOLU == "4" si la grille admet une solution

    •  
  •  Parametres de la Fonction : 

    •  
  •  	nbr_appel_rec : nombre de fois qu'on execute cette fonction

    •  
  • 	a[T_MAX][T_MAX] : Grille sudoku à resoudre

    •  
  • 	set_ligne: la ligne à laquelle on va toucher

    •  
  • 	set_col : la colone à laquelle on va toucher

    •  
  • 	set_num : le numero qu'on va appliquer à la case(set_ligne,set_col)

    •  
  • /  

int resolution_grille( int nbr_appel_rec, int a[T_MAX][T_MAX], int set_ligne, int set_col, int set_num ) {
	int	 ligne, col;
	int	 compt;
	int	 num;
	int	 val_retour;
	int	 h[T_MAX][T_MAX];
	CodeCase p[T_MAX][T_MAX];
	
	for ( ligne = 0; ligne < T_MAX; ligne++ )     //
		for ( col = 0; col < T_MAX; col++ )   //On dupplique la grille passer en parametre
			h[ligne][col] = a[ligne][col];// 
						       
	if ( set_num )
	{
		val_retour = set_case_grille( h, set_ligne, set_col, set_num );
		if ( E_OK != val_retour ) return( val_retour );// Si on a pas pu mettre set_num dans la 
							       // grille_temporaire(set_ligne,set_col)
							       // On indique la raison,ici la Valeur de retour
	}

	printf( "Etape %d, la case(%d,%d)<-%d:\n",nbr_appel_rec, set_ligne+1, set_col+1, set_num );
	afficher_matrice( h );   // On affiche la grille temporaire
	figure_possibles( h, p );// Mise à jour de la matrice des CodeCases parrapport à la grille_temporaire
	l_candidat_double(p);//
	c_candidat_double(p);// On applique la regle des candidats double pour les lignes colones et les régions
	r_candidat_double(p);// 
	for ( ligne = 0; ligne < T_MAX; ligne++ )
		for ( col = 0; col < T_MAX; col++ )
			if (( 0 == h[ligne][col] ) && ( 0 == poidbinaire( p, ligne, col )))
				return( E_POSSIBILITES_MANQUANTES );/* IMPLIQUE LA GRILLE EST FAUSSE !!! */

	/* On cherche la nouvelle case qui a le moins de possiblilité */
	compt = trouver_plus_petit( p, &ligne, &col );
	if ( compt < 1 )/* Plus rien à faire */
	{
		for ( ligne = 0; ligne < T_MAX; ligne++ )	    //
			for ( col = 0; col < T_MAX; col++ )	    // On copie la grille temporaire dans la grille
				grille[ligne][col] = h[ligne][col]; //
		return( E_RESOLU ); // Travail fini
	}
	/* Pour Grilletemporaire(ligne,col) Si le nombres de possiblilites == 1 -> possibilite sinon possiblilites */
	printf( "MIN(des possiblilites) : La case (%d,%d) a %d possibilit%s\n",ligne+1, col+1, compt, ( compt == 1 ) ? "e" : "es");
	for ( num = 1; num <= T_MAX; num++ )            //
		if ( est_possible( p, ligne, col, num ))// On teste sur la grille des CodeCases ,si num peut être mi dans grilletemporaire(ligne,col)  
		{					// Si oui, on continue avec num en le mettant dans la grille a(ligne,col)
							// On contiue à travailler sur la Grille temporaire "h" au lieu de "a", ce qui nous permet 
							// de revenir sur nos pas "Backtracker" dans le cas où on a plusieurs possibilités et qu'on
							// s'est engagé sur la mauvaise.
			val_retour = resolution_grille( nbr_appel_rec + 1, h, ligne, col, num );// Appel recursif de la fonction resolution 
												// avec la grille temporaire "h" comme parametre
			if ( E_RESOLU == val_retour ) break;
		}
	return( val_retour );
}

int tester( int grille[T_MAX][T_MAX] )
{
	int	val_retour;
	int	a[T_MAX][T_MAX];
	charger_grille( a, grille );
	printf( "\033[0;34m\033[40m.::GRILLE CHARGEE::.\033[0m\n" );
	afficher_matrice( a );
	val_retour = resolution_grille( 0, a, 0, 0, 0 );
	if ( E_RESOLU == val_retour )
		printf( "\033[1;32m\033[40m .::GRILLE RESOLU::.\033[0m\n" );
	else
		printf( "\033[0;31m\033[40m !! ERREUR !!\033[0m%s \n",(val_retour == E_POSSIBILITES_MANQUANTES) ? " FAUSSE GRILLE " : " ");
	afficher_matrice( grille );
	return( val_retour );
}

int main( int argc, char *argv[] ) {
	int val_retour;
	if (argc < 2) { 
		printf(" \n\n\t\033[0;31m\033[40mECHEC DU LANCEMENDE DU PROGRAMME : PARAMETRE D'APPEL INSUFFISANT !!\033[0m \n Veuillez relancer le programme en lui donnant un fichier txt contenant la grille à resoudre \n");
		printf(" Exemple : \033[0;34m\033[40m ./SUDOKU grille \033[0m:Si la Grille se trouve dans le même dossier que SUDOKU\n");
		printf(" Sinon   : \033[0;34m\033[40m ./SUDOKU chemin_ou_se_trouve_la_grille/grille \033[0m\n\n\n");
		return (0);
	}
	lire_grille(argv[1]);
	val_retour = tester(grille);
	return( 0 );
}
Télécharger le projet

Codes Sources

A voir également

S'inscrire maintenant

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.