|
|
|
|
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);
}
/*=================================================================*/
/* 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);
}
}
}
/*=================================================================*/
/* 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);
}
}
}
}
Configuration: Windows Vista Firefox 2.0.0.7
Salutations,
|
Merci de ton aide :)
"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 :) |
>>comment retourner est ce oui ou non la grille Sudoku a été bien résolu ou manque d'autres cellules à rechercher
#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.
|