[c] mon solveur de sudoku Fermé

Question

bonjour voila je dois realiser mon propre solveur de sudoku^^" tache assez hasardeuse pour un novice de la programmation meme si je pourrai me rendre la tache plus facile en en utilisant un tout fait ^^ je prefere le concevoir par moi meme pour comprendre plus facilement ce dernier voici mon code

#include<stdio.h>
#include<stdlib.h>

//definition Grille sudoku carré 3*3 de regions comportant 3*3 case de 10 candidats potentiels
typedef int grille[3][3][3][3][10];




//initialisation des regions du sudoku ainsi que des candidats
void initialisation_grille(grille X)
     {
     int i,j,x,y,z;
     for(z=0;z<=9;z++){
                       for(i=0;i<=2;i++)
                                        {
                                         for(j=0;j<=2;j++)
                                                          {
                                                           for(x=0;x<=2;x++)
                                                                           {
                                                                            for(y=0;y<=2;y++)
                                                                                             X[i][j][x][y][z]=0;
                                                                            }
                                                          }
                                                       
                                        }
                       }                 
     }
 

 
     
//affichage de la griffe de sudoku prealablement mise a 0 + mise en forme tel une grille     
void affichage_grille(grille X)
     {
	 int i,j,x,y,z;
	 printf("                          +---+---+---+\n                          ");
     for(j=0;j<=2;j++){
                       for(y=0;y<=2;y++){
                                          for(i=0;i<=2;i++){
                                                            for(x=0;x<=2;x++){
                                                                              if(x==0 )printf("|");
                                                                              printf("%d",X[i][j][x][y][0]);
                                                                              }
                                                           }
                                        printf("|\n                          ");
                                        if(y==2)
                                                printf("+---+---+---+\n                          "); 
                                        }
                      }
    }
    



    
//remplissage sudoku avec condition d'acces
void remplissage_grille(grille X)
     {/*
     char continuer;
     int i,j,x,y;
     
     printf("\n\n******Remplissage de la grille de sudoku******\n");
     
     do{
        
        do{
           printf("\nEntrez tout d'abord les coordonnees de la region(col_lig)\n");
           scanf("%d %d",&x,&y);
           }while((x<0 || x>2) || (y<0 || y>2));
        
        do{
           printf("\nEntrez ensuite les coordonnees de la case(col_lig)\n");
           scanf("%d %d",&i,&j);
           }while((i<0 || i>2) || (j<0 || j>2));
        
        do{
           printf("\nEntrez maintenant la valeur a affecter\n");
           scanf("%d",&X[x][y][i][j][0]);
           }while(X[x][y][i][j][0]<1 || X[x][y][i][j][0]>9);
        
        printf("\nPour continuer le remplissage de la grille entrer y\n");
        scanf("%c",&continuer);
        scanf("%c",&continuer);
        
        }while(continuer=='y');
     
     printf("\n******Remplissage termine avec succes******\n");
   */
/*X[1][0][1][0][0]=2;
X[1][0][2][0][0]=4;
X[2][0][2][0][0]=5;
X[0][0][1][1][0]=8;
X[0][0][2][1][0]=2;
X[1][0][0][1][0]=5;
X[1][0][1][1][0]=7;
X[1][0][2][1][0]=3;
X[2][0][1][1][0]=4;
X[2][0][2][1][0]=1;
X[0][0][2][2][0]=4;
X[1][0][0][2][0]=1;
X[1][0][1][2][0]=6;
X[1][0][2][2][0]=8;
X[2][0][2][2][0]=3;
X[0][1][0][0][0]=6;
X[1][1][0][0][0]=2;
X[1][1][1][0][0]=8;
X[0][1][1][1][0]=9;
X[1][1][2][1][0]=7;
X[2][1][1][1][0]=1;
X[2][1][2][1][0]=2;
X[0][1][1][2][0]=3;
X[2][1][1][2][0]=6;
X[2][1][2][2][0]=8;
X[0][2][0][0][0]=3;*/
X[0][2][2][0][0]=6;
X[0][2][0][1][0]=8;
X[0][2][1][1][0]=5;
X[0][2][1][2][0]=4;
X[1][2][2][0][0]=1;
X[1][2][2][1][0]=2;
X[2][2][2][0][0]=4;
X[2][2][0][2][0]=3;
X[2][2][1][2][0]=2;     

}


    
    
     
//verifie si un chiffre "chiffre" figure dans une ligne "lig" exepté la colonne de la case choisit
int existe_ligne(grille X,int reg_lig,int lig,int reg_col, int col,int chiffre)
    {int x,i;
    for(x=0;x<=2;x++){
                      for(i=0;i<=2;i++)
                                        if((x!=reg_col || i!=col) && X[x][reg_lig][i][lig][0]==chiffre)
                                        return 1;
                                        
                      }
    
    
    return 0;
    
    }

