Discussion :

[bisthebis]

Bonjour à tous,
Ca faisait longtemps que je n'avais plus programmé (et à l'époque je n'étais pas très bon ) 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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 ?)

[Capitaine Kirk]

Bonjour,

Je ne suis pas programmeur c++ donc il y a certaines petites choses qui m'echaperont surement, mais au niveau de l'algorithme je ne sais pas si c'est une bonne idee de proceder ainsi parce que j'ai l'impression le probleme se situe dans le fait que tu peux avoir 10 fois de suite le meme chiffre aleatoire genere, donc tu vas verifier 10 fois le meme chiffre c'est surement pour cette raison que ton programme prend enormement de temps et donne l'impression de bloquer, il faudrait je pense trouver un moyen de stocker les chiffres deja present et eviter a ton generateur de les generer.

Cordialement.

[ternel]

En général, les algorithmes utilisent une grille des nombres encore possible pour chaque case.
Chaque fois que tu choisis un nombre, tu le retire des possibles de chaque case de sa ligne, de sa colonne et de son bloc.
Si tu as une case qui n'a plus de possible mais n'est pas rempli, c'est que le nombre généré n'était pas possible.

A ce moment là, tu remarques que les grilles sont générées par parcours (éventuellement avec embranchement).
Il pourrait être intéressant de créer un arbre de dépendance entre les cases, et de générer les premières cases aléatoirement.

C'est triste à dire, mais la génération d'une grille en un temps rapide requiert de savoir résoudre une grille.
En effet, ce sont les techniques de résolution qui permette de lier les nombres.
Il "suffit" de générer dans l'autre sens pour savoir comment l'initialiser.

[kajtp]

Oui il y a bien un problème d'algo, voir le message précédent pour la solution, avec le tient on peut tomber sur cette grille par exemple
<code>
2 8 1 6 4 7 5 9 3
6 5 3 4 2 9 1 7 8
4 3 7 8 9 6 2 1 5
7 1 5 3 8 4 6 2 9
3 4 6 2 7 5 8 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
<\code>
où l'on voit bien que pour remplir la case (4,7) aucune de tes conditions n'est satisfaite (tout les nombre sont déjà pris par la colonne et la ligne qui entoure la case), done est toujours false, et boucle infinie (pourtant, toutes les cases précédentes ont vérifient tes conditions).

[ternel]

Une idée, empruntée à un ami: générer des blocs de 3 sur 3, et chercher 9 blocs compatibles.

Une autre, lire les mathématiques du sudoku sur wikipedia.

[bisthebis]

Merci à tous pour les réponses
Effectivement le cas présenté par kajtp est insolvable, bien vu !

C'est triste à dire, mais la génération d'une grille en un temps rapide requiert de savoir résoudre une grille.
En effet, ce sont les techniques de résolution qui permette de lier les nombres.
Il "suffit" de générer dans l'autre sens pour savoir comment l'initialiser.

Peux-tu développer ? Je n'arrive pas vraiment à saisir le concept... Est-il question de placer quelques nombres aléatoires de façon à faire une grille solvable, puis de la résoudre pour avoir une grille complète ?
Quant aux concepts de dépendance et d'arbres, je ne les maitrise absolument pas. J'ajoute ça à ma liste de choses à voir.

Je pense que je vais lire la page wikipedia (j'avais cherché en vitesse sur la page des sudokus mais je n'avais pas trouvé de page dédiée à l'aspect mathématique) et évenutellement tenter le coup des blocs compatibles.

Encore merci !