Bonjour!
Je suis actuellement en L2 à la fac où je fais un peu de programmation, et mon groupe et moi avons un projet, qui consiste, entre autres, à proposer un programme de résolution de Sudoku de toute taille(nous ne nous sommes encore penchés que sur des grilles carrées), mais voilà que nous avons un problème dans notre début de programme que nous n'expliquons pas (pour l'initialisation de la grille à résoudre).
Je vous mets une partie de ce que nous avons fait, la partie qui nous intéresse et où il y a un problème. Si quelqu'un peut prendre le temps de tout lire, comprendre, et nous trouve d'où vient notre bug, ça nous aidera vraiment beaucoup.
Nous implémentons notre grille de sudoku comme un tableau 2D avec des pointeurs.
Nous définissons une structure de données "element" qui représente les éléments que l'on aura dans notre tableau 2D.
Code :
- struct element {
- int ValeurFinale;
- int valposs[];
- }
|
Dans chaque case, il y a donc un tableau valposs[] qui contient tous les valeurs possibles de la case, et des 0 pour remplacer les valeurs qu'on a deviné improbables.
Exemple, si 1,3,5 est l'ensemble des valeurs possibles dans notre case de sudoku 9*9, le valposs correspondant est:
[1,0,3,0,5,0,0,0,0]
La ValeurFinale de chaque case vaut 0 tant qu'on ne sait pas quoi mettre dans cette case
(c'est-à-dire tant que le tableau valposs[] contient plus d'une valeur non-nulle), et quand il n'y a plus qu'une valeur non-nulle dans valposs[] on attribue cette valeur à ValeurFinale.
Code :
- #include <iostream>
- #include <math.h>
- using namespace std;
- struct element{
- int ValeurFinale;
- int valposs[] ;
- };
- //---------------------------------------------------------------------------------------------------------
- //Fonction qui teste si n est un carré parfait:
- bool EstUnCarre(int n){
- return (sqrt(n)==floor(sqrt(n)));
- }
- //----------------------------------------------------------------------------------------------------------
- //Remplissage des valeurs finales avec des 0
- void remplissage0(int n,element* grille[])
- {
- for (int i=0;i<n;i++)
- {
- for(int j=0;j<n;j++)
- {
- grille[i][j].ValeurFinale=0;
- }
- }
- }
- //----------------------------------------------------------------------------------------------------------
- //Affichage: affiche "X " quand la valeur finale est un 0, "v " quand la valeur finale v s'écrit en deux chiffres, et //"v " quand elle s'écrit en un chiffre pour que l'affichage soit propre
- void affichage(int n,element* grille[])
- { for (int i=0;i<n;i++)
- {for(int j=0;j<n;j++)
- {if (grille[i][j].ValeurFinale==0)
- {cout<<"X ";}
- else
- { if(grille[i][j].ValeurFinale>9)
- {cout<<grille[i][j].ValeurFinale<<" ";}
- else
- {cout<<grille[i][j].ValeurFinale<<" ";}
- }
- }
- cout<<endl;
- }
- }
- //-----------------------------------------------------------------------------------------------------------
- //remplissage des tableaux de valeurs possibles dans chaque case
- void remplissageVP(int n,element* grille[])
- {
- for(int i=0; i<n; i++)
- {for(int j=0; j<n; j++)
- {for (int k=0; k<n; k++)
- {grille[i][j].valposs[k]=k+1;
- }
- }
- }
- }
- //---------------------------------------------------------------------------------------------------------
- //affichage des tableaux de valeurs possibles de chaque case
- void affichageVP(int n, element* grille[])
- {
- for(int i=0; i<n; i++)
- {for(int j=0; j<n; j++)
- {for (int k=0; k<n; k++)
- {
- cout<<grille[i][j].valposs[k];
- }
- cout<<" ";
- }
- cout<<endl;
- }
- }
- //-----------------------------------------------------------------------------------------------------------
- void remplissageEtAffichageVP(int n,element* grille[])
- {
- for(int i=0; i<n; i++)
- {for(int j=0; j<n; j++)
- {for (int k=0; k<n; k++)
- {grille[i][j].valposs[k]=k+1;
- cout<<grille[i][j].valposs[k];
- }
- cout<<" ";
- }
- cout<<endl;
- }
- }
- //-----------------------------------------------------------------------------------------------------------
- //...
- //-----------------------------------------------------------------------------------------------------------
- //-------------------------------------MAIN----------------------------------------------------------//
- int main ()
- {
- //----------------------------------Initialisation de la grille--------------------------------------//
- int n;
- int comptRemplissage=0;
- //comptRemplissage sert uniquement pour la résolution, il compte le nombre de valeurs qui ont été rentrées //dans la grille de Sudoku.
- //Quand comptRemplissage atteint n²(81 pour une grille basique), c'est qu'on a terminé de la résoudre.
- cout<<"Saisir la taille de la grille (nombre de cases par ligne, par colonne ou par carre)"<<endl;
- do
- {
- cin>>n;
- if (!(EstUnCarre(n)))
- {
- cout<<"Taille invalide, saisissez une taille valide"<<endl;
- }
- }while(!(EstUnCarre(n)));
- //allocation dynamique
- element **grille = new element* [n];
- for (int i = 0; i < n; i++)
- {grille[i] = new element[n];}
- //Remplissage avec des 0
- remplissage0(n,grille);
- //Affichage
- affichage(n,grille);
- //Remplissage et Affichage des valeurs possibles: 1ère façon:
- remplissageVP(n,grille);
- affichageVP(n,grille);
- //Remplissage et Affichage des valeurs possibles: 2ème façon:
- //remplissageEtAffichageVP(n,grille);
- ...
|
Il n'y a aucun problème de compilation, mais nous avons quelque chose d'étrange à l'exécution: une différence anormale entre la 1ère et la 2ème façon d'afficher nos valeurs possibles, mais dans les deux cas, la suite du programme donne des résultats complètement faux, et nous pensons que le problème qui suit est engendré par ce problème-là au niveau des valeurs possibles des cases.
(dans la suite du programme, nous faisons la saisie des valeurs initiales de la grille, et, par exemple, lorsque nous mettons uniquement un 1 dans la première ligne, première colonne, l'affichage de la grille donne un truc du genre
1 1 X 1
4 1 X 1
3 1 X 1
3 1 X 1 pour une grille 4*4)
1ère façon:
Citation :
Saisir la taille de la grille (nombre de cases par ligne, par colonne ou par carre)
4
X X X X
X X X X
X X X X
1234 1234 1234 1234
1234 1234 1234 1234
1234 1234 1234 1234
1234 1234 1234 1234
|
2ème façon:
Citation :
Saisir la taille de la grille (nombre de cases par ligne, par colonne ou par carre)
4
X X X X
X X X X
X X X X
1111 1112 1123 1231
1111 1112 1123 1231
1111 1112 1123 1231
1111 1112 1123 1234
|
Voilà tout, si vous êtes disposés à nous aider nous vous en serons reconnaissants. S'il y a quelque chose qui n'est pas clair dans mon explication du programme, demandez-moi s'il vous plaît.
Merci
)