//verifie si un chiffre "chiffre" figure dans une ligne "lig" exepté la colonne de la case choisit
int existe_lignebis(grille X,int reg_lig,int lig,int reg_col, int col,int chiffre)
    {int x,i,k;
    for(x=0;x<=2;x++){
                      for(i=0;i<=2;i++)
                                       {
                                                         
                                                         if((x!=reg_col || i!=col) && X[x][reg_lig][i][lig][chiffre]==1 )
                                                         return 1;
                    }                                    }
    
    
    return 0;
    
    }


    
//verifie si un chiffre "chiffre" figure dans une colonne "col" exepté la ligne de la case choisit
int existe_colonne(grille X,int reg_lig,int lig, int reg_col, int col, int chiffre)
    {int y,j,k;
    for(y=0;y<=2;y++){
                      for(j=0;j<=2;j++)
                                       if((y!=reg_lig || j!=lig) && X[reg_col][y][col][j][0]==chiffre)
                                       return 1;
                                       
                      }
    return 0;
    
    }

//verifie si un chiffre "chiffre" figure dans une colonne "col" exepté la ligne de la case choisit
int existe_colonnebis(grille X,int reg_lig,int lig, int reg_col, int col, int chiffre)
    {int y,j,k;
    for(y=0;y<=2;y++){
                      for(j=0;j<=2;j++)
                                        {
                                                          
                                                          if((y!=reg_lig || j!=lig) && X[reg_col][y][col][j][chiffre]==1  )
                                                          return 1;
                                       
                                                           }                
                                         
                      }
    return 0;
    
    }



//verifie si un chiffre figure dans la region passé en parametre d'entré
int existe_region(grille X,int reg_lig,int lig, int reg_col, int col, int chiffre)
    {int i,j,k;
    for(i=0;i<=2;i++)
                     for(j=0;j<=2;j++)
                                      if(X[reg_col][reg_lig][i][j][0]==chiffre && (i!=col || j!=lig))
                                      return 1;
                                                                   
    return 0;}    

//verifie si un chiffre figure dans la region passé en parametre d'entré
int existe_regionbis(grille X,int reg_lig,int lig, int reg_col, int col, int chiffre)
    {int i,j,k;
    for(i=0;i<=2;i++)
                    { for(j=0;j<=2;j++)
                                       {
                                                         if( (i!=col || j!=lig) && X[reg_col][reg_lig][i][j][chiffre]==1 )
                                                         return 1;
                                                         }                                      
                                       
                    }
    return 0;
    }  


    
//verifie si la grille est partiellement remplissable 
int resolver_grille(grille X)
    {int i,j,y,x;
    
     for(i=0;i<=2;i++)
                     {
                     for(j=0;j<=2;j++)
                                      {
                                      for(x=0;x<=2;x++)
                                                      {
                                                      for(y=0;y<=2;y++){
                                                                       if(X[x][y][i][j][0]==0 || 
                                                                       existe_ligne(X,y,j,x,i,X[x][y][i][j][0]) || 
                                                                       existe_colonne(X,y,j,x,i,X[x][y][i][j][0]) || 
                                                                       existe_region(X,y,j,x,i,X[x][y][i][j][0]))
                                                                       {return 0;}
                                                                       }    
                                                      }
                                                       
                                        }
                       }
      return 1;                 
     }
     
//compte les possibilités des valeurs pour une case données     
int cpt_poss(int reg_lig, int reg_col, grille X, int col, int lig)
{
    int k,result=0;

    for(k=1;k<10;k++)
    {
        if(X[reg_col][reg_lig][col][lig][k]==1) 
        result++;
    }

    return result;
}




//retourne la premiere possibilitées d'une case(la seul si il y en a qu'une)
int seul_poss(int lig, int col,grille X,int reg_col,int reg_lig)
{
    int k;

    for(k=1;k<10;k++)
    {
        if(X[reg_col][reg_lig][col][lig][k]!=0) return k;
    }

    return 0;
}




//si une possibilitées affectation a la variable
int simplification_seul_poss(grille X)
{
    int i,j,x,y,result = 0;

for(x=0;x<=2;x++)
                 {for(y=0;y<=2;y++)
                                   {for(i=0; i < 3; i++)
                                                       {
                                                       for(j = 0; j < 3; j++)
                                                                             {
                                                                             if(cpt_poss(y,x,X,i,j)==1 && X[x][y][i][j][0]==0)
                                                                            {
                                                                            X[x][y][i][j][0] = seul_poss(j,i,X,x,y);
                                                                            result = 1;
                                                                            }
                                                                             }                                                                            
                                                       }
                                   }
                 }                  
    return result;
}



