IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

C++ Discussion :

"Generateur du Sudokus" : problème d'algorithme ?


Sujet :

C++

Vue hybride

Message précédent Message précédent   Message suivant Message suivant
  1. #1
    Membre actif
    Homme Profil pro
    Lycéen
    Inscrit en
    Juillet 2015
    Messages
    26
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 26
    Localisation : Belgique

    Informations professionnelles :
    Activité : Lycéen

    Informations forums :
    Inscription : Juillet 2015
    Messages : 26
    Par défaut "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 ) 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 ?)

  2. #2
    Membre éprouvé Avatar de Capitaine Kirk
    Profil pro
    Inscrit en
    Mars 2005
    Messages
    98
    Détails du profil
    Informations personnelles :
    Localisation : Etats-Unis

    Informations forums :
    Inscription : Mars 2005
    Messages : 98
    Par défaut
    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.

  3. #3
    Expert éminent

    Femme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    Juin 2007
    Messages
    5 202
    Détails du profil
    Informations personnelles :
    Sexe : Femme
    Localisation : France, Essonne (Île de France)

    Informations professionnelles :
    Activité : Ingénieur développement logiciels

    Informations forums :
    Inscription : Juin 2007
    Messages : 5 202
    Par défaut
    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.

  4. #4
    Membre éprouvé
    Profil pro
    Inscrit en
    Juin 2010
    Messages
    53
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Juin 2010
    Messages : 53
    Par défaut
    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).

  5. #5
    Expert éminent

    Femme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    Juin 2007
    Messages
    5 202
    Détails du profil
    Informations personnelles :
    Sexe : Femme
    Localisation : France, Essonne (Île de France)

    Informations professionnelles :
    Activité : Ingénieur développement logiciels

    Informations forums :
    Inscription : Juin 2007
    Messages : 5 202
    Par défaut
    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.

  6. #6
    Membre actif
    Homme Profil pro
    Lycéen
    Inscrit en
    Juillet 2015
    Messages
    26
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 26
    Localisation : Belgique

    Informations professionnelles :
    Activité : Lycéen

    Informations forums :
    Inscription : Juillet 2015
    Messages : 26
    Par défaut
    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 !

Discussions similaires

  1. Réponses: 10
    Dernier message: 23/05/2007, 09h30
  2. problème d'algorithme pour trouver les circuit d'un graphe
    Par marc_dd dans le forum Algorithmes et structures de données
    Réponses: 11
    Dernier message: 21/08/2006, 16h36

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo