Resoudre Sudoku,,backTracking & random!!! [Résolu/Fermé]

Signaler
Messages postés
35
Date d'inscription
jeudi 24 janvier 2008
Statut
Membre
Dernière intervention
5 avril 2010
-
Messages postés
496
Date d'inscription
lundi 17 septembre 2007
Statut
Membre
Dernière intervention
22 juin 2010
-
Bonjour,
Intro facultatif : "Je m'appelle Achraf étudiant en 1ére année du cycle d'ingénieur informatique,,,comment toujours, un module de programmation C nous a été présenté et maintenant c'est le tour de mini-projet C"

Je doit réaliser un programme qui peut résoudre une grille de sudoku,, "c'est l'idée principale car aprés il y aura des optimisations et d'ajout d'autre fonction au programme, par exemple: générer une grille,enregistrer vers une fichier,choisir des mode de difficultés....etc"

j'ai commencé par créer un menu principale pour donner une idée sur les fonctions nécessaires:
		/**---------------------------------------------**\
		|*  Mini-projet: programmation C                 *|
		|*  sujet: Sudoku                                *|
		|*  Elaboré par: Achraf Noomane		             *|
		|*               Med Anis Harrak                 *|
		|*                                               *|
		\**---------------------------------------------**/


#include<stdio.h>
#include<conio.h>         //définir les bibliothèque
#include<windows.h>
#include<stdlib.h>


#define TRUE 1
#define FALSE 0
#define err_f   "\n\n erreur d'ouverture de fichier!!!"
#define err_in  "\n\n erreur d'entree!! verifier svp!!"
/*________________ définir des cst & var______________________________________*/

int n;
FILE *f;
typedef struct {
               int tab[9];
               int taille_tab;
               int solution;
               }cellule;




/* _________________fonction(1): initialiser la matrice à zero _______________*/

void initialiser_grid(cellule grid[10][10]) {

 		for(int i=0;i<9;i++)
 			{
   			for(int j=0;j<9;j++)
   				{
               	grid[i][j].solution=FALSE;
               }
         }
}
/* ___________________________________________________________________________*/

/* ________________fonction(2):Saisie de valeur init par utilisateur _________*/

void saisie_grid(cellule grid[10][10]) {

int i,j,k,solution_temp;

printf("\n\n\n Veuillez entrer les valeurs initiales de votre Sudoku!!!!\n");
printf("le saisie est de la forme suivante");
printf(":\t<Num ligne> espace <Num colonne> espace <valeur de cellule>\n");
printf("pour signaler la fin de la saisie entrer la combinaison <0> <0> <0>\n");

	for(k=0;k<81;k++)
   {
   /*logiquement la saisie ne peut pas dépasser 81 valeur ("taille max de Sudoku")*/

			scanf("%d %d",&i,&j);
         scanf("%d",&solution_temp);

         if(i==0 && j==0 && solution_temp==0)
         break; //désigne la fin de la saisie de valeurs

         grid[i][j].solution=solution_temp;
	}

}

/*____________________________________________________________________________*/

/*_______________________fonction resolution _________________________________*/


//Not yet


/*____________________________________________________________________________*/





//Not yet




/* _____________________fonction(3):affichage ________________________________*/




//Not yet



/* ________________Programme principale ______________________________________*/

void main()
{
  char choix;
   cellule grid[10][10];
  clrscr();
  printf("*******  Sudoku  *******");
  getch();

  do{
    clrscr();
    printf("\n\tMENU");
    printf("\n\n 1. Resoudre une Sudoku");
    printf("\n\n 2. Enregistrer une Sudoku & solution");
    printf("\n\n 3. Generer une sudoku");
    printf("\n\n 4. Changer les parametres");
    printf("\n\n 5. Credits");
    printf("\n\n 6. Exit");

    printf("\n\nEnter votre choix :  ");
    scanf("%d",&choix);

    clrscr();

    switch(choix)
    {
      case 1:
       /*
         étape 1: saisie des valeurs présenter pas l'utilisateur  */
        saisie_grid(grid);
        break;

      case 2:
        /*ip_storesudoku();
        break; */

      case 3:
      /* l'application génére une sodoku */

      case 4:
       /* change_settings();
        break; */

      case 5:

        clrscr();
        printf("___________credit_______________\n");
        Sleep(650);
        printf("\n\n\nCreated By :Achraf Noomane & Med Anis Harrak");
        Sleep(650);
        printf("\n\nCopyright 2008 - Esprit *3B1 info ");
        Sleep(650);
        printf("\n\n Mail : dima_online@hotmail.com");
        Sleep(650);
        do
        {n=random(10);} while(!n);
        printf("%d",n);
        getch();
        break;

      case 6:
        break;

      default:
        printf("\a%s",err_in);
        getch();
    }

  }while(choix!=6);
}


