Partage
  • Partager sur Facebook
  • Partager sur Twitter

Solver sudoku

Erreur de segmentation (core dumped)

    26 septembre 2021 à 14:26:22

    Bonjour,

    j'ai réalisé un solver de sudoku mais sur certaines grilles il ne fonctionne pas.

    J'ai 

    sudoku.size() -> 8
    Erreur de segmentation (core dumped)

    ça ne le fait pas avec toutes les grilles.

    Et je n'arrive pas à en trouver l'origine

    Déjà je ne comprends pas sur la grille ci dessous, la taille me renvoie 8 au lieu de 9.

    voici le programme

    #include <iostream>
    #include <algorithm>
    #include <vector>
    #include <chrono>
    
    #define N 9
    
    struct Bloc
    {
      Bloc();
      int pos, n;
    };
    Bloc::Bloc() :pos(0), n(0) {}
    std::vector<Bloc> val;
    
    std::vector<std::vector<int>> solution;
    
    //Liste des fonctions
    bool backtrack(std::vector<std::vector<int>> grille, int id);
    bool rien_carre_3x3(std::vector<std::vector<int>> grille, int k, int i, int j);
    bool rien_ligne_colonne(std::vector<std::vector<int>> grille, int l, int c, int k);
    
    void afficher(std::vector<std::vector<int>> grille)
    {
      for (int x = 0; x < N; x++)
      {
        for (int y = 0; y < N; y++)
        {
          std::cout << grille [x][y];
          ((y + 1) % 3) ? std::cout << " " : std::cout << "|";
        }
        std::cout << '\n';
        if (!((x + 1) % 3))
        {
          std::cout << "------------------\n";
        }
      }
      std::cout << std::endl;
    }
    int main()
    {
      /*
      std::vector<std::vector<int>> grille
      {
        {0,0,5,0,0,0,1,0,0},
        {0,6,1,0,0,0,2,0,0},
        {0,0,0,3,8,0,0,0,0},
        {0,2,0,0,0,0,0,0,4},
        {0,0,0,0,3,0,0,0,9},
        {0,1,3,5,0,0,0,0,2},
        {9,0,0,0,0,2,0,4,0},
        {0,0,0,0,0,0,0,7,0},
        {4,0,0,0,5,9,0,0,3}
      };
      */
      /*
      std::vector<std::vector<int>> grille
      {
        {3,0,6,5,0,8,4,0,0},
        {5,2,0,0,0,0,0,0,0},
        {0,8,7,0,0,0,0,3,1},
        {0,0,3,0,1,0,0,8,0},
        {9,0,0,8,6,3,0,0,5},
        {0,5,0,0,9,0,6,0,0},
        {1,3,0,0,0,0,2,5,0},
        {0,0,0,0,0,0,0,7,4},
        {0,0,5,2,0,6,3,0,0}
      };
      */
      std::vector<std::vector<int>> grille
      {
        {5,0,0,4,0,0,0,3,0},
        {0,0,0,0,1,0,6,0,0},
        {0,0,0,0,0,0,0,0,0},
        {0,0,1,3,4,0,0,0,0},
        {0,7,3,2,0,0,0,0,9},
        {6,8,0,0,0,0,0,0,7},
        {0,0,0,5,0,0,0,2,0},
        {2,1,0,0,6,0,0,0,0}
      };
      solution = grille;
      auto taille{grille.size()}; std::cout << "sudoku.size() -> " << grille.size() << "\n";
    
      for (uint i{0}; i < taille * N; i++)
      {
        Bloc indice;
        if (grille [i / N][i % N] == 0)
        {
          int count{0};
          for (int ii{0}; ii < N; ii++)
          {
            if (grille [ii][i % N] == 0)
            {
              count++;
            }
          }
          for (int jj{0}; jj < N; jj++)
          {
            if (grille [i / N][jj] == 0)
            {
              count++;
            }
          }
          indice.pos = i;
          indice.n = count;
          val.push_back(indice);
        }
        else
        {
          indice.pos = i;
          indice.n = 0;
          val.push_back(indice);
        }
      }
      std::sort(std::begin(val), std::end(val), [](const Bloc &lhs, const Bloc &rhs) {return lhs.n < rhs.n; });
      int position{0}, i{0};
      while (position == 0)
      {
        if (val [i].n != 0)
        {
          position = i; std::cout << "position -> " << position << "\n";
        }
        i++;
      }
      std::cout << "Grille\n";
      afficher(grille);
      std::chrono::time_point<std::chrono::system_clock> start, end;
      start = std::chrono::system_clock::now();
      //backtrack(grille, position);
      if (backtrack(grille, position))
      {
        end = std::chrono::system_clock::now();
        std::cout << "Solution\n";
        afficher(solution);
        std::chrono::duration<double> duree = end - start;
        std::cout.precision(10);
        std::cout << "Durée = " << std::fixed << duree.count() << "s" << std::endl;;
      }
      else
      {
        std::cout << "Pas de solution" << std::endl;
      }
    
      return 0;
    }
    bool backtrack(std::vector<std::vector<int>> grille, int id)
    {
      int pos{val [id].pos};
      if (id == N * N)
      {
        return true;
      }
      int i = pos / 9, j = pos % 9;
      /*
        if (grille [i][j] != 0)
        {
          return backtrack(grille, id + 1);
        }
        */
        //else
        //{
      for (int k{1}; k <= N; k++)
      {
        if (rien_carre_3x3(grille, i, j, k) && rien_ligne_colonne(grille, i, j, k))
        {
          grille [i][j] = k;
          solution [i][j] = k;
          if (backtrack(grille, id + 1))
          {
            return true;
          }
        }
      }
      grille [i][j] = 0;
      return false;
      //}
    }
    bool rien_carre_3x3(std::vector<std::vector<int>> grille, int l, int c, int k)
    {
      int ii = l - (l % 3), jj = c - (c % 3);  // ou encore : _i = 3*(i/3), _j = 3*(j/3);
      for (l = ii; l < ii + 3; l++)
      {
        for (c = jj; c < jj + 3; c++)
        {
          if (grille [l][c] == k)
          {
            return false;
          }
        }
      }
      return true;
    }
    bool rien_ligne_colonne(std::vector<std::vector<int>> grille, int l, int c, int k)
    {
      for (int i{0}; i < N; i++)
      {
        if (grille [l][i] == k || grille [i][c] == k)
        {
          return false;
        }
      }
      return true;
    }
    



     

    -
    Edité par Duncan4031 26 septembre 2021 à 14:28:01

    • Partager sur Facebook
    • Partager sur Twitter
      26 septembre 2021 à 14:40:57

      Bonjour,

      Duncan4031 a écrit:

      Déjà je ne comprends pas sur la grille ci dessous, la taille me renvoie 8 au lieu de 9.

        std::vector<std::vector<int>> grille
        {
          {5,0,0,4,0,0,0,3,0},
          {0,0,0,0,1,0,6,0,0},
          {0,0,0,0,0,0,0,0,0},
          {0,0,1,3,4,0,0,0,0},
          {0,7,3,2,0,0,0,0,9},
          {6,8,0,0,0,0,0,0,7},
          {0,0,0,5,0,0,0,2,0},
          {2,1,0,0,6,0,0,0,0}
        };
      Ta grille fait 8 lignes...

      • Partager sur Facebook
      • Partager sur Twitter
        26 septembre 2021 à 14:46:10

        pfff 2h00 que j'étais dessus...

        Merci pour la remarque.

        Autrement comment améliorer l'algorithme ? Avez vous des pistes ?

        • Partager sur Facebook
        • Partager sur Twitter
          26 septembre 2021 à 14:49:45

          Ton constructeur de Bloc ne fait rien, il faut l'enlever. Le simple fait d'en ajouter un rend l'optimisation plus difficile pour le compilateur (cf. https://www.youtube.com/watch?v=3LsRYnRDSRA). La seule différence serait si tu n'appelle pas explicitement le constructeur de bloc, mais de toute façon il faut initialiser ses variables, n'est-ce pas ?

          struct Bloc {
            int pos, n;
          };
          
          int main() {
            Bloc b1; // non initialisé (mais à éviter généralement)
            Bloc b2{}; // initialisé par le constructeur par défaut  
            // on a bien b2.pos == 0 && b2.n == 0
            return 0;
          }


          Ensuite il est normal que la pile d'exécution explose, déjà parce que tu utilises une fonction récursive, bien que ça ne soit pas gênant dans la plupart des cas, mais on préférera des versions itératives si possibles, sauf si la fonction est récursive terminale, auquel cas le compilateur peut trivialement la rendre itérative. Mais le plus gros problème est que tu prends à chaque fois la grille par valeur, autrement dit à chaque appel, l'entièreté de la grille est copiée.

          Le C++ ne fonctionne pas comme d'autres langages style Java, quand tu prends un objet par valeur, c'est une copie qui est faite. Il faut donc plutôt le prendre par référence (constante si tu n'as pas l'intention de modifier la grille) :

          bool backtrack(const std::vector<std::vector<int>>& grille, int id);

          Mais ici, tu as besoin de modifier la grille avant de lancer l'appel récursif, tu devrais donc faire une copie de la grille juste avant l'appel récursif, pour éviter de le copier à chaque fois. Sinon d'une manière générale, si tu as l'intention de copier l'objet passé en paramètre, il est plus clair de le prendre explicitement par copie, et non par référence constante et le copier juste après. Mais ici cela peut éviter de faire des copies inutiles à chaque appel récursif. D'ailleurs tu ne veux pas vraiment copier la grille passé en paramètre, tu veux plutôt générer les noeuds "fils" de l'état courant.

          Aussi, on pourrait discuter sur le fait d'utiliser un vecteur de vecteur pour représenter la grille, qui n'est pas forcément la solution optimale, étant donné que tu connais la taille de la grille à la compilation. Tu pourrais utiliser std::array, et au passage remplacer le #define par une variable constexpr, qui a l'avantage de passer par le système de typage, pour plus de "sécurité". Et tant qu'on y est, tu peux renommer le tableau de tableau en "Grille" par exemple, comme ça c'est plus court à taper et ça enlève la responsabilité à toutes les fonctions qui l'utilisent de savoir que c'est un "tableau de tableau" :

          constexpr int N = 9;
          
          using Grille = std::array<std::array<Bloc, N>, N>;
          
          bool backtrack(const Grille& grille, int id);

          Si tu veux aller plus loin et entrer dans le territoire de "l'overengineering", tu peux faire une véritable classe "Grille" qui en interne utilise un tableau de tableau et qui expose des fonctions permettant de manipuler la grille, accéder à ses éléments, etc, En redéfinissant operator[] par exemple pour utiliser la syntaxe des crochets. Je te conseille cependant de savoir que tu as effectivement besoin d'une telle complexité avant de te de faire ça, car souvent on pense trop et on se retrouve à devoir modifier la spec dans tous les cas, ce qui est au mieux une perte de temps et au pire on passe à côté d'une solution plus simple (puisqu'on a réfléchi à une solution sans réellement avoir les problèmes pratiques sous les yeux, puisqu'on a pas encore commencé à coder).

          -
          Edité par JadeSalina 26 septembre 2021 à 15:31:26

          • Partager sur Facebook
          • Partager sur Twitter
            26 septembre 2021 à 21:19:54

            Merci pour toutes ces infos.

            Effectivement je ne pense pas toujours à passer par référence. 

            Gain de temps de presque 0.7s quand même

            Je vais appliquer tes conseils.

            Comme j'apprends seul c'est quand même important de pouvoir échanger par moment.

            • Partager sur Facebook
            • Partager sur Twitter
              28 septembre 2021 à 9:44:03

              Je teste une nouvelle idée qui est de se positionner sur la case qui a moins le de possibilités.

              Sauf que maintenant je termine toujours avec cette erreur

              main.cpp:209: int cherche_case_vide(Grille&): Assertion `i == 81 && "i = 81"' failed.
              Abandon (core dumped)
              

              je pense que la fonction backtrap n'est pas correcte mais je ne trouve pas l'erreur

              Si vous avez des suggestions ?

              #include <iostream>
              #include <algorithm>
              #include <vector>
              #include <chrono>
              #include <cassert>
              
              constexpr int N = 9;
              using Grille = std::vector<std::vector<int>>;
              struct Bloc
              {
                int position, possibilite;//position = pos, possibilite = n
              };
              std::vector<Bloc> val;
              
              //std::vector<std::vector<int>> solution;
              Grille solution{};
              
              //Liste des fonctions
              bool backtrack(Grille &grille, int id);
              bool rien_carre_3x3(Grille &grille, int k, int i, int j);
              bool rien_ligne_colonne(Grille &grille, int l, int c, int k);
              int cherche_case_vide(Grille &grille);
              
              void afficher(Grille &grille)
              {
                std::cout << "+-----+-----+-----+\n";
                for (int x = 0; x < N; x++)
                {
                  std::cout << "|";
                  for (int y = 0; y < N; y++)
                  {
                    std::cout << grille [x][y];
                    ((y + 1) % 3) ? std::cout << " " : std::cout << "|";
                  }
                  std::cout << '\n';
                  if (!((x + 1) % 3))
                  {
                    std::cout << "+-----+-----+-----+\n";
                  }
                }
                std::cout << std::endl;
              }
              int main()
              {
                
                 //grilles lentes pour backtracking
                /*
                Grille grille
                {
                  {0,0,0,0,0,0,0,6,8},
                  {9,0,0,0,0,0,0,0,2},
                  {0,0,0,4,0,0,5,0,0},
                  {0,4,1,0,0,0,0,0,0},
                  {0,0,0,0,3,5,0,0,0},
                  {0,5,0,0,0,0,0,0,0},
                  {0,0,0,8,0,0,0,1,0},
                  {3,0,0,0,0,0,7,0,0},
                  {0,0,0,1,0,0,4,0,0}
                };
                */
                
                Grille grille
                {
                  {0,0,0,0,0,0,2,0,1},
                  {0,0,4,0,3,0,0,0,0},
                  {0,0,0,0,0,0,0,0,0},
                  {3,7,0,0,0,0,0,8,0},
                  {6,0,0,2,0,0,0,0,0},
                  {0,0,0,5,0,0,0,0,0},
                  {5,4,0,0,0,0,6,0,0},
                  {0,0,0,0,7,0,0,4,0},
                  {0,0,2,0,0,1,0,0,0}
                };
                
                /*
                Grille grille
                {
                  {0,0,0,0,0,0,3,6,0},
                  {4,3,0,0,0,0,0,0,0},
                  {0,0,0,5,0,0,7,0,0},
                  {0,0,0,7,6,0,0,0,0},
                  {2,0,0,0,0,0,0,0,5},
                  {0,0,0,0,0,0,1,0,0},
                  {0,0,0,0,4,2,0,0,8},
                  {0,7,0,0,0,0,0,4,0},
                  {0,0,1,0,0,0,0,0,0}
                };
                */
                solution = grille;
                auto taille{grille.size()}; std::cout << "sudoku.size() -> " << taille << "\n";
                
                std::cout << "Grille\n";
                afficher(grille);
                std::chrono::time_point<std::chrono::system_clock> start, end;
                start = std::chrono::system_clock::now();
                int position = cherche_case_vide(grille);
                //backtrack(grille, position);
                if (backtrack(grille, position))
                {
                  end = std::chrono::system_clock::now();
                  std::cout << "Solution\n";
                  afficher(solution);
                  std::chrono::duration<double> duree = end - start;
                  std::cout.precision(10);
                  std::cout << "Durée = " << std::fixed << duree.count() << "s" << std::endl;;
                }
                else
                {
                  std::cout << "Pas de solution" << std::endl;
                }
              
                return 0;
              }
              bool backtrack(Grille &grille, int pos)
              {
                if (pos == N * N)
                {
                  return true;
                }
                int i = pos / 9, j = pos % 9;
              
                for (int k{1}; k <= N; k++)
                {
                  if (rien_carre_3x3(grille, i, j, k) && rien_ligne_colonne(grille, i, j, k))
                  {
                    grille [i][j] = k;
                    solution [i][j] = k;
              
                    pos = cherche_case_vide(grille);
              
                    if (backtrack(grille, pos))
                    {
                      return true;
                    }
                  }
                }
                grille [i][j] = 0;
                return false;
              }
              bool rien_carre_3x3(Grille &grille, int l, int c, int k)
              {
                int ii = l - (l % 3), jj = c - (c % 3);
                for (l = ii; l < ii + 3; l++)
                {
                  for (c = jj; c < jj + 3; c++)
                  {
                    if (grille [l][c] == k)
                    {
                      return false;
                    }
                  }
                }
                return true;
              }
              bool rien_ligne_colonne(Grille &grille, int l, int c, int k)
              {
                for (int i{0}; i < N; i++)
                {
                  if (grille [l][i] == k || grille [i][c] == k)
                  {
                    return false;
                  }
                }
                return true;
              }
              int cherche_case_vide(Grille &grille)
              {
                Bloc indice{};
                int count{0};
              
                for (uint i{0}; i < N * N; i++)
                {
                  if (grille [i / N][i % N] == 0)
                  {
                    for (int ii{0}; ii < N; ii++)
                    {
                      if (grille [ii][i % N] == 0)
                      {
                        count++;
                      }
                    }
                    for (int jj{0}; jj < N; jj++)
                    {
                      if (grille [i / N][jj] == 0)
                      {
                        count++;
                      }
                    }
                    indice.position = i;
                    indice.possibilite = count;
                    val.push_back(indice);
                    count = 0;
                  }
                  else
                  {
                    indice.position = i;
                    indice.possibilite = 0;
                    val.push_back(indice);
                  }
                }
              
                std::sort(std::begin(val), std::end(val), [](const Bloc &lhs, const Bloc &rhs) {return lhs.possibilite < rhs.possibilite; });
                int position{0}, i{0};
              
                while (position == 0)
                {
                  if (val [i].possibilite != 0)
                  {
                    assert(i == 81 && "i = 81");
                    position = val [i].position; //std::cout << "i -> " << i << "  position -> " << position << " contenant -> " << val [i].position << " soit ligne -> " << val [i].position / N << " colonne -> " << val [i].position % N << " avec " << val[i].possibilite << " possibilités\n";
                  }
                  i++;
                }
              
                val.clear();
                //val.resize(0);
                return position;
              }




              • Partager sur Facebook
              • Partager sur Twitter
                28 septembre 2021 à 13:25:00

                N'aurais-tu pas compris le fonctionnement de assert à l'envers ? 

                Ta ligne :

                assert(i == 81 && "i = 81");

                termine le programme si i est différent de 81, alors que ça devrait être l'inverse. La condition dans l'assertion doit être vraie pour laisser le programme continuer, or i ne devrait jamais dépasser 80 en fonctionnement normal.

                • Partager sur Facebook
                • Partager sur Twitter
                  28 septembre 2021 à 14:54:49

                  En fait je cherchais pour quelle valeur de i j'ai un core dumped.

                  Si je comprends bien il faut l'écrire comme ça 

                  assert(i != 81 && "i != 81")

                  J'obtiens alors

                  Erreur de segmentation (core dumped)



                  • Partager sur Facebook
                  • Partager sur Twitter
                    28 septembre 2021 à 15:22:12

                    Si le sujet vous intéresse:
                    https://openclassrooms.com/forum/sujet/concours
                    Je n'ai pas terminé ma version finale ...
                    • Partager sur Facebook
                    • Partager sur Twitter

                    Le Tout est souvent plus grand que la somme de ses parties.

                      28 septembre 2021 à 17:00:06

                      PierrotLeFou a écrit:

                      Si le sujet vous intéresse:
                      https://openclassrooms.com/forum/sujet/concours
                      Je n'ai pas terminé ma version finale ...


                      Effectivement j'ai commencé à le parcourir

                      En attendant quelqu'un à une piste pour mon souci ?

                      Edit:

                      finalement j'ai résolu le problème du core dumped

                      c'est pas le programme le plus rapide, mais après quelques tests sur des grilles plutôt tordues ça fonctionne

                      #include <iostream>
                      #include <algorithm>
                      #include <vector>
                      #include <chrono>
                      #include <cassert>
                      
                      constexpr int N = 9;
                      using Grille = std::vector<std::vector<int>>;
                      struct Bloc
                      {
                        int position, possibilite;
                      };
                      std::vector<Bloc> val;
                      
                      //Liste des fonctions
                      bool backtrack(Grille &grille, int id);
                      bool rien_carre_3x3(Grille &grille, int k, int i, int j);
                      bool rien_ligne_colonne(Grille &grille, int l, int c, int k);
                      int cherche_case_vide(Grille &grille);
                      
                      void afficher(Grille &grille)
                      {
                        std::cout << "+-----+-----+-----+\n";
                        for (int x = 0; x < N; x++)
                        {
                          std::cout << "|";
                          for (int y = 0; y < N; y++)
                          {
                            std::cout << grille [x][y];
                            ((y + 1) % 3) ? std::cout << " " : std::cout << "|";
                          }
                          std::cout << '\n';
                          if (!((x + 1) % 3))
                          {
                            std::cout << "+-----+-----+-----+\n";
                          }
                        }
                        std::cout << std::endl;
                      }
                      int main()
                      {
                        /*
                        Grille grille
                        {
                          {0,0,0,0,0,6,0,0,5},
                          {0,0,9,0,0,0,0,0,0},
                          {0,0,1,0,0,0,0,0,0},
                          {0,0,0,0,0,0,0,0,0},
                          {7,0,0,0,0,0,0,0,0},
                          {0,0,0,0,0,0,0,0,0},
                          {9,0,0,0,0,0,0,0,0},
                          {2,0,0,0,0,0,0,0,0},
                          {0,0,0,0,0,0,0,0,0}
                        };
                        */
                        //grilles lentes pour backtracking
                       /*
                       Grille grille
                       {
                         {0,0,0,0,0,0,0,6,8},
                         {9,0,0,0,0,0,0,0,2},
                         {0,0,0,4,0,0,5,0,0},
                         {0,4,1,0,0,0,0,0,0},
                         {0,0,0,0,3,5,0,0,0},
                         {0,5,0,0,0,0,0,0,0},
                         {0,0,0,8,0,0,0,1,0},
                         {3,0,0,0,0,0,7,0,0},
                         {0,0,0,1,0,0,4,0,0}
                       };
                       */
                       /*
                       Grille grille
                       {
                         {0,0,0,0,0,0,2,0,1},
                         {0,0,4,0,3,0,0,0,0},
                         {0,0,0,0,0,0,0,0,0},
                         {3,7,0,0,0,0,0,8,0},
                         {6,0,0,2,0,0,0,0,0},
                         {0,0,0,5,0,0,0,0,0},
                         {5,4,0,0,0,0,6,0,0},
                         {0,0,0,0,7,0,0,4,0},
                         {0,0,2,0,0,1,0,0,0}
                       };
                       */
                       /*
                       Grille grille
                       {
                         {0,0,0,0,0,0,3,6,0},
                         {4,3,0,0,0,0,0,0,0},
                         {0,0,0,5,0,0,7,0,0},
                         {0,0,0,7,6,0,0,0,0},
                         {2,0,0,0,0,0,0,0,5},
                         {0,0,0,0,0,0,1,0,0},
                         {0,0,0,0,4,2,0,0,8},
                         {0,7,0,0,0,0,0,4,0},
                         {0,0,1,0,0,0,0,0,0}
                       };
                       */
                        Grille grille
                        {
                          {2,0,0,4,0,0,6,0,0},
                          {0,0,0,5,0,0,0,1,0},
                          {0,0,0,0,0,0,0,0,0},
                          {5,0,0,0,8,0,0,0,4},
                          {3,0,0,0,2,0,0,0,0},
                          {0,0,0,0,0,0,0,8,0},
                          {0,0,0,7,0,5,3,0,0},
                          {0,0,8,0,0,0,0,0,2},
                          {0,1,0,0,0,0,0,0,0}
                        };
                        auto taille{grille.size()}; std::cout << "sudoku.size() -> " << taille << "\n";
                      
                        std::cout << "Grille\n";
                        afficher(grille);
                        std::chrono::time_point<std::chrono::system_clock> start, end;
                        start = std::chrono::system_clock::now();
                        int position = cherche_case_vide(grille);
                        if (backtrack(grille, position))
                        {
                          end = std::chrono::system_clock::now();
                          std::cout << "Solution\n";
                          afficher(grille);
                          std::chrono::duration<double> duree = end - start;
                          std::cout.precision(10);
                          std::cout << "Durée = " << std::fixed << duree.count() << "s" << std::endl;;
                        }
                        else
                        {
                          end = std::chrono::system_clock::now();
                          std::chrono::duration<double> elapsed_seconds = end - start;
                          std::cout.precision(10);
                          std::cout << "Pas de solution" << std::endl;
                          std::cout << "elapsed time = " << std::fixed << elapsed_seconds.count() << "s\n";
                        }
                      
                        return 0;
                      }
                      bool backtrack(Grille &grille, int pos)
                      {
                      
                        if (pos == N * N)
                        {
                          return true;
                        }
                        int i = pos / 9, j = pos % 9;
                      
                        if (grille [i][j] != 0)
                        {
                          //pos = cherche_case_vide(grille);
                          return backtrack(grille, pos + 1);
                        }
                      
                        for (int k{1}; k <= N; k++)
                        {
                          if (rien_carre_3x3(grille, i, j, k) && rien_ligne_colonne(grille, i, j, k))
                          {
                            grille [i][j] = k;
                      
                            pos = cherche_case_vide(grille);
                      
                            if (backtrack(grille, pos))
                            {
                              return true;
                            }
                      
                          }
                        }
                        grille [i][j] = 0;
                        return false;
                      }
                      bool rien_carre_3x3(Grille &grille, int l, int c, int k)
                      {
                        int ii = l - (l % 3), jj = c - (c % 3);
                        for (l = ii; l < ii + 3; l++)
                        {
                          for (c = jj; c < jj + 3; c++)
                          {
                            if (grille [l][c] == k)
                            {
                              return false;
                            }
                          }
                        }
                        return true;
                      }
                      bool rien_ligne_colonne(Grille &grille, int l, int c, int k)
                      {
                        for (int i{0}; i < N; i++)
                        {
                          if (grille [l][i] == k || grille [i][c] == k)
                          {
                            return false;
                          }
                        }
                        return true;
                      }
                      int cherche_case_vide(Grille &grille)
                      {
                        Bloc indice{};
                        int count{0};
                        val.clear();
                        val.resize(0);
                      
                        for (uint i{0}; i < N * N; i++)
                        {
                          if (grille [i / N][i % N] == 0)
                          {
                            for (int ii{0}; ii < N; ii++)
                            {
                              if (grille [ii][i % N] == 0)
                              {
                                count++;
                              }
                            }
                            for (int jj{0}; jj < N; jj++)
                            {
                              if (grille [i / N][jj] == 0)
                              {
                                count++;
                              }
                            }
                            indice.position = i;
                            indice.possibilite = count;
                            val.push_back(indice);
                            count = 0;
                          }
                          else
                          {
                            indice.position = i;
                            indice.possibilite = 0;
                            val.push_back(indice);
                          }
                        }
                      
                        std::sort(std::begin(val), std::end(val), [](const Bloc &lhs, const Bloc &rhs) {return lhs.possibilite < rhs.possibilite; });
                        int position{0};
                      
                        for (int i{0}; i < 81; i++)
                        {
                          if (val [i].possibilite != 0)
                          {
                            position = val [i].position; break; //std::cout << "i -> " << i << "  position -> " << position << " contenant -> " << val [i].position << " soit ligne -> " << val [i].position / N << " colonne -> " << val [i].position % N << " avec " << val[i].possibilite << " possibilités\n";
                          }
                        }
                        return position;
                      }



                      -
                      Edité par Duncan4031 28 septembre 2021 à 19:19:15

                      • Partager sur Facebook
                      • Partager sur Twitter
                        29 septembre 2021 à 2:45:34

                        Je suis allé revoir mon premier code. :)
                        Si tu remarques, j'ai abandonné la grille des contraintes ou peu importe comment on l'appelle.
                        Ma façon de faire les appels récursifs fait que je ne peux pas effacer une case initialisée au départ.
                        Le fondement d'un algorithme récursif (je dis des conneries?) est de savoir quand s'arrêter. Il semble que tu as fini par le comprendre.
                        On n'a pas besoin de backtracking explicite. C'est l'empilage et le dépilage de la récursivité qui le fait.
                        Regardes comment est faite ma fonction placer().

                        Ça pourrait ressembler à ceci:
                        bool placer(grille, position) {
                            si je suis rendu au bout, je retourne true
                            Je fais la liste des chiffres que je peux placer dans cette position (ligne, colonne, carré)
                            pour chiffre dans la liste {
                                je met le chiffre dans position
                                si placer(grille, position suivante) je retourne true    // je me suis rendu au bout au cours d'un appel ultérieur
                            }
                            // je suis passé par toutes les possibilités de la liste sans succès
                             j'efface le chiffre pour cette position
                            je retourne false   // essai suivant à la position précédente (backtracking)
                        }
                        Le truc est de retourner à ses appelants le fait qu'on s'est rendu au bout (true) ou pas (false)
                        Comme je l'ai indiqué selon les conseils d'autres personnes, on peut faire beaucoup plus rapide.

                        Tu as un vector de vector. Je ne suis pas un expert en performances en C++, mais c'est sûrement plus lent qu'un simple array malgré mes calculs d'indices.

                        -
                        Edité par PierrotLeFou 29 septembre 2021 à 3:43:07

                        • Partager sur Facebook
                        • Partager sur Twitter

                        Le Tout est souvent plus grand que la somme de ses parties.

                          29 septembre 2021 à 9:49:47

                          Effectivement comme me l'a déjà fait remarquer @JadeSalina je vais modifier le code pour passer par des array.

                          Je pense que ça devrait améliorer les performances.

                          Sinon j'ai commencé à regarder ton code

                          Là l'idée maintenant est que je réussisse à implémenter la recherche de singleton mais c'est chaud.

                          avec mon programme ci dessus sur une grille de ce genre il trouve bien la solution mais faut pas être pressé.

                          Grille
                          +-----+-----+-----+
                          |8 0 0|0 0 0|0 2 0|
                          |0 0 0|1 0 0|8 0 0|
                          |0 0 0|0 7 0|0 0 0|
                          +-----+-----+-----+
                          |4 2 0|0 0 0|6 0 0|
                          |5 0 0|7 0 0|0 0 0|
                          |0 0 0|3 0 0|0 0 1|
                          +-----+-----+-----+
                          |0 0 0|0 4 0|0 5 0|
                          |0 0 0|0 5 0|0 0 7|
                          |0 1 0|0 0 0|0 0 0|
                          +-----+-----+-----+
                          
                          Solution
                          +-----+-----+-----+
                          |8 7 3|5 9 6|1 2 4|
                          |9 5 4|1 3 2|8 7 6|
                          |1 6 2|4 7 8|5 9 3|
                          +-----+-----+-----+
                          |4 2 7|8 1 9|6 3 5|
                          |5 3 1|7 6 4|2 8 9|
                          |6 8 9|3 2 5|7 4 1|
                          +-----+-----+-----+
                          |7 9 6|2 4 1|3 5 8|
                          |2 4 8|6 5 3|9 1 7|
                          |3 1 5|9 8 7|4 6 2|
                          +-----+-----+-----+
                          
                          Durée = 17.1111622390s
                          



                          • Partager sur Facebook
                          • Partager sur Twitter
                            29 septembre 2021 à 12:49:12

                            Pour ma preuve de concept, j'avais utilisé un mdarray (C++23), mais un std::array ça sera bien aussi. Le gain ne sera pas visible à l'initialisation du programme.

                            Si en revanche tu recherches une solution par récursion, là cela pourra etre bien plus sensible.

                            PS: on avait eu un fil sur le sujet de de défi de solveur de sudoku il y a quelques mois.

                            • Partager sur Facebook
                            • Partager sur Twitter
                            C++: Blog|FAQ C++ dvpz|FAQ fclc++|FAQ Comeau|FAQ C++lite|FAQ BS| Bons livres sur le C++| PS: Je ne réponds pas aux questions techniques par MP.
                              29 septembre 2021 à 14:54:29

                              @lmghs:
                              Le lien que je donne est celui dont tu parles. Je ne t'ai pas cité explicitement, désolé.
                              • Partager sur Facebook
                              • Partager sur Twitter

                              Le Tout est souvent plus grand que la somme de ses parties.

                                29 septembre 2021 à 15:46:56

                                @PierrotLeFou avec la non reconnaissance du lien par le forum, j'avais raté la présence d'un lien. Au temps pour moi. ^^'
                                • Partager sur Facebook
                                • Partager sur Twitter
                                C++: Blog|FAQ C++ dvpz|FAQ fclc++|FAQ Comeau|FAQ C++lite|FAQ BS| Bons livres sur le C++| PS: Je ne réponds pas aux questions techniques par MP.
                                  29 septembre 2021 à 16:40:45

                                  @PierrotLeFou je suppose que je peux continuer le fil du défi de solver de sudoku même si c'est un peu ancien ?

                                  Je vais pour le moment simplement modifier le std::vector en array.

                                  @lmghs tu es déjà en train de tester c++23 ? intéressant.

                                  • Partager sur Facebook
                                  • Partager sur Twitter
                                    29 septembre 2021 à 17:20:54

                                    Duncan4031 a écrit:

                                    @PierrotLeFou je suppose que je peux continuer le fil du défi de solver de sudoku même si c'est un peu ancien ?

                                    Je vais pour le moment simplement modifier le std::vector en array.

                                    @lmghs tu es déjà en train de tester c++23 ? intéressant.


                                    On peut citer un autre sujet, mais ce n'est pas conseillé de continuer la discussion sur un sujet plus ancien.

                                    Tu peux continuer sur le sujet courant.

                                    • Partager sur Facebook
                                    • Partager sur Twitter

                                    Le Tout est souvent plus grand que la somme de ses parties.

                                      29 septembre 2021 à 17:25:45

                                      Oui. Je trouve la syntaxe du quintuple std::array bien lourde (et celle du double aussi...), j'avais déjà été séduit par les mdspan, d'autant qu'ils permettent d'exprimer la notion de groupe ici: tous les algos d'analyses seront strictement les memes entre ligne, colonne ou carré.

                                      Entre temps, Lundi j'ai découvert https://github.com/jfalcou/kiwaku, à tester

                                      EDIT: tentative de contourner l'URLification du forum.

                                      PS: kwk risque d’être ardu pour un débutant d'autant que la doc a l'air d’être bien cachée : il faut lire les tests. A voir quand la présentation de Joel (de lundi) sera mise en ligne histoire de donner quelques points de départ

                                      -
                                      Edité par lmghs 29 septembre 2021 à 18:21:25

                                      • Partager sur Facebook
                                      • Partager sur Twitter
                                      C++: Blog|FAQ C++ dvpz|FAQ fclc++|FAQ Comeau|FAQ C++lite|FAQ BS| Bons livres sur le C++| PS: Je ne réponds pas aux questions techniques par MP.
                                        29 septembre 2021 à 18:05:13

                                        @lmghs le lien affiche erreur 404

                                        • Partager sur Facebook
                                        • Partager sur Twitter
                                          29 septembre 2021 à 18:11:03

                                          La virgule à la fin est de trop. Autrement ça marche.

                                          edit: j'ai une version avec bitmap qui semble fonctionner et qui semble environ 4 fois plus rapide que ma version de base.

                                          (voir l'autre post)

                                          -
                                          Edité par PierrotLeFou 30 septembre 2021 à 8:23:53

                                          • Partager sur Facebook
                                          • Partager sur Twitter

                                          Le Tout est souvent plus grand que la somme de ses parties.

                                            30 septembre 2021 à 19:21:34

                                            Voici ma seconde version du solveur de Sudoku avec des bitmap.
                                            Il y a un bitmap pour chaque ligne, colonne, carré. Il y a un bit pour chaque chiffre dans un bitmap.
                                            Le bit est allumé si je peux placer le chiffre à cet endroit et éteint dans le cas contraire.
                                            Je n'ai pas à parcourir chaque ligne, colonne, carré pour savoir si le chiffre s'y trouve déjà. Ça se fait plus rapidement en combinant les 3 bitmap.
                                            Par contre, le temps pour allumer les 3 bits pour chaque choix et les éteindre n'est sans doute pas négligeable.
                                            J'ai utilisé des macro dans l'espoir que le code sera plus lisible (...).
                                            On pourrait gagner en efficacité si on avait un array de 81 structures donnant les bons bitmap pour chaque position.
                                            Ils seraient calculés au début lors de l'initialisation.
                                            J'ai compilé les deux versions avec l'option -O3 et je suis à la limite de précision de mon ordi.
                                            C'est donc difficile de savoir dans quel rapport le second code est plus efficace que le premier.
                                            -
                                            // Mon solveur de Sudoku - 2.0.
                                            #include <iostream>
                                            #include <array>
                                            #include <string>
                                            #include <fstream>
                                            #include <chrono>
                                            typedef unsigned int bitmap;
                                            // Structure associée à la grille.
                                            typedef struct Work Work;
                                            struct Work {
                                                std::array<int, 81> grid;
                                                std::array<bitmap, 9> lines;
                                                std::array<bitmap, 9> columns;
                                                std::array<bitmap, 9> squares;
                                            };
                                            // Accès aux bitmap.
                                            #define setbit(w,b) ((w)|=1<<(b))
                                            #define offbit(w,b) ((w)&=(~(1<<(b))))
                                            #define getbit(w,b) (((w)>>(b))&1)
                                            #define line(l) (l/9)
                                            #define column(c) (c%9)
                                            #define square(s) ((s)/27*3+(s)%9/3)
                                            // Placer un chiffre dans la prochaine position libre.
                                            bool placeNumber(Work &work, int pos) {
                                                while(pos < 81 && work.grid[pos]) pos++;
                                                if(pos >= 81) return true;
                                                // Extraire les nombres qu'on peut placer.
                                                bitmap mask = work.lines[line(pos)] & work.columns[column(pos)] & work.squares[square(pos)];
                                                for(int bit = 1; bit <= 9; bit++) {
                                                    if(getbit(mask, bit)) {
                                                        work.grid[pos] = bit;
                                                        // Éteindre les 3 bits
                                                        offbit(work.lines[line(pos)], bit); offbit(work.columns[column(pos)], bit); offbit(work.squares[square(pos)], bit);
                                                        if(placeNumber(work, pos+1)) return true;
                                                        // Rallumer les 3 bits
                                                        setbit(work.lines[line(pos)], bit); setbit(work.columns[column(pos)], bit); setbit(work.squares[square(pos)], bit);
                                                    }
                                                }
                                                work.grid[pos] = 0;
                                                return false;
                                            }
                                            // Programme principal.
                                            int main() {
                                                Work work;
                                                const std::string name{ "sudoku.t" };
                                                // Initialiser les bitmap: 1=disponible, 0=dans la case
                                                bitmap mask = ((1<<9) - 1) << 1;   // bits 1 à 9 allumés.
                                                for(int i = 0; i < 9; i++) {
                                                    work.lines[i] = mask;
                                                    work.columns[i] = mask;
                                                    work.squares[i] = mask;
                                                }
                                                // Lecture de la grille de départ.
                                                std::ifstream file(name);
                                                if(!file) {
                                                    std::cerr << "Impossible d'ouvrir le fichier " << name << std::endl;
                                                    exit(1);
                                                }
                                                int pos = 0;
                                                for(int i = 0; i < 9; i++) {
                                                    std::string text;
                                                    std::getline(file, text);
                                                    for(int c = 0; c < 9; c++) {
                                                        int tmp;
                                                        if(text[c]==' ') tmp=0; else tmp=text[c]-'0';
                                                        if(tmp) {
                                                            if(getbit(work.lines[line(pos)], tmp) & getbit(work.columns[column(pos)], tmp) & getbit(work.squares[square(pos)], tmp)) {
                                                                offbit(work.lines[line(pos)], tmp); offbit(work.columns[column(pos)], tmp); offbit(work.squares[square(pos)], tmp);
                                                            } else { // erreur
                                                                std::cerr << "Grille invalide, ligne " << line(pos)+1 << ", colonne " << column(pos)+1 << std::endl;
                                                            } // erreur
                                                        } // tmp
                                                        work.grid[pos++] = tmp;
                                                    } // c
                                                } // i
                                                // Résoudre le jeu.
                                                auto start = std::chrono::high_resolution_clock::now();
                                                bool solution = placeNumber(work, 0);
                                                auto elapsed = std::chrono::high_resolution_clock::now() - start;
                                                long long microseconds = std::chrono::duration_cast<std::chrono::microseconds>(elapsed).count();
                                                std::cout << microseconds << " microsecondes" << std::endl;
                                                if(solution) {
                                                    // Afficher la grille.
                                                    for(int l = 0; l < 81; l+=9) {
                                                        if(l > 0 && l%27 == 0) std::cout << std::endl;
                                                        for(int c = 0; c < 9; c++) {
                                                            if (c > 0 && c%3 == 0) std::cout << " ";
                                                            std::cout << work.grid[l+c];
                                                        }
                                                        std::cout << std::endl;
                                                    }
                                                } else {
                                                    std::cerr << "Cette grille n'as pas de solution" << std::endl;
                                                }
                                                return 0;
                                            }
                                            • Partager sur Facebook
                                            • Partager sur Twitter

                                            Le Tout est souvent plus grand que la somme de ses parties.

                                              30 septembre 2021 à 22:57:18

                                              Je ne connais pas l'usage des bitmaps. Une piste à creuser à priori.

                                              De mon côté j'essaie de résoudre le maximum de cases nues et cachées (singleton) pour avoir à utiliser le backtrack le moins possible.

                                              Pas simple à programmer.

                                              • Partager sur Facebook
                                              • Partager sur Twitter
                                                1 octobre 2021 à 1:36:29

                                                Ça consiste en un ensemble de bits qu'on peut mettre dans un entier par exemple (unsigned int dans mon cas).
                                                Dans mon code, le bit 0 de l'entier ne sert à rien. Le bit N correspondant au chiffre N me dit si le chiffre peut être placé dans ma grille.
                                                Par exemple, si le bit 1 est allumé, ça veut dire que je peux placer le chiffre 1.
                                                J'ai besoin de le savoir pour la ligne, la colonne et le carré où se trouve la case que je suis en train d'examiner.
                                                J'avais jeté un coup d'oeil sur l'idée des cases nues et cachées (singleton). Je n'ai pas encore examiné cela en profondeur.
                                                Si ça fait passer le nombre d'appels récursifs de 81 à 9 ou 10, ça peut valoir la peine si le temps de calcul n'est pas trop long.
                                                En fait, je n'ai pas tout à fait 81 appels. Je dois soustraire le nombre de cases déjà présentes au début.
                                                Le singleton a peut-être le même effet.

                                                edit:
                                                Voici un extrait d'un lien fourni par lmghs:
                                                «Singles:
                                                Any cells which have only one candidate can safely be assigned that value.
                                                It is very important whenever a value is assigned to a cell, that this value is also excluded as a candidate from all other blank cells sharing the same
                                                row, column and box.»
                                                Que se passe-t-il si par la suite ça ne marche pas? Qu'est-ce qu'on a réellement sauvé?
                                                Cet extrait laisse supposer que quelqu'un serait tenté d'essayer tous les chiffres à une position donnée.
                                                Ce n'est pas ce que je fais, je choisis les candidats vraisemblables.
                                                Si le candidat est uniqque à un endroit donné à un moment donné, c'est parce que d'autres chiffres ont été placés avant celui-ci.
                                                Ces choix n'étaient pas nécessairement corrects ou souhaitables.

                                                -
                                                Edité par PierrotLeFou 1 octobre 2021 à 3:17:29

                                                • Partager sur Facebook
                                                • Partager sur Twitter

                                                Le Tout est souvent plus grand que la somme de ses parties.

                                                  1 octobre 2021 à 9:06:21

                                                  En fait avec la recherche de singleton ce sont des boucles qui s’emboîtent. On teste pour chaque chiffre s'il est unique.

                                                  Si oui on remplit la case et ainsi de suite.

                                                  Une fois que tous les chiffres uniques sont trouvés on peut lancer le backtrack pour les cases qui restent.

                                                  • Partager sur Facebook
                                                  • Partager sur Twitter
                                                    1 octobre 2021 à 14:39:09

                                                    Si je lance le processus au début, il y a peu de chance que je trouve des cases uniques.
                                                    À partir de quel moment cela en vaudra-t-il la peine?
                                                    Et si je ne me rend pas au bout, je fais quoi avec ces cases? Je les laisse là ou je les enlève?
                                                    • Partager sur Facebook
                                                    • Partager sur Twitter

                                                    Le Tout est souvent plus grand que la somme de ses parties.

                                                      1 octobre 2021 à 16:39:01

                                                      Tu lances la recherche de singleton au début afin de réduire le nombre de cases vides pour le backtrack. 

                                                      Je viens de tester ton programme, il est super rapide. J'ai juste remplacer les espaces par des points car la grille est illisible sinon.

                                                      Je me demande si ça vaut le coup de chercher des singletons, mais pourquoi pas.

                                                      Si tu veux t'amuser à tester voici un lien avec des grilles difficiles pour un humain

                                                      http://magictour.free.fr/top1465

                                                      -
                                                      Edité par Duncan4031 1 octobre 2021 à 17:15:27

                                                      • Partager sur Facebook
                                                      • Partager sur Twitter
                                                        1 octobre 2021 à 18:08:53

                                                        Si je lance la recherche au début, la probabilité d'avoir des singleton est très faible.
                                                        Sauf si le nombre de contraintes est très élevé (comme dans le lien que tu mentionnes)
                                                        Et précisément dans ce cas, plus le nombre de contraintes sera élevé, plus j'irai rapidement.
                                                        Je vais essayer d'en tester quelques uns.

                                                        edit: j'en ai testé un et c'est très rapide.

                                                        Je pense m'écrire une fonction qui vérifie si la solution est bien correcte.

                                                        Ça devrait être assez facile avec mes bitmap.

                                                        edit2:

                                                        J'ai écrit la fonction. Ou bien je n'ai pas d'erreur ... ou bien la fonction est buggée ...

                                                        Ça fait une grosse différence de compiler avec l'optiion -O3

                                                        Je suis sur Windows 10 et mon compilateur C++ est le suivant:
                                                        g++ (MinGW-W64 x86_64-posix-seh, built by Brecht Sanders) 9.3.1 20200703                                                
                                                        Copyright (C) 2019 Free Software Foundation, Inc.                                                                       

                                                        -
                                                        Edité par PierrotLeFou 1 octobre 2021 à 19:38:14

                                                        • Partager sur Facebook
                                                        • Partager sur Twitter

                                                        Le Tout est souvent plus grand que la somme de ses parties.

                                                          1 octobre 2021 à 22:26:42

                                                          Je viens de compiler avec le switch O3 , je ne vois pas de différence. D'habitude je suis avec O2

                                                          Ma version du compilateur est la dernière proposée

                                                          $ g++ --version
                                                          g++ (Ubuntu 11.2.0-7ubuntu2) 11.2.0
                                                          Copyright (C) 2021 Free Software Foundation, Inc.
                                                          This is free software; see the source for copying conditions.  There is NO
                                                          warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE
                                                          • Partager sur Facebook
                                                          • Partager sur Twitter
                                                            2 octobre 2021 à 1:10:34

                                                            Je ne compile jamais avec -O2 donc je ne sais pas.
                                                            J'avais fait mes tests sans l'option -O*
                                                            C'est possible que la différence entre -oO2 et -O3 soit minime.

                                                            Quand on y pense, c'est peut-être idiot de choisir -O1, -O2, -O3. Je dis à mon compilateur «optimise un peu, mais pas trop ...»

                                                            edit:
                                                            Si je regarde les alternatives pour restreindre les candidats, je me refère au lien suivant donné par lmghs sur l'autre post:
                                                            http://www.angusj.com/sudoku/hints.php
                                                            Avec les bitmap, il n'est pas trop difficile de placer des chiffres dans les cases appropriées.
                                                            Mais si on ne trouve pas la solution, qu'est ce qu'on enlève?
                                                            J'ai juste essayé de placer tous les single à chaque niveau sans les enlever et je me retrouve dans une boucle infinie.

                                                            -
                                                            Edité par PierrotLeFou 2 octobre 2021 à 7:38:35

                                                            • Partager sur Facebook
                                                            • Partager sur Twitter

                                                            Le Tout est souvent plus grand que la somme de ses parties.

                                                              2 octobre 2021 à 9:08:17

                                                              L'idée est la suivante :

                                                              Pour chaque carré 3x3 si la case est vide je passe en revu les nombres de 1 à 9 en vérifiant qu'il n'est pas déjà dans une autre case dans le carré, la ligne ou la colonne.

                                                              Si pour la case je ne trouve qu'une seule possibilité je lui affecte le nombre trouvé.

                                                              Puis je fais de même pour chaque ligne colonne.

                                                              Reste plus qu'à programmer ça correctement.

                                                              Edit: j'essaie de m'informer sur l'utilisation des bitmap. il y a la librairie bitset. si tu as de la lecture à me conseiller.

                                                              -
                                                              Edité par Duncan4031 2 octobre 2021 à 10:15:36

                                                              • Partager sur Facebook
                                                              • Partager sur Twitter

                                                              Solver sudoku

                                                              × Après avoir cliqué sur "Répondre" vous serez invité à vous connecter pour que votre message soit publié.
                                                              • Editeur
                                                              • Markdown