void poss(grille X) /*défini les possibilités pour chaque case*/
{
int i,j,x,y,k;
for(x=0;x<=2;x++){
                  for(y=0;y<=2;y++){
                                    for(i=0;i<3;i++)
                                                    {
                                                    for(j=0;j<3;j++)
                                                                    {
                                                                    if(X[x][y][i][j][0]==0)
                                                                                          {
	                                                                                      for(k=1;k<10;k++)
                                                                                                           {
                                                                                                           if(existe_ligne(X,y,j,x,i,k) || 
                                                                                                           existe_colonne(X,y,j,x,i,k) || 
                                                                                                           existe_region(X,y,j,x,i,k))
                                                                                                           X[x][y][i][j][k]=0;
	                                                                                                       else
                                                                                                           X[x][y][i][j][k]=1;
                                                                                                           }
                                                                                          }
                                                                    }
                                                    }
                                    }
                  }
}


//procedure permettant de determiner le candidats parmis plusieurs parmis n candidats possible en utilisant une methode mathematiques
void une_seul_possible_parmis_plusieurs_candidats(grille X) 
     {
     int i,j,x,y,z;
     
                       for(x=0;x<=2;x++)
                                        {
                                         for(y=0;y<=2;y++)
                                                          {
                                                           for(i=0;i<=2;i++)
                                                                           {
                                                                            for(j=0;j<=2;j++)
                                                                                             {for(z=1;z<=9;z++)
                                                                                                               {
                                                                                                               if(X[x][y][i][j][z]==1 && X[x][y][i][j][0]==0)
                                                                                                                                            {
                                                                                                                                             if((existe_lignebis(X,y,j,x,i,z)==0 || 
                                                                                                                                             existe_colonnebis(X,y,j,x,i,z)==0 || 
                                                                                                                                             existe_regionbis(X,y,j,x,i,z)==0))
                                                                                                                                             X[x][y][i][j][0]=z;             
                                                                                                                                                          
                                                                                                                                                          
                                                                                                                                                          
                                                                                                                                            }              
                                                                                                           
                                                                                                           
                                                                                                           
                                                                                                           }
                                                                                             }
                                                                            }
                                                       
                                                            }
                                         }                 
     }
     


int recup_position(grille X,int *i,int *j,int *x, int *y)
{
  for(*x=0;*x<=2;*x++)
                {
                for(*y=0;*y<=2;*y++)
                                 {
                                 for(*i=0;*i<=2;*i++)
                                                  {
                                                  for(*j=0;*j<=2;*j++)
                                                                   { 
                                                                   if(X[*x][*y][*i][*j][0]==0)
                                                                                              
                                                                                              return 1;   
                                                                                              
                                                                   }
                                                  }
                                 }
                }
                
  }     

//creer un tableau de possibilité pour un case donné non_determiné finissant par 0     
void toutes_poss_case(grille X,int x, int y, int i, int j,int Poss[11])
{int k;
     Poss[0]=0;
   for(k=1;k<10;k++)
                    {
                    if(existe_ligne(X,y,j,x,i,k) || 
                    existe_colonne(X,y,j,x,i,k) || 
                    existe_region(X,y,j,x,i,k))
                    Poss[k]=0;
                    else
                    Poss[k]=1;
                    }   
Poss[10]=0;
}

void sauvegarde(grille X,grille Sauve)
{ int x, y , i ,j ,z;
     
                         for(x=0;x<=2;x++)
                                        {
                                         for(y=0;y<=2;y++)
                                                          {
                                                           for(i=0;i<=2;i++)
                                                                           {
                                                                            for(j=0;j<=2;j++)
                                                                                             {for(z=0;z<=9;z++)
                                                                                                               {Sauve[x][y][i][j][z]=X[x][y][i][j][z];}
                                                                                             }
                                                                            }
                                                           }
                                         }
}                  
     

//procedure generatrice de solution
void resoudre(grille X)
{int cpt=0,modif=1;
int i,j,x,y,Poss_case[11],k;
grille sauvegard;                                           
while(resolver_grille(X)!=1   && modif!=0)
                              {poss(X);
                              modif=simplification_seul_poss(X);
                              }
if(resolver_grille(X)!=1)                                                                   
{recup_position(X,&i,&j,&x,&y);
toutes_poss_case(X,x,y,i,j,Poss_case);
k=0;
while(resolver_grille(X)!=1 )                                                                  
{k++;
while(Poss_case[k]!=0 && k<11){
sauvegarde(X,sauvegard);

sauvegard[x][y][i][j][0]=Poss_case[k];
resoudre(sauvegard);
if(resolver_grille(sauvegard))
                              sauvegarde(sauvegard,X);
k++;
}}
}   
}