pas la peine de me dire, je sais c'est rien du tout ce que j'ai écrit mais bon,,, j'aime sentir que j'ai fait quelque chose comme même,,,aller au sérieux !!!!! (:-)
SVP quelque moment de concentration avec moi :::

mon algorithme consiste à:: crée une grille de structure ""Cellule"" dont chacune contient un tableau contenant tous les valeurs de [1..9],variable taille_tableau,,,et une dernière qui s'appelle solution... le principe c'est parcourir ligne par ligne puis colonne par colonne toute la grille de cellule, chaque cellule où son champ de (cellule.solution==0) on élimine du tableau (cellule.tab) tous les valeurs de solution des cellules dans le même ligne et le même colonne et la même région.

/*=================================================================*/
/*  fonction pour verifier les différentes possibilités par ligne  */
/*=================================================================*/

void possibilite_ligne(int i,int j,sudoku grille)
{
  int k;
  for (k=0;k<9;k++)
  {
    if(grille[i][k].solution!=0)
        {
       
/*  c'est une fonciton qui élimine un valeur du tableau s'il existe et décrémente la taille du tableau afin de réduire la possibilité des solutions possible*/

            supprimer_val_d1tableau(grille[i][j].taille_tableau,grille[i][j].tab,grille[i][k].solution);
        }
  }
}


meme principe avec le parcours verticale c-a-d dans un colonne, il suffit de changer grille[i][k] par grille[k][j].
/*=================================================================*/
/* fonction pour verifier les différentes possibilités par region  */
/*=================================================================*/

void possibilite_region(int i,int j,sudoku grille)
{
  int k,l,pos_ligne,pos_colonne;
  if((0<=i)&&(i<=2))
    {
     pos_ligne=0;
    }
  if((3<=i)&&(i<=5))
    {
     pos_ligne=3;
    }
  if((6<=i)&&(i<=8))
    {
     pos_ligne=6;
    }
  if((0<=j)&&(j<=2))
    {
     pos_colonne=0;
    }
  if((3<=j)&&(j<=5))
    {
     pos_colonne=3;
    }
  if((6<=j)&&(j<=8))
    {
     pos_colonne =6;
    }
  
for(k=pos_ligne;k<(pos_ligne+3);k++)
    {
     for(l=pos_colonne;l<(pos_colonne+3);l++)
       {
        if(grille[k][l].solution!=0)
          {
           
supprimer_val_d1tableau(grille[i][j].taille_tableau,grille[i][j].tab,grille[k][l].solution);
          }
       }
    }
}


Remarque: tous ces fonctions ne sont pas définitive et j'aime bien quand me corrige ou commenter mon travaille pour optimiser ou de prévenir des éventuelles bugs..

ce que j'ai pas vraiment trouvé ces comment mettre tous ça dans des boucles pour résoudre le sudoku surtout surtout comment choisir des valeurs aléatoires dans le cas ou le Sudoku admet plusieurs solutions.. Mon professeur encadreur ma parler du technique de backtracking!!! I have no idea.aussi la fonction affichage d'une grille c'est pas évident du tout...merci pour votre attention..

3 réponses

Messages postés
496
Date d'inscription
lundi 17 septembre 2007
Statut
Membre
Dernière intervention
22 juin 2010
123
Salutations,

J'aurais un sodoku à faire, je ferais trois parties.
- Un moteur de jeu
- Une brique de résolution
- Un programme d'interface.

Le moteur se concrétiserait par un .h avec des déclarations du type:
- récupérer la valeur en i, j
- écrire une valeur en i, j
- définition d'une constante pour 'valeur inconnue'
- des codes d'erreurs
- La case i, j est elle 'read only'
- La partie est est dans une configuration gagnante.
Enfin bref, le stricte nécessaire pour jouer, pas de structure de tableau ni rien d'accessible frauduleusement.
après au choix, soit des fonctions 'Administrateur' soit des fonctions permettant d'initialiser un jeu à partir de donnée pré-remplies. (et donc un autre .h avec les fonctions de créations ou chargement depuis un fichier)

La brique de résolution a à sa disposition les fonctions normale d'un joueur.
- En random, ben... random
- Back tracking. C'est une méthode de résolution qui explore "intelligemment" toutes les solutions. Un peu à la "Et ça fait quoi si là je met un 9, après là je pourrais mettre un 5, ah non, un 4 ? non plus, Ah bah je pouvais pas mettre un 9..." J'avais utilisé ça pour un TP sur les distributeurs automatiques de billets. Je dois rendre telles sommes sachant qu'il me reste X, Y, Z billets de 100, 50, 20, 10, 5, 2, 1 et que je dois rendre obligatoirement le plus gros possible qu'il me reste et 2 du plus petit. Pour cette méthode il faut constamment avoir sous la main le maximum d'information. Ce solver devra donc maintenir de liste de ce qui peut-être joué : Dans chaque ligne, dans chaque colonne et dans chaque pâté de neuf. Avec ensuite des fonctions de recoupement des trois infos pour connaître les valeurs jouables dans chaque case. Plus exactement, on fera une fonction qui mets les trois informations à jours et une qui récupère une liste de choix possibles pour une case. Le but sera ensuite de remplir les cases vides une par une en essayant un des nombres possibles. On obtient alors une nouvelle configuration. Si le jeu n'est pas gagnant, on le résout de la même façon (ie: en appelant la même fonction récursivement)

