Sudoku

Marsh Posté le 13-04-2009 à 18:08:23

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

Reply

Marsh Posté le 13-04-2009 à 18:08:23

Reply

Marsh Posté le 13-04-2009 à 19:16:40

En C++, les tabelaux c'est vector pas des structures moches.
Ensuite, vous verrait que ca ira mieux

C'ets quoi cette fac ou on parle pas de la STL en L2 ?

Reply

Marsh Posté le 13-04-2009 à 19:43:57

On ne connaît pas bien les vecteurs (à peine vus en Java), et je ne vois pas en quoi ça nous arrangerait?

Je veux bien que notre structure soit moche, mais elle n'est pas incorrecte a priori?

Merci quand même pour la réponse.

Reply

Marsh Posté le 13-04-2009 à 21:01:50

si ...

int valpos[]; n'a pas le sens que tu crois ...
En C++, la mémoire on l'allour dynamiquement et c'ets chaint et c'ets exactement ce que gére vector<>.

Encore une victime de JAVA v_v

Message cité 1 fois

Reply

Marsh Posté le 13-04-2009 à 22:17:25

Joel F a écrit :

si ...

int valpos[]; n'a pas le sens que tu crois ...
En C++, la mémoire on l'allour dynamiquement et c'ets chaint et c'ets exactement ce que gére vector<>.

Encore une victime de JAVA v_v

Je dirais pas victime, mais bon quand on change de langage, c'est con de présumer que ca fonctionne pareil.

Mais quand même victime, péter du java et faire de la struct avec des fonctions bien moches, ça le fait bien

Reply

Marsh Posté le 13-04-2009 à 22:23:11

ah donc en fait le problème viendrait du valposs[], et c'est lui que tu voudrais remplacer par un Vector?

C'est vrai qu'on n'a jamais défini la place que prenait notre tableau valposs[] en mémoire pour chaque case...
Y a-t-il un moyen de faire ça sans passer par un vecteur, histoire que mon groupe et moi restions dans des choses qu'on connaît?

Message cité 1 fois
Message édité par Manudesbois le 13-04-2009 à 22:29:14

Reply

Marsh Posté le 13-04-2009 à 22:39:01

Bah utiliser la même syntaxe pour valposs que pour tes autres pointeurs, faire les mêmes new et delete

Reply

Marsh Posté le 13-04-2009 à 22:42:27

Manudesbois a écrit :

ah donc en fait le problème viendrait du valposs[], et c'est lui que tu voudrais remplacer par un Vector?

C'est vrai qu'on n'a jamais défini la place que prenait notre tableau valposs[] en mémoire pour chaque case...
Y a-t-il un moyen de faire ça sans passer par un vecteur, histoire que mon groupe et moi restions dans des choses qu'on connaît?

A toi de voir si ça vaut le coup d'apprendre un peu pour supprimer plein de lignes de codes ou pas.

Reply

Marsh Posté le 14-04-2009 à 11:10:53

OK.

Si je mets

Code :

int* valposs;

dans mon struct à la place de

Code :

int valposs[];

et qu'ensuite ligne 143 je mets

Code :

for (int i=0;i<n;i++)
{
for (int j=0;j<n;j++)
{
int* grille[i][j].valposs = (int*)malloc (n*sizeof(int));
}
}

c'est pas bon?

Message cité 1 fois

Reply

Marsh Posté le 14-04-2009 à 11:22:21

Diantre, v_v.
La manière propre d'allouer un tableau à 2 dimensiosn :
http://forum.hardware.fr/forum2.ph [...] w=0&nojs=0

cf fin du fil.

Message édité par Joel F le 14-04-2009 à 11:22:54

Reply

Marsh Posté le 14-04-2009 à 11:22:21

Reply

Marsh Posté le 14-04-2009 à 11:33:19

Manudesbois a écrit :

OK.

Si je mets

Code :

int* valposs;

dans mon struct à la place de

Code :

int valposs[];

et qu'ensuite ligne 143 je mets

Code :

for (int i=0;i<n;i++)
{
for (int j=0;j<n;j++)
{
int* grille[i][j].valposs = (int*)malloc (n*sizeof(int));
}
}

c'est pas bon?

C'est marrant ça. Je te dis tout pareil avec new, et tois tu sors un malloc ...
Et puis la syntaxe n'est pas bonne.

Tout pareil j'ai dit.

Message édité par Taz le 14-04-2009 à 11:33:52

Reply

Marsh Posté le 14-04-2009 à 11:45:19

Deux manières d'aborder la résolution de sudoku en algo.
Le backtracking :
Tu essaies un chiffre, tu continues tant que ça va, puis si jamais ça chies, tu reviens en arrière tant que la résolution foire.
C'est une méthode simple mais peu efficace en terme de complexité (quoi que tu peux la sophistiquer un peu en faisant des vérifications "a priori" ).

Je n'aborderais pas la seconde technique nommée "dancing links", d'une part parcequ'il y a de nombreux tutos à ce sujet sur le net, d'autre part car je n'ai pas réussi à l'implémenter. (En même temps on a eu deux jours pour faire ce projet )

Reply

Marsh Posté le 14-04-2009 à 12:08:02

Citation :

Deux manières d'aborder la résolution de sudoku en algo.
Le backtracking :
Tu essaies un chiffre, tu continues tant que ça va, puis si jamais ça chies, tu reviens en arrière tant que la résolution foire.
C'est une méthode simple mais peu efficace en terme de complexité (quoi que tu peux la sophistiquer un peu en faisant des vérifications "a priori" ).

Je n'aborderais pas la seconde technique nommée "dancing links", d'une part parcequ'il y a de nombreux tutos à ce sujet sur le net, d'autre part car je n'ai pas réussi à l'implémenter. (En même temps on a eu deux jours pour faire ce projet )

Merci pour l'info, mais notre problème n'est pas vraiment là, la méthode de résolution, en théorie on l'a^^
C'est juste que le remplissage de la grille foire

Citation :

C'est marrant ça. Je te dis tout pareil avec new, et tois tu sors un malloc ...
Et puis la syntaxe n'est pas bonne.

Tout pareil j'ai dit.

Oui, j'avais essayé un new quand même avant^^ (sans succès)

Reply

Marsh Posté le 14-04-2009 à 12:12:08

grille[i][j].valposs = new int[n];

copié/collé quoi

Reply

Marsh Posté le 14-04-2009 à 12:13:43

toujours avec

Code :

int* valposs;

dans le struct.

et à la ligne 143:

Code :

for (int i=0;i<n;i++)
{
for (int j=0;j<n;j++)
{
int* grille[i][j].valposs = new int[n];
}
}

et voici ce que le compilo dit:

Citation :

143 error: expected initializer before '.' token

Reply

Marsh Posté le 14-04-2009 à 12:15:01

ah cool, sans le int* devant, ça marche, merci!

Reply

Marsh Posté le 14-04-2009 à 12:19:30

Wouhou! Le bug des 1211 a disparu! Merci beaucoup Taz, tu me sauves!

(au passage, si on enlève le int* devant, c'est pourquoi? Parce que grille[i][j].valposs existe déjà?)

Et pour éviter un autre problème, à la fin, il faut bien faire:

Code :

for (int i=0;i<n;i++)
{
for (int j=0;j<n;j++)
{
delete [] grille[i][j].valposs;
}
}

n'est-ce pas?

Message édité par Manudesbois le 14-04-2009 à 12:23:01

Reply

Sudoku

Sujets relatifs:

Leave a Replay