//prototype procedure presentation     
void auteur_et_presentation();
     
// fonction principale
int main()
      {
      grille X;
      auteur_et_presentation();
      initialisation_grille(X);
      remplissage_grille(X);
      printf("\n\n                ******AFFICHAGE GRILLE INITIALE******\n\n");
      affichage_grille(X);
      resoudre(X);
      printf("\n\n                ******AFFICHAGE GRILLE RESOLUE******\n\n");
      affichage_grille(X);
      printf("\n\n");
      system("pause");
      }

voila le probleme il resout les sudoku dit facile mais il il ne resoud pas les diabolique il me renvoie un erreur au nivo de la recurence pouvez m'eclairai a ce niveau

mamiemando · Answer

Hum bon en fait je ne vais pas te faire un cours de recherche opérationnelle mais le sudoku est un problème assez trivial de satisfaction de contrainte (problème CSP). Un CSP se définit par trois ensembles (X,D,C) :

- X : les variables : ici les nombres associés à chaque case, en gros ta matrice de sudoku. X = {X00,X01,...X09,X10,...,X19,....X99}

- D : les domaines de chaque variables. Les domaines des cases initialisées sont de taille 1 (la valeur de la case), les autres domaines étant {1,2,...,9}

- C : les contraintes, qui définissent les règles du sudoku (un seul nombre dans un carré de 9, dans une ligne, et dans une colonne). Ca donne des contraintes du genre :
Xi0 != Xi1 != ... != Xi9 pour tout i de 0 à 9
X0i != X1i != ... != X9i pour tout i de 0 à 9
X01 != X02 !=X03 != X10 != X12 != X13 !=X20 != X22 != X23 (idem pour les autres carrés)

Phase de présolve

A ce stade on peut réduire certains domaines grâce à tes contraintes. Par exemple si dans ma grille de départ j'ai un 2 qui est placé, je peux
- supprimer cette valeur de tous les domaines des variables associées à cette ligne
- supprimer cette valeur de tous les domaines des variables associées à cette colonne
- cette valeur de tous les domaines des variables associées à ce carré.

Ensuite tu marques cette case comme traitée et tu répètes la procédure pour toutes les cases ayant un domaine de taille 1 qui ne sont pas encore marquées. A ce stade il y aura pas mal de cases qui se seront remplies. Les cases "survivantes" seront celle ou un doute subsiste (noeud de branchement).

Phase de résolution

Là il y a deux possilibités, mais tu risques de devoir lire un peu de littérature sur la recherche opérationnelle. 

1) Soit tu explores toutes les solutions restantes avec une procédure récursive (en effectuant les réductions de domaines à chaque itération) (Branch and Bound). C'est assez coûteux en terme de mémoire et de performance mais ca permet de trouver toutes les solutions admissibles ou de prouver qu'il n'en existe aucune. En particulier il faudra retenir les configurations des noeuds au cas ou une branche de l'arbre de recherche ne mène pas à une solution. Etant donné que ce sont de tout petits problèmes cette solution est envisageable.

2) Soit tu pars du principe qu'il en existe une et tu fais une méthode de recherche locale (genre un tabu search).

Bonne chance

kilian · Answer

Je pense que c'est plus simple avec du "backtracking", à savoir réunir l'ensemble de solutions possibles pour chaque case compte tenu des valeurs déjà définies pour les autres et revenir en arrière si ça ne va plus. 

On part du principe que la première des solutions possibles pour la case courante est la bonne, on fait la même chose pour la suivante. Si pour la suivante on a pas de solution possible, alors on revient à la case précédente et on prend la solution possible suivante, s'il n'y en a pas non plus, on revient encore à la case précédente etc...

C'est à mon avis la manière la plus simple et la plus concise pour écrire un solveur de sudoku...

Et pour celà, il suffit d'un tableau à deux dimensions de 9x9. Ce qui permet de limiter les boucles imbriquées avec des for dans des for dans des for etc...

kilian · Answer

En même temps je dis ça aussi parce que j'avais de très mauvaises notes en recherche opérationnelle ;-)

mamiemando · Answer

Ca s'appelle un branch and bound ca kilian :) C'est la solution n°1 que j'ai donné en phase de résolution ;)

Alex · Answer

Bonjour,

C'est un vieux post, mais voilà un solveur - entraineur de Sudoku fait sous Excel. A télécharger gratuitement sur le site suivant :
www.acamasupport.com
Au cas où certains tombent, comme moi, sur ce post.
Vous voulez le code, laissez un message sur le site on vous l'enverra.

Alex

[c] mon solveur de sudoku

5 réponses

Discussions similaires