typiquement la fonction:
- cherche une case libre
- joue la première valeur possible (idéalement c'est une nouvelle fonction "jouer( i, j valeur )" qui met à jour les infos automatiquement et appelle le moteur pour jouer réellement).
- si le jeu est résolu on mémorise la grille complétée et on a fini (On a joué le dernier coup) -> return 1
- sinon, on relance la fonction de résolution.
- Si elle réussi on a fini (On a joué un coup intermédiaire) -> return 1
- sinon, on retire le coup qu'on a joué ("Back tracking") et on recommence à l'étape 2 avec la valeur possible suivante. Si il n'y en a plus, on ne peut pas résoudre cette partie -> return 0, l'appelant essaiera un autre valeur à lui.

Au final c'est presque un "brute force" de mot de passe: on essaie avec un 'a' en premier puis le reste du mot de passe, si ça marche pas on tentera avec un 'b' etc, sauf que le choix d'une lettre élimine des choix pour après, style un mot de passe qui ne contient que 2 fois une même lettre ou un truc du genre.

La partie interface, ben... permettre au joueur d'utiliser le moteur pour jouer. Ce qui importe c'est qu'elle ne rende pas le moteur de jeu dépendant d'elle.

Après, c'est juste ce que j'en pense... (Pour une fois que ça m'arrive !!)

M.

PS:
Pour stocker les valeurs possibles finalement je ferais une matrice d'entiers qui stockeraient les valeurs possibles par des flags. Ensuite, on peut directement savoir si une valeur est jouable en faisant un ET logique sur le secteur voulu, ligne, colonne ou pâté de 9. Chacun son truc...
1
Merci

Quelques mots de remerciements seront grandement appréciés. Ajouter un commentaire

CCM 65492 internautes nous ont dit merci ce mois-ci

Messages postés
35
Date d'inscription
jeudi 24 janvier 2008
Statut
Membre
Dernière intervention
5 avril 2010
1
Merci de ton aide :)

J'ai bien compris l'idée du backtracking, et bien saisi l'algorithme grâce à ton explication.

Et puis, me reste comment mettre toutes les fonctions que j'ai citées ci-dessus en boucle afin de créer la fonction
"jouer( i, j,valeur )"
dont tu m'as parlé et surtout comment retourner est ce oui ou non la grille Sudoku a été bien résolu ou manque d'autres cellules à rechercher.

- joue la première valeur possible (idéalement c'est une nouvelle fonction "jouer( i, j valeur )" qui met à jour les infos automatiquement et appelle le moteur pour jouer réellement).
--> Si tu veux bien, tu m'expliques comment ça se fait réellement, comment mettons-nous à jour la grille, comment activons-nous le moteur du jeu ? Le principe m'est clair, mais je ne sais pas d'où commencer et comment mettre en "évidence" mes connaissances théoriques.

Pour stocker les valeurs possibles finalement je ferais une matrice d'entiers qui stockeraient les valeurs possibles par des flags. Ensuite, on peut directement savoir si une valeur est jouable en faisant un ET logique sur le secteur voulu, ligne, colonne ou pâté de 9. Chacun son truc...
--> J'arrive pas à saisir comment utiliser les mots en gras afin de stocker les valeurs de ma matrice.

Merci encore une fois :)
Messages postés
496
Date d'inscription
lundi 17 septembre 2007
Statut
Membre
Dernière intervention
22 juin 2010
123
>>comment retourner est ce oui ou non la grille Sudoku a été bien résolu ou manque d'autres cellules à rechercher

Selon moi, la fonction de résolution renvoie 0 ou 1 selon qu'elle ait pu résoudre ou non la grille complète. 1 la solution a été trouvée, 0 la résolution est impossible. La fonction répond 0 lorsqu'elle n'a pas ou plus de valeurs possibles à tester pour sa case. L'appel précédent de la fonction récupère donc cette réponse, tente une autre valeur et rappelle la fonction de résolution.


Pour la réalisation d'une fonction "jouer" plus ou moins intelligente, cela implique d'avoir définie une manière de conserver les informations nécessaires. Il n'y a pas de restriction sur la manière de le faire, il faut juste pouvoir connaître à tout moment et pour chaque case toutes les valeurs qu'il est possible de jouer.
Concretement:
#include "sudoku.h"   // interface du moteur de jeu

void BT_mettreAJour( unsigned int uLigne, unsigned int uColonne, unsigned int uValeur );
// BTpour Back Tracking

void BT_jouer( unsigned int uLigne, unsigned int uColonne, unsigned int uValeur )
{
   BT_mettreAJour( uLigne, uColonne, uValeur );
   sudoku_jouer( uLigne, uColonne, uValeur );
}

Il n'y a pas forcement besoin d'une fonction BT_mettreAJour mais comme je ne savais pas comment tu veux la faire...

Pour simplifier, une première version de la résolution par backtracking pourrait ne pas garder d'information supplémentaire sur les valeurs possibles. Elles sont tout simplement choisies de 1 à 9 pour chaque cases. Cela va tester des réponses stupides comme une grille avec que des '1' etc mais cela a les mêmes chances de résolution.

Moi je verrais bien ton projet en projetS.
Une librairie Sudoku (.dll, .lib, .a ou .su selon ton choix et ton OS)
Une librairie de résolution qui exploite la librairie sudoku.
Un executable d'interface utilisateur pour exploiter les deux librairies.

Pour ce qui est de mon choix de stocker les coups possibles/impossibles par des flags je trouve ça plus intéressant du point de vue programmeur. (Surtout pour ne pas se prendre la tête avec des if ou des switch.)
Le principe est simple, plutôt que de faire un tableau de 1 à 9 pour chaque case pour dire si le chiffre peut être joué, on code ça sur les bits d'un entier. (chaque bit représentant une puissance de 2)
#define _VALUE_1 0x0001
#define _VALUE_2 0x0002
#define _VALUE_3 0x0004
#define _VALUE_4 0x0008
#define _VALUE_5 0x0010
#define _VALUE_6 0x0020
#define _VALUE_7 0x0040
#define _VALUE_8 0x0080
#define _VALUE_9 0x0100

D'ailleurs, à y réfléchir, on peut ne garder les valeurs possibles que pour les lignes, les colonnes et les pâtés et non pas pour chaque cases. Ce qui fait 2 tableaux de 9 entiers et un de 3x3. Comme ça "maintenir les infos à jour" revient modifer trois entiers :)

Ensuite, pour obtenir les valeurs possibles pour une case on a une fonction plus simple:

unsigned int ValeurPossiblesCase( unsigned int uLigne, unsigned int u )
{
return ValeurPossiblesLigne( uLigne) & ValeurPossiblesColonne( uColonne ) &
ValeurPossiblesPâté( uLigne, uColonne );
}

Les autres étant des accesseurs tout simples pour les trois tableaux.

Pour savoir si on peut jouer un 5:

if ( ValeurPossiblesCase( i, j ) & _VALUE_5 )



(Petit rappel sur les opérateurs "binaire" ou "logique":
0011
& 1010 et
= 0010
(Ainsi:
65 & 17 = 1 (leur seul bit en commun)
65 & 18 = 0 etc)

0011
| 1010 ou
= 1011

0011
^ 1010 ou exclusif, xor -> L'un ou l'autre mais pas les deux.
= 1001

~ 01
= 10
(/!\ ~1 = 11111110 sur 8 bits, 1111111111111110 sur 16 bits etc)

et aussi << et >> qui ne vont pas beaucoup servir ici.

Le & nous dira donc dans la fonction ci dessus quels bits sont à 1 dans les 3 cas.

Pour mettre un bit à 1:
"1 ou X = 1"
i = i | _VALUE_5; ou
i |= _VALUE_5;

Pour mettre un bit à 0:
"0 et X = 0"
i = i & (~_VALUE_5); ou
i &= ~_VALUE_5;

Vérifier qu'un nombre ne s'écrit qu'avec un seul bit (= est une puissance de 2)
( i & ( i - 1 ) ) == 0

Enfin bref, je dévie un peu de la question...

Est-ce plus clair ?

M.
Messages postés
35
Date d'inscription
jeudi 24 janvier 2008
Statut
Membre
Dernière intervention
5 avril 2010
1
Dear Mahmah
votre aide ,,, vraiment ça fait plaisir de donner autant de temps pour me faire expliquer que mon professeur !!! c'est paradoxale non!!
j'ai une meilleur vision pour le problème grâce à vous et je mettra tous ça en œuvre des maintenant,,,je vous répondra en fonction des mes avances,,,,,,merci autre fois, merci merci merci
Messages postés
496
Date d'inscription
lundi 17 septembre 2007
Statut
Membre
Dernière intervention
22 juin 2010
123 >
Messages postés
35
Date d'inscription
jeudi 24 janvier 2008
Statut
Membre
Dernière intervention
5 avril 2010

Y a pas de soucis ^^

M.