"Generateur du Sudokus" : problème d'algorithme ?
Bonjour à tous,
Ca faisait longtemps que je n'avais plus programmé (et à l'époque je n'étais pas très bon :D) et pour me remettre dans le bain j'ai décidé de coder un jeu de Sudoku (en console pour l'instant).
Entre les points virgules oubliés et les pointeurs ratés (quand je dis que je suis rouillé ^^) J'ai réussi à obtenir quelques maigres résultats, avec un problème assez surprenant.
En ce moment, je planche sur la génération d'une grille 9x9 complète et correcte (donc : injouable car déjà complétée, mais qui respecte les contraintes du jeu : pas de doublons dans les lignes, colonnes et carrés).
Comme j'avance par étapes, je me contente d'abord des lignes et colonnes : les deux marchent à merveille individuellement, mais je n'arrive pas à les combiner.
Le raisonnement de base consiste à avoir une grille (un tableau 9x9) qui commence avec 0 partout (pour l'initialisation), ensuite, pour chaque case, j'utilise une fonction "mettre n'importe quelle valeur tant que ca fonctionne" : la première case a donc une valeur purement aléatoire, mais la suivante en a une autre, et ainsi de suite. Pour chaque case, on prend une valeur test aléatoire : si elle respecte les contraintes on la prend, sinon on réessaye, jusqu'à ce que ça marche.
Donc, pour vérifier que les contraintes sont respectées, je regarde toute la ligne ou colonne et regarde si cette valeur est déjà prise.
Voici la méthode telle que je l'ai implémentée.
Elle prend à paramètre les coordonnées de la case à remplir, et se termine par le remplissage de la case. (Le tableau de cases étant un attribut de l'objet représentant la grille)
Il y a une boucle pour la vérification de la ligne, et une pour la colonne. Si je commente une des deux boucles et n'utilise qu'une seule des deux vérifications, celle-ci marche crème. Peu importe si je garde la 1ere ou la 2e. Mais si les deux sont actifs, le programme freeze (boucle infinie je présume).
Je voudrais savoir si j'ai fait une bourde de syntaxe quelque part ou si mon algorithme est mauvais. (Peut-être que, statistiquement, mon algorithme bloquera forcément à la fin ?)
Dois-je changer une ligne, ou bien trouver un autre raisonnement ?
Code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
| void Sudoku_grille::PutRandomPossibleValue(int x, int y)
{
bool done = false;
int valeurtest = 0;
int i = 0;
bool lineOK = true;
bool columnOK = true;
while (!done)
{
valeurtest = (rand()%9)+1; // Choisir une valeur à tester
for (i =0; i<9; i++) // Vérification de la colonne
{
columnOK = true;
if (cases[x][i]->get_correct_value() == valeurtest && i != y) //Si déjà pris... Ou si se vérifie lui-meme
{
columnOK = false;
break;
}
}
for (i =0; i<9; i++) // vérif ligne
{
lineOK = true;
if (cases[i][y]->get_correct_value() == valeurtest && i != x) //Si déjà pris... Ou si se vérifie lui-meme
{
lineOK = false;
break;
}
}
if (lineOK && columnOK)
{
cases[x][y]->set_correct_value(valeurtest);
done = true;
}
}
} |
Merci d'avance :)
(PS : Je suis nouveau ici; j'hésitais entre poster ici ou sur la section débuter; que me conseillez vous à l'avenir ?)
