Partage
  • Partager sur Facebook
  • Partager sur Twitter

[FAIT][Défis] #3 : Des sudokus en folie !

Venez vous entraîner !

    18 septembre 2011 à 22:50:48

    J'ai testé la grille sur mon programme et pareil (après avoir attendu longtemps... xD), il ne me retourne rien (enfn, la grille telle quelle). :-°
    Le site qui a mit cette grille en ligne à dû se tromper quelque part. :(
    • Partager sur Facebook
    • Partager sur Twitter
      19 septembre 2011 à 6:17:31

      Citation : Pouet_forever

      J'ai testé la grille sur mon programme et pareil (après avoir attendu longtemps... xD), il ne me retourne rien (enfn, la grille telle quelle). :-°


      Moi aussi, j'ai attendu longtemps. Très longtemps, en fait (>40s). :-°

      Je me rends compte qu'un backtracking même ultra-optimisé (je maintiens que ma version peut résoudre n'importe quelle grille valide en quelques millisecondes, jusqu'à preuve du contraire bien sûr), reste désarmé devant une grille fausse (le principe est de faire sortir la solution au début, s'il n'y en a pas, ben... c'est embêtant :p ).

      Ce genre de problème ne se pose pas avec un DLX, par exemple: je viens de tester, le programme répond instantanément qu'il n'y a pas de solution.

      [edit]: En fait, théoriquement, dans un cas moyen, un backtracking ne devrait pas avoir trop de difficultés à terminer, vu qu'on élague énormément de branches, et les blocages sont censés se produire assez haut dans l'arbre. Visiblement, il doit néanmoins subsister des cas particuliers...
      • Partager sur Facebook
      • Partager sur Twitter
        19 septembre 2011 à 7:00:00

        Citation : Pouet_forever


        @che > Ca prend très peu de temps à faire comme programme si tu fais un truc basique. :)


        J'imagine, que tu dois avoir raison :)

        J'essayerais ...
        • Partager sur Facebook
        • Partager sur Twitter
        🍊 - Étudiant - Codeur en C | Zeste de Savoir apprenez avec une communauté | Articles  - ♡ Copying is an act of love.
          21 septembre 2011 à 22:59:47

          Bon, je suis content de voir que finalement je ne m'était pas trompé. :)
          Combien de participants ? 1 ! :-°
          • Partager sur Facebook
          • Partager sur Twitter
          Anonyme
            21 septembre 2011 à 23:22:18

            Je participerais volontiers, si j'avais plus de temps...
            • Partager sur Facebook
            • Partager sur Twitter
              22 septembre 2011 à 0:16:57

              On connait la chanson tkt. :-°
              Un jour peut-être...
              • Partager sur Facebook
              • Partager sur Twitter
                22 septembre 2011 à 1:09:35

                Pouet_forever, provoquant jusqu'au bout!
                • Partager sur Facebook
                • Partager sur Twitter
                  22 septembre 2011 à 3:56:20

                  Bonjour,

                  J'ai testé avec la grille de Pouet_forever et j'ai la solution instantanément.(bah oui, je me suis trompé en recopiant la grille.) >_<

                  Pour changer un peu, j'ai voulu essayer de jouer certains coups triviaux avant de lancer le bactrack(recherche des singletons).
                  Dans le cas de la grille testée, ça n'apporte rien, le bactrack est effectué complètement.
                  J'ai testé 4, 5 grilles et ça semble rester très rapide.

                  attention , code moche... :-°
                  #include <stdio.h>
                  #include <stdlib.h>
                  
                  #define N   9
                  
                  typedef struct
                  {
                      int pos;
                      int n;
                  } cell;
                  
                  
                  
                  cell cells[N * N];
                  int possibility[N * N][N + 1];
                  
                  
                  int cmp(void const *p, void const *q)
                  {
                      return ((cell *)p)->n - ((cell *)q)->n;
                  }
                  
                  
                  
                  void grid_display(int *g)
                  {
                      for(int i = 0; i < N; i++)
                      {
                          for(int j = 0; j < N; j++)
                              printf("%d", g[i * N + j]);
                          puts("");
                      }
                      puts("");
                  }
                  
                  
                  int check_square(int *g, int row, int col, int v)
                  {
                      int ox = (col / 3) * 3;
                      int oy = (row / 3) * 3;
                  
                      for(int i = oy; i < oy + 3; i++)
                          for(int j = ox; j < ox + 3; j++)
                              if(g[i * N + j] == v)
                                  return 0;
                      return 1;
                  }
                  
                  
                  
                  int check_row_col(int *g, int row, int col, int v)
                  {
                      for(int i = 0; i < N; i++)
                          if(g[i * N + col] == v || g[row * N + i] == v)
                              return 0;
                      return 1;
                  }
                  
                  
                  int check_cell(int *g, int pos, int v)
                  {
                      int col = pos % N;
                      int row = pos / N;
                      return check_row_col(g, row, col, v) && check_square(g, row, col, v);
                  }
                  
                  
                  
                  int backtrack(int *g, int id)
                  {
                      int pos = cells[id].pos;
                      if(id == N * N)
                          return 1;
                      if(g[pos])
                          return backtrack(g, id + 1);
                      else
                      {
                          for(int k = 1; k <= N; k++)
                          {
                              if(possibility[pos][k])
                                  if(check_cell(g, pos, k))
                                  {
                                      g[pos] = k;
                                      if(backtrack(g, id + 1))
                                          return 1;
                                  }
                          }
                          g[pos] = 0;
                          return 0;
                      }
                  }
                  
                  
                  int singleton_block(int *g)
                  {
                      int n_singletons = 0;
                      for(int i = 0; i < N; i += 3)
                          for(int j = 0; j < N; j += 3)
                          {
                              int pos = 0;
                              for(int k = 1; k <= N; k++)
                              {
                                  int count = 0;
                                  for(int ii = i; ii < i + 3; ii++)
                                      for(int jj = j; jj < j + 3; jj++)
                                      {
                                          if(!g[ii * N + jj] && check_cell(g, ii * N + jj, k))
                                          {
                                              count++;
                                              pos =  ii * N + jj;
                                          }
                                      }
                                  if(count == 1)
                                  {
                                      g[pos] = k;
                                      n_singletons++;
                                  }
                              }
                          }
                      return n_singletons;
                  }
                  
                  
                  int singleton_col(int *g)
                  {
                      int n_singletons = 0;
                      for(int col = 0; col < N; col++)
                      {
                          int pos;
                          for(int k = 1; k <= N; k++)
                          {
                              int count = 0;
                              for(int row = 0; row < N; row++)
                              {
                                  if(!g[ row * N + col])
                                  {
                                      if(check_cell(g, row * N + col, k))
                                      {
                                          count++;
                                          pos =  row * N + col;
                                      }
                                  }
                              }
                              if(count == 1)
                              {
                                  g[pos] = k;
                                  n_singletons++;
                              }
                          }
                      }
                      return n_singletons;
                  }
                  
                  
                  int singleton_row(int *g)
                  {
                      int n_singletons = 0;
                      for(int row = 0; row < N; row++)
                      {
                          int pos;
                          for(int k = 1; k <= N; k++)
                          {
                              int count = 0;
                              for(int col = 0; col < N; col++)
                              {
                                  if(!g[ row * N + col])
                                  {
                                      if(check_cell(g, row * N + col, k))
                                      {
                                          count++;
                                          pos =  row * N + col;
                                      }
                                  }
                              }
                              if(count == 1)
                              {
                                  g[pos] = k;
                                  n_singletons++;
                              }
                          }
                      }
                      return n_singletons;
                  }
                  
                  
                  void solve(int *g)
                  {
                      int find = 0;
                      do
                      {
                          find = singleton_row(g) + singleton_col(g) + singleton_block(g);
                          for(int i = 0; i < N * N; i++)
                          {
                              int n = 0;
                              int last = 0;
                              if(!g[i])
                              {
                                  for(int k = 1; k <= N; k++)
                                      if(check_cell(g, i, k))
                                      {
                                          possibility[i][k] = 1;
                                          last = k;
                                          n++;
                                      }
                                  if(n == 1)
                                  {
                                      g[i] = last;
                                      find = 1;
                                  }
                              }
                              cells[i].pos = i;
                              cells[i].n = n;
                          }
                      }
                      while(find);
                  
                      qsort(cells, N * N, sizeof *cells, cmp);
                      backtrack(g, 0);
                  }
                  
                  int main(void)
                  {
                      int grid[N * N] =
                      {
                          0, 0, 0, 0, 0, 5, 0, 8, 0,
                          0, 0, 0, 0, 6, 1, 0, 4, 3,
                          0, 0, 0, 0, 0, 0, 0, 0, 0,
                          0, 1, 0, 5, 0, 0, 0, 0, 0,
                          0, 0, 0, 1, 0, 6, 0, 0, 0,
                          3, 0, 0, 0, 0, 0, 0, 0, 5,
                          5, 3, 0, 0, 0, 0, 0, 6, 1,
                          0, 0, 0, 0, 0, 0, 0, 0, 4,
                          0, 0, 0, 0, 0, 0, 0, 0, 0
                      };
                  
                  
                      solve(grid);
                  
                      grid_display(grid);
                  
                      return 0;
                  }
                  

                  81
                  123456789
                  456789123
                  789123456
                  214365897
                  365897214
                  897214365
                  531642978
                  642978531
                  978531642
                  
                  
                  Process returned 0 (0x0)   execution time : 0.016 s
                  Press any key to continue.


                  edit: correction d'une coquille dans singleton_block et suppresion d'un test inutile dans la fonction solve.
                  • Partager sur Facebook
                  • Partager sur Twitter
                  Zeste de Savoir, le site qui en a dans le citron !
                    22 septembre 2011 à 5:38:13

                    @yosh: Merci de ton commentaire et désolé du retard de la réponse. En effet ça aurait été plus logique de traiter les cases déjà remplies dans la fonction solve, c'est pas très malin ce que j'ai fait là. Par "ça ne finit pas", j'entendais évidemment par là que ça risquait de prendre assez longtemps à finir. Enfin entre une chose et une autre je n'ai toujours pas eu le temps d'améliorer mon programme.

                    @GurneyH: Ca m'étonnait un peu que tu trouves une solution alors qu'un backtracking normal n'en trouve pas, mais j'ai compris pourquoi,


                    void get_grid(int *grid)
                    {
                      int i, j;
                      for(i = 0; i < N; i++, getchar())
                        for(j = 0; j < N; j++)
                        {
                          int tmp = getchar();
                          grid[i*N+j] = tmp == ' ' ? 0 : tmp - '0';
                        }
                    }
                    
                    int main(void)
                    {
                      /*int grid[N * N] = {
                            0, 0, 0, 0, 0, 5, 0, 8, 0,
                            0, 0, 0, 0, 6, 1, 0, 4, 3,
                            0, 0, 0, 0, 0, 0, 0, 0, 0,
                            0, 1, 0, 5, 0, 0, 0, 0, 0,
                            0, 0, 0, 1, 0, 6, 0, 0, 0,
                            3, 0, 0, 0, 0, 0, 0, 0, 5,
                            5, 3, 0, 0, 0, 0, 0, 6, 1,
                            0, 0, 0, 0, 0, 0, 0, 0, 4,
                            0, 0, 0, 0, 0, 0, 0, 0, 0
                            };*/
                      int grid[N*N];
                      get_grid(grid);
                      grid_display(grid);
                    
                      //solve(grid);
                    
                      //grid_display(grid);
                    
                      return 0;
                    }
                    

                    ~/tmp$ cat grid.txt 
                    000005080
                    000601043
                    000000000
                    010500000
                    000106000
                    300000005
                    530000061
                    000000004
                    000000000
                    ~/tmp$ ./a.out < grid.txt > test1

                    int main(void)
                    {
                      int grid[N * N] = {
                            0, 0, 0, 0, 0, 5, 0, 8, 0,
                            0, 0, 0, 0, 6, 1, 0, 4, 3,
                            0, 0, 0, 0, 0, 0, 0, 0, 0,
                            0, 1, 0, 5, 0, 0, 0, 0, 0,
                            0, 0, 0, 1, 0, 6, 0, 0, 0,
                            3, 0, 0, 0, 0, 0, 0, 0, 5,
                            5, 3, 0, 0, 0, 0, 0, 6, 1,
                            0, 0, 0, 0, 0, 0, 0, 0, 4,
                            0, 0, 0, 0, 0, 0, 0, 0, 0
                            };
                      grid_display(grid);
                    
                      //solve(grid);
                    
                      //grid_display(grid);
                    
                      return 0;
                    }
                    

                    ~/tmp$ gcc -std=c99 main.c
                    ~/tmp$ ./a.out > test2
                    ~/tmp$ diff test1 test2
                    2c2
                    < 000601043
                    ---
                    > 000061043


                    la position du 6 dans la deuxième ligne n'est pas "la bonne". En testant avec la grille donnée par Pouet, ça ne trouve pas de solution non plus. Enfin à mon avis la grille est fausse mais bon.

                    Par contre, en essayant ton code avec ce qui avait été pour moi le pire des cas, ça m'a donné :
                    ~/tmp$ ./a.out < grille2.txt 
                    000000000
                    000003085
                    001020000
                    000507000
                    004000100
                    090000000
                    500000073
                    002010000
                    000040009
                    
                    11
                    967958321
                    920173685
                    351624097
                    103597842
                    874236150
                    295481736
                    519862473
                    742319568
                    638745219

                    donc soit je me sers mal de ton code, soit il y a un petit problème quelque part.
                    Pour cette grille, j'avais eu comme résultat (après que mon PC ait ramé pendant une bonne vingtaine de secondes, mais ça faut pas le dire :-° ) :
                    ~/Dropbox/Programming/C/sudoku$ ./a.out < grille2.txt 
                    000000000
                    000003085
                    001020000
                    000507000
                    004000100
                    090000000
                    500000073
                    002010000
                    000040009
                    
                    987654321
                    246173985
                    351928746
                    128537694
                    634892157
                    795461832
                    519286473
                    472319568
                    863745219
                    • Partager sur Facebook
                    • Partager sur Twitter
                      22 septembre 2011 à 5:46:11

                      J'avais un doute en recopiant la grille, mais je ne voyait pas le soucis... :-°

                      Je corrige(j'essaye), le problême que tu as vu.
                      Je venais de voir que sur certaines grilles, c'était incorrect.

                      edit:

                      Coquille trouvée dans la fonction singleton_block c'est corrigé.
                      Et avec la grille de shaddan.
                      #include <stdio.h>
                      #include <stdlib.h>
                      
                      #define N   9
                      
                      typedef struct
                      {
                          int pos;
                          int n;
                      } cell;
                      
                      
                      
                      cell cells[N * N];
                      int possibility[N * N][N + 1];
                      
                      
                      int cmp(void const *p, void const *q)
                      {
                          return ((cell *)p)->n - ((cell *)q)->n;
                      }
                      
                      
                      
                      void grid_display(int *g)
                      {
                          for(int i = 0; i < N; i++)
                          {
                              for(int j = 0; j < N; j++)
                                  printf("%d", g[i * N + j]);
                              puts("");
                          }
                          puts("");
                      }
                      
                      
                      int check_square(int *g, int row, int col, int v)
                      {
                          int ox = (col / 3) * 3;
                          int oy = (row / 3) * 3;
                      
                          for(int i = oy; i < oy + 3; i++)
                              for(int j = ox; j < ox + 3; j++)
                                  if(g[i * N + j] == v)
                                      return 0;
                          return 1;
                      }
                      
                      
                      
                      int check_row_col(int *g, int row, int col, int v)
                      {
                          for(int i = 0; i < N; i++)
                              if(g[i * N + col] == v || g[row * N + i] == v)
                                  return 0;
                          return 1;
                      }
                      
                      
                      int check_cell(int *g, int pos, int v)
                      {
                          int col = pos % N;
                          int row = pos / N;
                          return check_row_col(g, row, col, v) && check_square(g, row, col, v);
                      }
                      
                      
                      
                      int backtrack(int *g, int id)
                      {
                          int pos = cells[id].pos;
                          if(id == N * N)
                              return 1;
                          if(g[pos])
                              return backtrack(g, id + 1);
                          else
                          {
                              for(int k = 1; k <= N; k++)
                              {
                                  if(possibility[pos][k])
                                      if(check_cell(g, pos, k))
                                      {
                                          g[pos] = k;
                                          if(backtrack(g, id + 1))
                                              return 1;
                                      }
                              }
                              g[pos] = 0;
                              return 0;
                          }
                      }
                      
                      
                      int singleton_block(int *g)
                      {
                          int n_singletons = 0;
                          for(int i = 0; i < N; i += 3)
                              for(int j = 0; j < N; j += 3)
                              {
                                  int pos = 0;
                                  for(int k = 1; k <= N; k++)
                                  {
                                      int count = 0;
                                      for(int ii = i; ii < i + 3; ii++)
                                          for(int jj = j; jj < j + 3; jj++)
                                          {
                                              if(!g[ii * N + jj] && check_cell(g, ii * N + jj, k))
                                              {
                                                  count++;
                                                  pos =  ii * N + jj;
                                              }
                                          }
                                      if(count == 1)
                                      {
                                          g[pos] = k;
                                          n_singletons++;
                                      }
                                  }
                              }
                          return n_singletons;
                      }
                      
                      
                      
                      int singleton_col(int *g)
                      {
                          int n_singletons = 0;
                          for(int col = 0; col < N; col++)
                          {
                              int pos = 0;
                              for(int k = 1; k <= N; k++)
                              {
                                  int count = 0;
                                  for(int row = 0; row < N; row++)
                                  {
                                      if(!g[ row * N + col])
                                      {
                                          if(check_cell(g, row * N + col, k))
                                          {
                                              count++;
                                              pos =  row * N + col;
                                          }
                                      }
                                  }
                                  if(count == 1)
                                  {
                                      g[pos] = k;
                                      n_singletons++;
                                  }
                              }
                          }
                          return n_singletons;
                      }
                      
                      
                      int singleton_row(int *g)
                      {
                          int n_singletons = 0;
                          for(int row = 0; row < N; row++)
                          {
                              int pos = 0;
                              for(int k = 1; k <= N; k++)
                              {
                                  int count = 0;
                                  for(int col = 0; col < N; col++)
                                  {
                                      if(!g[ row * N + col])
                                      {
                                          if(check_cell(g, row * N + col, k))
                                          {
                                              count++;
                                              pos =  row * N + col;
                                          }
                                      }
                                  }
                                  if(count == 1)
                                  {
                                      g[pos] = k;
                                      n_singletons++;
                                  }
                              }
                          }
                          return n_singletons;
                      }
                      
                      
                      void solve(int *g)
                      {
                          int find = 0;
                          do
                          {
                              find = singleton_row(g) + singleton_col(g) + singleton_block(g);
                              for(int i = 0; i < N * N; i++)
                              {
                                  int n = 0;
                                  int last = 0;
                                  if(!g[i])
                                  {
                                      for(int k = 1; k <= N; k++)
                                          if(check_cell(g, i, k))
                                          {
                                              possibility[i][k] = 1;
                                              last = k;
                                              n++;
                                          }
                                      if(n == 1)
                                      {
                                          g[i] = last;
                                          find = 1;
                                      }
                                  }
                                  cells[i].pos = i;
                                  cells[i].n = n;
                              }
                          }while(find);
                      
                          qsort(cells, N * N, sizeof *cells, cmp);
                          backtrack(g, 0);
                      
                      }
                      
                      
                      int main(void)
                      {
                          int grid[N * N] =
                          {
                              0,0,0,0,0,0,0,0,0,
                              0,0,0,0,0,3,0,8,5,
                              0,0,1,0,2,0,0,0,0,
                              0,0,0,5,0,7,0,0,0,
                              0,0,4,0,0,0,1,0,0,
                              0,9,0,0,0,0,0,0,0,
                              5,0,0,0,0,0,0,7,3,
                              0,0,2,0,1,0,0,0,0,
                              0,0,0,0,4,0,0,0,9
                          };
                      
                      
                          solve(grid);
                      
                          grid_display(grid);
                      
                          return 0;
                      }
                      


                      987654321
                      246173985
                      351928746
                      128537694
                      634892157
                      795461832
                      519286473
                      472319568
                      863745219
                      
                      
                      Process returned 0 (0x0)   execution time : 0.016 s
                      Press any key to continue.


                      le prétraitement avant le backtrack permet de remplir une quarantaine de cases dans le cas de cette grille.
                      • Partager sur Facebook
                      • Partager sur Twitter
                      Zeste de Savoir, le site qui en a dans le citron !
                        22 septembre 2011 à 9:13:49

                        Citation : Shaddan

                        @GurneyH: Ca m'étonnait un peu que tu trouves une solution alors qu'un backtracking normal n'en trouve pas, mais j'ai compris pourquoi,
                        [...]
                        la position du 6 dans la deuxième ligne n'est pas "la bonne". En testant avec la grille donnée par Pouet, ça ne trouve pas de solution non plus. Enfin à mon avis la grille est fausse mais bon.



                        J'aurais dû lire ton message plus tôt, j'ai vraiment eu peur en lisant le post de GurneyH :-° jusqu’à ce que je me rende compte de ce petit détail. C'est fort, quand même de tomber sur une bonne grille en se trompant... :p

                        Au passage, la grille telle que l'a copiée GurneyH possède apparemment plusieurs solutions (pas compté). Peut-être ceci explique cela (en partie)...

                        ________

                        Sinon, je voudrais bien poster mes codes, mais ils ne correspondent pas exactement à l'énoncé de l'exo, et je ne trouve pas de temps pour le faire. :( Au pire, je posterai tel quel.
                        • Partager sur Facebook
                        • Partager sur Twitter
                          22 septembre 2011 à 19:46:05

                          Citation : Mr21

                          Pouet_forever, provoquant jusqu'au bout!


                          Provoquant ? non. Réaliste, oui. ;)
                          • Partager sur Facebook
                          • Partager sur Twitter
                            22 septembre 2011 à 19:46:36

                            Les deux. :D
                            • Partager sur Facebook
                            • Partager sur Twitter
                            "If debbugging is the process of removing bugs, then programming must be the process of putting them in." (Edsger Dijkstra)
                            Anonyme
                              22 septembre 2011 à 21:58:14

                              Citation : Pouet_forever

                              On connait la chanson tkt. :-°
                              Un jour peut-être...



                              Tu pourrais me croire un jour. :p

                              Non là j'avoue que j'ai aussi un peu la flemme, mais c'est surtout un manque de temps.
                              • Partager sur Facebook
                              • Partager sur Twitter
                                22 septembre 2011 à 22:12:26

                                Bonsoir,

                                Bon, je n'ai pas eu le temps d'adapter totalement mon code à l'exercice, j'ai préféré me concentrer sur l'ajout de commentaires. Comme promis, voici un backtracking "évolué", censé pouvoir résoudre n'importe quelle grille 9x9 (valide) extrêmement rapidement. :)

                                Le principe est de comptabiliser au cours de la descente récursive le nombre de valeurs possibles pour chaque case, et choisir à chaque fois la case comportant le minimum de solution. Cette technique a pour caractéristique d'"amener" la solution extrêmement rapidement (vous pouvez vous amuser à ajouter un compteur d'entrées dans la fonction de backtracking et comparer avec une version standard pour vous en convaincre).

                                Le code ci-dessous comprends quelques optimisations supplémentaires, mais elles sont mineures, mis à part le fait d'utiliser un tableau de variables globales pour stocker le nombre de valeurs candidates pour chaque case, qui apporte aussi un gain non négligeable.

                                Code en C99, à compiler avec l'option -std=C99
                                #include <stdlib.h>
                                #include <stdio.h>
                                #include <stdbool.h>
                                #include <time.h>
                                
                                
                                
                                #define N       (3)
                                #define N_2     (N*N)
                                #define start   (1)
                                
                                
                                ////////////////////////////////////////////////////////////
                                //             Fonction d'affichage
                                ////////////////////////////////////////////////////////////
                                void affichage (int grille[N_2][N_2])
                                {
                                    for (int i=0; i<N_2; i++)
                                    {
                                        for (int j=0; j<N_2; j++)
                                        {
                                            printf( ((j+1)%N) ? "%d " : "%d|", grille[i][j]);
                                        }
                                        putchar('\n');
                                        if (!((i+1)%N))
                                            puts("------------------");
                                    }
                                    puts("\n\n");
                                }
                                
                                ////////////////////////////////////////////////////////////
                                //   Listes circulaires : définition et fonctions
                                ////////////////////////////////////////////////////////////
                                
                                typedef struct _node
                                {
                                    struct _node* prev;
                                    struct _node* next;
                                    int i, j, b;
                                    int nbValeursPossibles;
                                } CIRCL_LIST;
                                
                                CIRCL_LIST* createRoot (void)
                                {
                                    CIRCL_LIST* node = malloc(sizeof *node);
                                    node->prev = node->next = node;
                                    return node;
                                }
                                
                                CIRCL_LIST* circular_list_append (CIRCL_LIST* root)
                                {
                                    CIRCL_LIST* node = malloc(sizeof *node);
                                    node->prev = root->prev;
                                    node->next = root;
                                    root->prev->next = node;
                                    root->prev = node;
                                    return node;
                                }
                                
                                void deleteAll (CIRCL_LIST* root)
                                {
                                    CIRCL_LIST *next;
                                    for (CIRCL_LIST* iter = root->next; iter != root; iter = next)
                                    {
                                        next = iter->next;
                                        free (iter);
                                    }
                                    free (root);
                                }
                                
                                ////////////////////////////////////////////////////////////
                                //                  Resolution Sudoku
                                ////////////////////////////////////////////////////////////
                                
                                // Variables globales pour la mémorisation
                                bool existeSurLigne[N_2][N_2];
                                bool existeSurColonne[N_2][N_2];
                                bool existeSurBloc[N_2][N_2];
                                
                                
                                ////////////////////////////////////////////////////////////
                                //             Backtracking "adaptatif" :
                                //  décide dynamiquement la branche de l'arbre à explorer
                                ////////////////////////////////////////////////////////////
                                bool estValide (int grille[N_2][N_2], CIRCL_LIST* root)
                                {
                                    bool ret = false;
                                    if (root == root->next)  // la liste est vide
                                        return true;
                                
                                    // cherche la case avec un nombre de valeurs possibles minimal
                                    int min = N_2+1;
                                    CIRCL_LIST* pos = NULL;
                                    for (CIRCL_LIST* iter = root->next; iter != root && min != 0; iter = iter->next)
                                    {
                                        if (iter->nbValeursPossibles < min)
                                            pos = iter, min = iter->nbValeursPossibles;
                                    }
                                
                                    if (min == 0) return false;  // si le nombre de valeurs possibles vaut 0, on stoppe
                                
                                    int i = pos->i, j = pos->j, b = pos->b;
                                
                                    // supprimme temporairement le noeud de la liste
                                    pos->prev->next = pos->next;
                                    pos->next->prev = pos->prev;
                                
                                    // Crée une liste de voisins de la case sélectionnée (même ligne/colonne/bloc)
                                    CIRCL_LIST* voisins[2*(N_2-1)+(N-1)*(N-1)];
                                    unsigned n = 0;
                                    for (CIRCL_LIST* iter = root->next; iter != root; iter = iter->next)
                                        if ( iter->i == i || iter->j == j || iter->b == b )
                                            voisins[n++] = iter;
                                
                                    unsigned nb = 0;
                                    for (int k=0; k < N_2 && nb != min; k++)
                                    {
                                        // si on peut placer k+start
                                        if ( !existeSurLigne[i][k] && !existeSurColonne[j][k] && !existeSurBloc[b][k] )
                                        {
                                            // on actualise le champ 'nbValeursPossibles' dans la liste
                                            for (CIRCL_LIST** it = voisins; it != voisins+n; it++)
                                                if ( !existeSurLigne[(*it)->i][k] && !existeSurColonne[(*it)->j][k] && !existeSurBloc[(*it)->b][k] )
                                                    (*it)->nbValeursPossibles--;
                                
                                            // Ajoute k aux valeurs enregistrées
                                            existeSurLigne[i][k] = existeSurColonne[j][k] = existeSurBloc[b][k] = true;
                                
                                            if ( (ret = estValide(grille, root)) )
                                            {
                                                grille[i][j] = k+start;
                                                break;
                                            }
                                
                                            // Supprime k des valeurs enregistrées
                                            existeSurLigne[i][k] = existeSurColonne[j][k] = existeSurBloc[b][k] = false;
                                
                                            // on re-actualise le champ 'nbValeursPossibles' dans la liste
                                            for (CIRCL_LIST** it = voisins; it != voisins+n; it++)
                                                if ( !existeSurLigne[(*it)->i][k] && !existeSurColonne[(*it)->j][k] && !existeSurBloc[(*it)->b][k] )
                                                    (*it)->nbValeursPossibles++;
                                            nb++;
                                        }
                                    }
                                
                                    // avant de quitter, on restaure le noeud dans la liste
                                    pos->prev->next = pos;
                                    pos->next->prev = pos;
                                
                                    return ret;
                                }
                                
                                // compte (naïvement) le nombre de solutions possibles pour une case
                                int nb_possibles (int i, int j, int b)
                                {
                                    int ret = 0;
                                    for (int k=0; k < N_2; k++)
                                        if ( !existeSurLigne[i][k] && !existeSurColonne[j][k] && !existeSurBloc[b][k] )
                                            ret++;
                                    return ret;
                                }
                                
                                bool resolution (int grille[N_2][N_2])
                                {
                                    // Initialise les tableaux
                                    for (int i=0; i < N_2; i++)
                                        for (int j=0; j < N_2; j++)
                                            existeSurLigne[i][j] = existeSurColonne[i][j] = existeSurBloc[i][j] = false;
                                
                                    // Enregistre toutes les valeurs déjà présentes dans la grille
                                    int k;
                                    for (int i=0; i < N_2; i++)
                                        for (int j=0; j < N_2; j++)
                                            if ( (k = grille[i][j]) != 0)
                                                existeSurLigne[i][k-start] = existeSurColonne[j][k-start] = existeSurBloc[N*(i/N)+(j/N)][k-start] = true;
                                
                                    // Crée une liste circulaire doublement chainée contenant toutes les cases vides
                                    CIRCL_LIST *positions = createRoot(), *node = NULL;
                                    for (int i=0; i < N_2; i++)
                                        for (int j=0; j < N_2; j++)
                                            if ( grille[i][j] == 0 )
                                            {
                                                node = circular_list_append ( positions );
                                                node->i = i, node->j = j, node->b = N*(i/N)+(j/N);
                                                node->nbValeursPossibles = nb_possibles(i, j, node->b);
                                            }
                                
                                
                                    // Appelle la fonction récursive estValide()
                                    bool ret = estValide (grille, positions);
                                
                                    deleteAll (positions);
                                
                                    return ret;
                                }
                                
                                int main (void)
                                {
                                //    int grille[N_2][N_2] =
                                //    {
                                //        {0,0,0,0,0,0,0,0,0},
                                //        {0,0,0,0,0,3,0,8,5},
                                //        {0,0,1,0,2,0,0,0,0},
                                //        {0,0,0,5,0,7,0,0,0},
                                //        {0,0,4,0,0,0,1,0,0},
                                //        {0,9,0,0,0,0,0,0,0},
                                //        {5,0,0,0,0,0,0,7,3},
                                //        {0,0,2,0,1,0,0,0,0},
                                //        {0,0,0,0,4,0,0,0,9},
                                //    };
                                //
                                //
                                //    int grille[N_2][N_2] =
                                //    {
                                //        {9,0,0,1,0,0,0,0,5},
                                //        {0,0,5,0,9,0,2,0,1},
                                //        {8,0,0,0,4,0,0,0,0},
                                //        {0,0,0,0,8,0,0,0,0},
                                //        {0,0,0,7,0,0,0,0,0},
                                //        {0,0,0,0,2,6,0,0,9},
                                //        {2,0,0,3,0,0,0,0,6},
                                //        {0,0,0,2,0,0,9,0,0},
                                //        {0,0,1,9,0,4,5,7,0}
                                //    };
                                
                                    int grille[N_2][N_2] =
                                    {
                                        {0,0,0,0,0,0,0,3,1},
                                        {6,0,0,0,2,0,0,0,0},
                                        {0,0,0,0,7,0,0,0,0},
                                        {0,5,0,1,0,8,0,0,0},
                                        {2,0,0,0,0,0,6,0,0},
                                        {0,0,0,3,0,0,0,7,0},
                                        {0,0,0,0,4,0,2,0,0},
                                        {0,3,0,5,0,0,0,0,0},
                                        {7,0,0,0,0,0,0,0,0},
                                    };
                                
                                
                                    affichage(grille);
                                
                                    clock_t t1 = clock();
                                    resolution (grille);
                                    clock_t t2 = clock();
                                
                                    affichage(grille);
                                
                                    printf(" %gs\n\n", (double)(t2-t1)/CLOCKS_PER_SEC);
                                
                                    return 0;
                                }
                                


                                Cette technique n'est pourtant absolument pas la meilleure (ni même la bonne) manière de résoudre un sudoku de dimension supérieure (16x16 ou 25x25). J’espère présenter prochainement un autre code le permettant. :)

                                PS : Si quelqu'un trouve une grille valide mettant ce code en échec (temps de résolution > 0.1s), merci de le signaler.
                                • Partager sur Facebook
                                • Partager sur Twitter
                                  22 septembre 2011 à 23:25:09

                                  Citation : Pouet_forever

                                  Combien de participants ? 1 ! :-°


                                  Mon solveur avec backtracking simple.
                                  3 minutes pour trouver aucune solution à ton Sudoku.
                                  5 secondes pour trouver la solution au Sudoku de Shaddan.

                                  Le Sudoku est entré sur la ligne de commande.

                                  Il y a une fonction juste pour vérifier ce que le backtracking trouve.

                                  Ça affiche toutes les solutions trouvées, du coup ça donne tous les Sudoku possibles avec une grille d'entrée vide.

                                  #include <ctype.h>
                                  #include <stdio.h>
                                  #include <stdlib.h>
                                  #include <string.h>
                                  
                                  
                                  char grid[9][9];
                                  
                                  
                                  void print_grid(void)
                                  {
                                  	int line, col;
                                  	for (line = 0; line < 9; ++line) {
                                  		for (col = 0; col < 9; ++col)
                                  			putchar(grid[line][col]);
                                  		putchar('\n');
                                  	}
                                  }
                                  
                                  
                                  int is_grid_done(void)
                                  {
                                  	int line, col, sq;
                                  	int numbers_mask;
                                  
                                  	for (line = 0; line < 9; ++line)
                                  		for (col = 0; col < 9; ++col)
                                  			if (grid[line][col] < '1' || grid[line][col] > '9')
                                  				return 0;
                                  	
                                  	for (line = 0; line < 9; ++line) {
                                  		numbers_mask = 0;
                                  		for (col = 0; col < 9; ++col)
                                  			numbers_mask |= 1 << (grid[line][col] - '1');
                                  		if (numbers_mask != 0x1FF)
                                  			return 0;
                                  	}
                                  	
                                  	for (col = 0; col < 9; ++col) {
                                  		numbers_mask = 0;
                                  		for (line = 0; line < 9; ++line)
                                  			numbers_mask |= 1 << (grid[line][col] - '1');
                                  		if (numbers_mask != 0x1FF)
                                  			return 0;
                                  	}
                                  
                                  	for (sq = 0; sq < 9; ++sq) {
                                  		numbers_mask = 0;
                                  		for (line = sq / 3 * 3; line < sq / 3 * 3 + 3; ++line)
                                  			for (col = sq % 3 * 3; col < sq % 3 * 3 + 3; ++col)
                                  				numbers_mask |= 1 << (grid[line][col] - '1');
                                  		if (numbers_mask != 0x1FF)
                                  			return 0;
                                  	}
                                  
                                  	return 1;
                                  }
                                  
                                  
                                  int next_insert_pos(int *pline, int *pcol)
                                  {
                                  	int line = *pline, col = *pcol;
                                  	while (line < 9) {
                                  		if (grid[line][col] == '.') {
                                  			*pline = line;
                                  			*pcol = col;
                                  			return 1;
                                  		}
                                  		++col;
                                  		if (col == 9) {
                                  			col = 0;
                                  			++line;
                                  		}
                                  	}
                                  	return 0;
                                  }
                                  
                                  
                                  int ok_in_line_column(int line, int col, char c)
                                  {
                                  	int i;
                                  	for (i = 0; i < 9; ++i)
                                  		if (grid[line][i] == c || grid[i][col] == c)
                                  			return 0;
                                  	return 1;
                                  }
                                  
                                  
                                  int ok_in_square(int line, int col, char c)
                                  {
                                  	int x, y;
                                  	for (y = (line / 3) * 3; y < (line / 3) * 3 + 3; ++y)
                                  		if (y != line)
                                  			for (x = (col / 3) * 3; x < (col / 3) * 3 + 3; ++x)
                                  				if (x != col)
                                  					if (grid[y][x] == c)
                                  						return 0;
                                  	return 1;
                                  }
                                  
                                  
                                  int print_solutions(int ins_line, int ins_col)
                                  {
                                  	int res = 0;
                                  	if (next_insert_pos(&ins_line, &ins_col)) {
                                  		int c;
                                  		for (c = '1'; c <= '9'; ++c) {
                                  			if (ok_in_line_column(ins_line, ins_col, c) &&
                                  			    ok_in_square(ins_line, ins_col, c)) {
                                  				grid[ins_line][ins_col] = c;
                                  				res += print_solutions(ins_line, ins_col);
                                  				grid[ins_line][ins_col] = '.';
                                  			}
                                  		}
                                  	}
                                  	else {
                                  		if (is_grid_done()) {
                                  			puts("Solution");
                                  			print_grid();
                                  			res = 1;
                                  		}
                                  		else {
                                  			puts("Bad grid");
                                  			print_grid();
                                  		}
                                  	}
                                  	return res;
                                  }
                                  
                                  
                                  void fill_grid(const char *sudoku_string)
                                  {
                                  	int line, col;
                                  	for (line = 0; line < 9; ++line) {
                                  		for (col = 0; col < 9; ++col) {
                                  			while (!strchr(".0123456789", *sudoku_string)) {
                                  				++sudoku_string;
                                  			}
                                  			grid[line][col] = *sudoku_string != '0' ? *sudoku_string : '.';
                                  			++sudoku_string;
                                  		}
                                  	}
                                  }
                                  
                                  
                                  void usage(char **argv, const char *msg)
                                  {
                                  	fprintf(stderr, "%s: %s\n", argv[0], msg);
                                  	exit(EXIT_FAILURE);
                                  }
                                  
                                  
                                  void check_sudoku_string(char **argv)
                                  {
                                  	int i;
                                  	const char *arg = argv[1];
                                  
                                  	for (i = 0; i < 9 * 9; ++i) {
                                  		while (isspace(*arg) || (*arg != '.' && ispunct(*arg))) {
                                  			++arg;
                                  		}
                                  
                                  		if (*arg == '\0') {
                                  			usage(argv, "sudoku string too short");
                                  		}
                                  		if (*arg != '.' && !isdigit(*arg)) {
                                  			static const char msg[] = "bad character '%c' in sudoku string";
                                  			char s[sizeof msg];
                                  			sprintf(s, msg, *arg);
                                  			usage(argv, s);
                                  		}
                                  
                                  		++arg;
                                  	}
                                  
                                  	while (isspace(*arg) || (*arg != '.' && ispunct(*arg))) {
                                  		++arg;
                                  	}
                                  
                                  	if (*arg != '\0') {
                                  		usage(argv, "sudoku string too long");
                                  	}
                                  }
                                  
                                  
                                  void check_args(int argc, char **argv)
                                  {
                                  	if (argc < 2) {
                                  		usage(argv, "missing sudoku string parameter");
                                  	}
                                  	else if (argc > 2) {
                                  		usage(argv, "too many parameters");
                                  	}
                                  	else {
                                  		check_sudoku_string(argv);
                                  	}
                                  }
                                  
                                  
                                  int main(int argc, char **argv)
                                  {
                                  	int nb_solutions;
                                  	check_args(argc, argv);
                                  	fill_grid(argv[1]);
                                  	print_grid();
                                  	nb_solutions = print_solutions(0, 0);
                                  	printf("This Sudoku has %d solution%s.\n", nb_solutions, "s"+(nb_solutions<2));
                                  	return EXIT_SUCCESS;
                                  }
                                  
                                  • Partager sur Facebook
                                  • Partager sur Twitter
                                    22 septembre 2011 à 23:45:57

                                    Merci de me faire mentir Marc. =)
                                    Le truc c'est qu'encore une fois, c'est un truc pour débutants et je sais que yoch, GurneyH ou encore toi savent le faire. Donc au final, on reste sur 1 participant ! :p
                                    Par contre, un 'vrai' sudoku n'a qu'une seule et unique solution, donc s'il y en a plusieurs c'est que ce n'est pas un 'vrai' sudoku. :)
                                    • Partager sur Facebook
                                    • Partager sur Twitter
                                      23 septembre 2011 à 5:35:13

                                      Bonjour, j'ai essayé defaire un bench des codes présentés pour le moment(hormis pour Marc dont le fonctionnement du code est un peu différent).

                                      #include <stdlib.h>
                                      #include <stdio.h>
                                      #include <stdbool.h>
                                      #include <time.h>
                                      
                                      #define N       (3)
                                      #define N_2     (N*N)
                                      #define start   (1)
                                      
                                      ////////////////////////////////////////////////////////////
                                      //             Fonction d'affichage
                                      ////////////////////////////////////////////////////////////
                                      void affichage (int grille[N_2][N_2])
                                      {
                                          for (int i=0; i<N_2; i++)
                                          {
                                              for (int j=0; j<N_2; j++)
                                              {
                                                  printf( ((j+1)%N) ? "%d " : "%d|", grille[i][j]);
                                              }
                                              putchar('\n');
                                              if (!((i+1)%N))
                                                  puts("------------------");
                                          }
                                          puts("");
                                      }
                                      
                                      /* Shaddan ------------------------------------------------------------------ */
                                      #define SIZE 9
                                      
                                      typedef int Grid[SIZE][SIZE];
                                      
                                      /* verifie si la valeur est valide */
                                      int check_case(Grid grid, int row, int col, int n)
                                      {
                                        int i,j;
                                        int mini_row = row - row % 3;
                                        int mini_col = col - col % 3;
                                        if(grid[row][col] == n)
                                          return 1;
                                        if(grid[row][col] != 0)
                                          return 0;
                                        for(i = 0; i < SIZE; i++)
                                          if(grid[row][i] == n || grid[i][col] == n)
                                            return 0;
                                        for(i = mini_row; i < mini_row + 3; i++)
                                          for(j = mini_col; j < mini_col + 3; j++)
                                            if(grid[i][j] == n)
                                              return 0;
                                        return 1;
                                      }
                                      
                                      void grid_cpy(Grid dest, Grid src)
                                      {
                                        int i,j;
                                        for(i = 0; i < SIZE; i++)
                                          for(j = 0; j < SIZE; j++)
                                            dest[i][j] = src[i][j];
                                      }
                                      
                                      /* resolution par backtracking */
                                      void shaddan_solve(Grid grid, int row, int col, Grid sol)
                                      {
                                        if(row < SIZE)
                                        {
                                          int i;
                                          for(i = 1; i <= SIZE; i++)
                                          {
                                            if(check_case(grid, row, col, i))
                                            {
                                              int tmp = grid[row][col];
                                              grid[row][col] = i;
                                      
                                              if(col != SIZE - 1)
                                                shaddan_solve(grid, row, col + 1, sol);
                                              else
                                                shaddan_solve(grid, row + 1, 0, sol);
                                      
                                              grid[row][col] = tmp; /* on remet l'ancienne valeur */
                                            }
                                          }
                                        }
                                        else
                                          grid_cpy(sol, grid); /* on copie la solution (quand trouvée) avant
                                                                  que l'ancienne valeur ne soit rétablie */
                                      }
                                      
                                      
                                      void shaddan_solve1(Grid grid)
                                      {
                                          shaddan_solve(grid, 0, 0, grid);
                                      }
                                      /* Pouet_forever ------------------------------------------------------------ */
                                      enum {
                                        M = 3,
                                        NNN = M * M,
                                        NxN = NNN * NNN
                                      };
                                      
                                      int isValid(int * grid, int n, int pos) {
                                        int i, j;
                                        int col, lin;
                                      
                                        col = pos % NNN;
                                        lin = pos / NNN;
                                      
                                        /* Line, column */
                                        for (i = 0; i < NNN; i++) {
                                          if (grid[lin * NNN + i] == n ||
                                              grid[i * N + col] == n)
                                            return 0;
                                        }
                                      
                                        /* case */
                                        col = (col / M) * M;
                                        lin = (lin / M) * M;
                                      
                                        for (i = 0; i < M; i++) {
                                          for (j = 0; j < M; j++) {
                                            if (grid[(lin + i) * N + (col + j)] == n)
                                              return 0;
                                          }
                                        }
                                      
                                        return 1;
                                      }
                                      
                                      int resolve(int * grid, int pos) {
                                        int i, tmp;
                                      
                                        if (pos >= NxN)
                                          return 1;
                                        if (grid[pos] != 0)
                                          return resolve(grid, pos + 1);
                                      
                                        for (i = 1; i <= NNN; i++) {
                                          if (isValid(grid, i, pos)) {
                                            grid[pos] = i;
                                      
                                            tmp = resolve(grid, pos + 1);
                                            if (tmp != 0)
                                              return tmp;
                                      
                                            grid[pos] = 0;
                                          }
                                        }
                                      
                                        return 0;
                                      }
                                      
                                      int resolve1(int * grid)
                                      {
                                          resolve(grid, 0);
                                      }
                                      
                                      
                                      
                                      /* GurneyH ------------------------------------------------------------------ */
                                      #define NN       9
                                      
                                      typedef struct
                                      {
                                          int pos;
                                          int n;
                                      } cell;
                                      
                                      
                                      
                                      cell cells[NN * NN];
                                      int possibility[NN * NN][NN + 1];
                                      
                                      
                                      int cmp(void const *p, void const *q)
                                      {
                                          return ((cell *)p)->n - ((cell *)q)->n;
                                      }
                                      
                                      
                                      
                                      void grid_display(int *g)
                                      {
                                          for(int i = 0; i < NN; i++)
                                          {
                                              for(int j = 0; j < NN; j++)
                                                  printf("%d", g[i * NN + j]);
                                              puts("");
                                          }
                                          puts("");
                                      }
                                      
                                      
                                      int check_square(int *g, int row, int col, int v)
                                      {
                                          int ox = (col / 3) * 3;
                                          int oy = (row / 3) * 3;
                                      
                                          for(int i = oy; i < oy + 3; i++)
                                              for(int j = ox; j < ox + 3; j++)
                                                  if(g[i * NN + j] == v)
                                                      return 0;
                                          return 1;
                                      }
                                      
                                      
                                      
                                      int check_row_col(int *g, int row, int col, int v)
                                      {
                                          for(int i = 0; i < NN; i++)
                                              if(g[i * NN + col] == v || g[row * NN + i] == v)
                                                  return 0;
                                          return 1;
                                      }
                                      
                                      
                                      int check_cell(int *g, int pos, int v)
                                      {
                                          int col = pos % NN;
                                          int row = pos / NN;
                                          return check_row_col(g, row, col, v) && check_square(g, row, col, v);
                                      }
                                      
                                      
                                      
                                      int backtrack(int *g, int id)
                                      {
                                          int pos = cells[id].pos;
                                          if(id == NN * NN)
                                              return 1;
                                          if(g[pos])
                                              return backtrack(g, id + 1);
                                          else
                                          {
                                              for(int k = 1; k <= NN; k++)
                                              {
                                                  if(possibility[pos][k])
                                                      if(check_cell(g, pos, k))
                                                      {
                                                          g[pos] = k;
                                                          if(backtrack(g, id + 1))
                                                              return 1;
                                                      }
                                              }
                                              g[pos] = 0;
                                              return 0;
                                          }
                                      }
                                      
                                      
                                      int singleton_block(int *g)
                                      {
                                          int n_singletons = 0;
                                          for(int i = 0; i < NN; i += 3)
                                              for(int j = 0; j < NN; j += 3)
                                              {
                                                  int pos = 0;
                                                  for(int k = 1; k <= NN; k++)
                                                  {
                                                      int count = 0;
                                                      for(int ii = i; ii < i + 3; ii++)
                                                          for(int jj = j; jj < j + 3; jj++)
                                                          {
                                                              if(!g[ii * NN + jj] && check_cell(g, ii * NN + jj, k))
                                                              {
                                                                  count++;
                                                                  pos =  ii * NN + jj;
                                                              }
                                                          }
                                                      if(count == 1)
                                                      {
                                                          g[pos] = k;
                                                          n_singletons++;
                                                      }
                                                  }
                                              }
                                          return n_singletons;
                                      }
                                      
                                      
                                      
                                      int singleton_col(int *g)
                                      {
                                          int n_singletons = 0;
                                          for(int col = 0; col < NN; col++)
                                          {
                                              int pos = 0;
                                              for(int k = 1; k <= NN; k++)
                                              {
                                                  int count = 0;
                                                  for(int row = 0; row < NN; row++)
                                                  {
                                                      if(!g[ row * NN + col])
                                                      {
                                                          if(check_cell(g, row * NN + col, k))
                                                          {
                                                              count++;
                                                              pos =  row * NN + col;
                                                          }
                                                      }
                                                  }
                                                  if(count == 1)
                                                  {
                                                      g[pos] = k;
                                                      n_singletons++;
                                                  }
                                              }
                                          }
                                          return n_singletons;
                                      }
                                      
                                      
                                      int singleton_row(int *g)
                                      {
                                          int n_singletons = 0;
                                          for(int row = 0; row < NN; row++)
                                          {
                                              int pos = 0;
                                              for(int k = 1; k <= NN; k++)
                                              {
                                                  int count = 0;
                                                  for(int col = 0; col < NN; col++)
                                                  {
                                                      if(!g[ row * NN + col])
                                                      {
                                                          if(check_cell(g, row * NN + col, k))
                                                          {
                                                              count++;
                                                              pos =  row * NN + col;
                                                          }
                                                      }
                                                  }
                                                  if(count == 1)
                                                  {
                                                      g[pos] = k;
                                                      n_singletons++;
                                                  }
                                              }
                                          }
                                          return n_singletons;
                                      }
                                      
                                      
                                      void solve(int *g)
                                      {
                                          int find = 0;
                                          do
                                          {
                                              find = singleton_row(g) + singleton_col(g) + singleton_block(g);
                                              for(int i = 0; i < NN * NN; i++)
                                              {
                                                  int n = 0;
                                                  int last = 0;
                                                  if(!g[i])
                                                  {
                                                      for(int k = 1; k <= NN; k++)
                                                          if(check_cell(g, i, k))
                                                          {
                                                              possibility[i][k] = 1;
                                                              last = k;
                                                              n++;
                                                          }
                                                      if(n == 1)
                                                      {
                                                          g[i] = last;
                                                          find = 1;
                                                      }
                                                  }
                                                  cells[i].pos = i;
                                                  cells[i].n = n;
                                              }
                                          }
                                          while(find);
                                      
                                          qsort(cells, NN * NN, sizeof *cells, cmp);
                                          backtrack(g, 0);
                                      }
                                      
                                      /* Yoch --------------------------------------------------------------------- */
                                      
                                      ////////////////////////////////////////////////////////////
                                      //   Listes circulaires : définition et fonctions
                                      ////////////////////////////////////////////////////////////
                                      
                                      typedef struct _node
                                      {
                                          struct _node* prev;
                                          struct _node* next;
                                          int i, j, b;
                                          int nbValeursPossibles;
                                      } CIRCL_LIST;
                                      
                                      CIRCL_LIST* createRoot (void)
                                      {
                                          CIRCL_LIST* node = malloc(sizeof *node);
                                          node->prev = node->next = node;
                                          return node;
                                      }
                                      
                                      CIRCL_LIST* circular_list_append (CIRCL_LIST* root)
                                      {
                                          CIRCL_LIST* node = malloc(sizeof *node);
                                          node->prev = root->prev;
                                          node->next = root;
                                          root->prev->next = node;
                                          root->prev = node;
                                          return node;
                                      }
                                      
                                      void deleteAll (CIRCL_LIST* root)
                                      {
                                          CIRCL_LIST *next;
                                          for (CIRCL_LIST* iter = root->next; iter != root; iter = next)
                                          {
                                              next = iter->next;
                                              free (iter);
                                          }
                                          free (root);
                                      }
                                      
                                      ////////////////////////////////////////////////////////////
                                      //                  Resolution Sudoku
                                      ////////////////////////////////////////////////////////////
                                      
                                      // Variables globales pour la mémorisation
                                      bool existeSurLigne[N_2][N_2];
                                      bool existeSurColonne[N_2][N_2];
                                      bool existeSurBloc[N_2][N_2];
                                      
                                      
                                      ////////////////////////////////////////////////////////////
                                      //             Backtracking "adaptatif" :
                                      //  décide dynamiquement la branche de l'arbre à explorer
                                      ////////////////////////////////////////////////////////////
                                      bool estValide (int grille[N_2][N_2], CIRCL_LIST* root)
                                      {
                                          bool ret = false;
                                          if (root == root->next)  // la liste est vide
                                              return true;
                                      
                                          // cherche la case avec un nombre de valeurs possibles minimal
                                          int min = N_2+1;
                                          CIRCL_LIST* pos = NULL;
                                          for (CIRCL_LIST* iter = root->next; iter != root && min != 0; iter = iter->next)
                                          {
                                              if (iter->nbValeursPossibles < min)
                                                  pos = iter, min = iter->nbValeursPossibles;
                                          }
                                      
                                          if (min == 0) return false;  // si le nombre de valeurs possibles vaut 0, on stoppe
                                      
                                          int i = pos->i, j = pos->j, b = pos->b;
                                      
                                          // supprimme temporairement le noeud de la liste
                                          pos->prev->next = pos->next;
                                          pos->next->prev = pos->prev;
                                      
                                          // Crée une liste de voisins de la case sélectionnée (même ligne/colonne/bloc)
                                          CIRCL_LIST* voisins[2*(N_2-1)+(N-1)*(N-1)];
                                          unsigned n = 0;
                                          for (CIRCL_LIST* iter = root->next; iter != root; iter = iter->next)
                                              if ( iter->i == i || iter->j == j || iter->b == b )
                                                  voisins[n++] = iter;
                                      
                                          unsigned nb = 0;
                                          for (int k=0; k < N_2 && nb != min; k++)
                                          {
                                              // si on peut placer k+start
                                              if ( !existeSurLigne[i][k] && !existeSurColonne[j][k] && !existeSurBloc[b][k] )
                                              {
                                                  // on actualise le champ 'nbValeursPossibles' dans la liste
                                                  for (CIRCL_LIST** it = voisins; it != voisins+n; it++)
                                                      if ( !existeSurLigne[(*it)->i][k] && !existeSurColonne[(*it)->j][k] && !existeSurBloc[(*it)->b][k] )
                                                          (*it)->nbValeursPossibles--;
                                      
                                                  // Ajoute k aux valeurs enregistrées
                                                  existeSurLigne[i][k] = existeSurColonne[j][k] = existeSurBloc[b][k] = true;
                                      
                                                  if ( (ret = estValide(grille, root)) )
                                                  {
                                                      grille[i][j] = k+start;
                                                      break;
                                                  }
                                      
                                                  // Supprime k des valeurs enregistrées
                                                  existeSurLigne[i][k] = existeSurColonne[j][k] = existeSurBloc[b][k] = false;
                                      
                                                  // on re-actualise le champ 'nbValeursPossibles' dans la liste
                                                  for (CIRCL_LIST** it = voisins; it != voisins+n; it++)
                                                      if ( !existeSurLigne[(*it)->i][k] && !existeSurColonne[(*it)->j][k] && !existeSurBloc[(*it)->b][k] )
                                                          (*it)->nbValeursPossibles++;
                                                  nb++;
                                              }
                                          }
                                      
                                          // avant de quitter, on restaure le noeud dans la liste
                                          pos->prev->next = pos;
                                          pos->next->prev = pos;
                                      
                                          return ret;
                                      }
                                      
                                      // compte (naïvement) le nombre de solutions possibles pour une case
                                      int nb_possibles (int i, int j, int b)
                                      {
                                          int ret = 0;
                                          for (int k=0; k < N_2; k++)
                                              if ( !existeSurLigne[i][k] && !existeSurColonne[j][k] && !existeSurBloc[b][k] )
                                                  ret++;
                                          return ret;
                                      }
                                      
                                      bool resolution (int grille[N_2][N_2])
                                      {
                                          // Initialise les tableaux
                                          for (int i=0; i < N_2; i++)
                                              for (int j=0; j < N_2; j++)
                                                  existeSurLigne[i][j] = existeSurColonne[i][j] = existeSurBloc[i][j] = false;
                                      
                                          // Enregistre toutes les valeurs déjà présentes dans la grille
                                          int k;
                                          for (int i=0; i < N_2; i++)
                                              for (int j=0; j < N_2; j++)
                                                  if ( (k = grille[i][j]) != 0)
                                                      existeSurLigne[i][k-start] = existeSurColonne[j][k-start] = existeSurBloc[N*(i/N)+(j/N)][k-start] = true;
                                      
                                          // Crée une liste circulaire doublement chainée contenant toutes les cases vides
                                          CIRCL_LIST *positions = createRoot(), *node = NULL;
                                          for (int i=0; i < N_2; i++)
                                              for (int j=0; j < N_2; j++)
                                                  if ( grille[i][j] == 0 )
                                                  {
                                                      node = circular_list_append ( positions );
                                                      node->i = i, node->j = j, node->b = N*(i/N)+(j/N);
                                                      node->nbValeursPossibles = nb_possibles(i, j, node->b);
                                                  }
                                      
                                      
                                          // Appelle la fonction récursive estValide()
                                          bool ret = estValide (grille, positions);
                                      
                                          deleteAll (positions);
                                      
                                          return ret;
                                      }
                                      
                                      
                                      
                                      void bench(char const *s, int (*f)(int [N_2][N_2]))
                                      {
                                          int grille[3][N_2][N_2] =
                                          {
                                              {
                                                  {0,0,0,0,0,0,0,0,0},
                                                  {0,0,0,0,0,3,0,8,5},
                                                  {0,0,1,0,2,0,0,0,0},
                                                  {0,0,0,5,0,7,0,0,0},
                                                  {0,0,4,0,0,0,1,0,0},
                                                  {0,9,0,0,0,0,0,0,0},
                                                  {5,0,0,0,0,0,0,7,3},
                                                  {0,0,2,0,1,0,0,0,0},
                                                  {0,0,0,0,4,0,0,0,9},
                                              },
                                      
                                              {
                                                  {9,0,0,1,0,0,0,0,5},
                                                  {0,0,5,0,9,0,2,0,1},
                                                  {8,0,0,0,4,0,0,0,0},
                                                  {0,0,0,0,8,0,0,0,0},
                                                  {0,0,0,7,0,0,0,0,0},
                                                  {0,0,0,0,2,6,0,0,9},
                                                  {2,0,0,3,0,0,0,0,6},
                                                  {0,0,0,2,0,0,9,0,0},
                                                  {0,0,1,9,0,4,5,7,0}
                                              },
                                      
                                              {
                                                  {0,0,0,0,0,0,0,3,1},
                                                  {6,0,0,0,2,0,0,0,0},
                                                  {0,0,0,0,7,0,0,0,0},
                                                  {0,5,0,1,0,8,0,0,0},
                                                  {2,0,0,0,0,0,6,0,0},
                                                  {0,0,0,3,0,0,0,7,0},
                                                  {0,0,0,0,4,0,2,0,0},
                                                  {0,3,0,5,0,0,0,0,0},
                                                  {7,0,0,0,0,0,0,0,0},
                                              }
                                          };
                                          printf("%s\n", s);
                                          for(int i = 0; i < 3; i++)
                                          {
                                              //affichage(grille[i]);
                                              clock_t t1 = clock();
                                              f(grille[i]);
                                              clock_t t2 = clock();
                                              //affichage(grille[i]);
                                              printf("Grille %d : %.3fs\n\n", i, (double)(t2-t1)/CLOCKS_PER_SEC);
                                          }
                                      }
                                      int main (void)
                                      {
                                          bench("Yoch", resolution);
                                          bench("GurneyH", solve);
                                          bench("Pouet", resolve1);
                                          bench("shaddan", shaddan_solve1);
                                          return 0;
                                      }
                                      


                                      J'obtiens bien sur des warnings:
                                      - Pouet et moi utilisons des tableaux 1d.
                                      - Yoch utilise le type bool
                                      - la fonction solve de shaddan ne retourne rien.

                                      Il faudrait qu'on se fixe une interface commune, pour faire un bench sérieux.

                                      Résultats avec les 3 grilles du code de Yoch(sauf erreur...)


                                      Yoch
                                      Grille 0 : 0.031s
                                      
                                      Grille 1 : 0.000s
                                      
                                      Grille 2 : 0.000s
                                      
                                      GurneyH
                                      Grille 0 : 0.016s
                                      
                                      Grille 1 : 0.000s
                                      
                                      Grille 2 : 0.000s
                                      
                                      Pouet
                                      Grille 0 : 0.078s
                                      
                                      Grille 1 : 0.000s
                                      
                                      Grille 2 : 0.000s
                                      
                                      shaddan
                                      Grille 0 : 40.797s
                                      
                                      Grille 1 : 1.437s
                                      
                                      Grille 2 : 0.500s
                                      
                                      
                                      Process returned 0 (0x0)   execution time : 42.906 s
                                      Press any key to continue.


                                      edit:
                                      Je viens de tester cette grille
                                      1 2 . | 4 . . | 3 . .  
                                      3 . . | . 1 . | . 5 .  
                                      . . 6 | . . . | 1 . .  
                                      ------+-------+------ 
                                      7 . . | . 9 . | . . .  
                                      . 4 . | 6 . 3 | . . .  
                                      . . 3 | . . 2 | . . .  
                                      ------+-------+------  
                                      5 . . | . 8 . | 7 . .  
                                      . . 7 | . . . | . . 5  
                                      . . . | . . . | . 9 8

                                      Elle met mon code par terre(9s), et passe pas mal si j'enlève le qsort(0.1s) -> Il faut bien réévaluer dynamiquement.
                                      Elle passe bien aussi avec vos codes.
                                      • Partager sur Facebook
                                      • Partager sur Twitter
                                      Zeste de Savoir, le site qui en a dans le citron !
                                        23 septembre 2011 à 6:59:07

                                        Salut,

                                        Merci pour le bench. :)

                                        Il y a un truc que je ne comprends pas du tout : le code de Pouet Forever (si c'est bien celui-ci) n'est pas du tout optimisé, et il donne les meilleures perfs ! Il doit y avoir un truc qui cloche quelque part... :-°

                                        J'ai refait un bench pour la grille 0 ("Near worst case" - tiré de Wikipédia) avec le code de Pouet Forever, et voici le résultat :
                                        #include <stdlib.h>
                                        #include <stdio.h>
                                        
                                        enum {
                                          M = 3,
                                          N = M * M,
                                          NxN = N * N
                                        };
                                        
                                        void printGrid(int * grid) {
                                          int i;
                                        
                                          for (i = 0; i < NxN; i++) {
                                            if (i != 0) {
                                              if (i % N == 0)
                                                putchar('\n');
                                              else if (i % M == 0)
                                                putchar(' ');
                                              if (i % (N * M) == 0)
                                                putchar('\n');
                                            }
                                        
                                            printf("%d ", grid[i]);
                                          }
                                          puts("");
                                          puts("-----------");
                                        }
                                        
                                        int isValid(int * grid, int n, int pos) {
                                          int i, j;
                                          int col, lin;
                                        
                                          col = pos % N;
                                          lin = pos / N;
                                        
                                          /* Line, column */
                                          for (i = 0; i < N; i++) {
                                            if (grid[lin * N + i] == n ||
                                                grid[i * N + col] == n)
                                              return 0;
                                          }
                                        
                                          /* case */
                                          col = (col / M) * M;
                                          lin = (lin / M) * M;
                                        
                                          for (i = 0; i < M; i++) {
                                            for (j = 0; j < M; j++) {
                                              if (grid[(lin + i) * N + (col + j)] == n)
                                                return 0;
                                            }
                                          }
                                        
                                          return 1;
                                        }
                                        
                                        int resolve(int * grid, int pos) {
                                          int i, tmp;
                                        
                                          if (pos >= NxN)
                                            return 1;
                                          if (grid[pos] != 0)
                                            return resolve(grid, pos + 1);
                                        
                                          for (i = 1; i <= N; i++) {
                                            if (isValid(grid, i, pos)) {
                                              grid[pos] = i;
                                        
                                              tmp = resolve(grid, pos + 1);
                                              if (tmp != 0)
                                                return tmp;
                                        
                                              grid[pos] = 0;
                                            }
                                          }
                                        
                                          return 0;
                                        }
                                        
                                        
                                        int main (void) {
                                          int grid[NxN] = {0,0,0,0,0,0,0,0,0,
                                                           0,0,0,0,0,3,0,8,5,
                                                           0,0,1,0,2,0,0,0,0,
                                                           0,0,0,5,0,7,0,0,0,
                                                           0,0,4,0,0,0,1,0,0,
                                                           0,9,0,0,0,0,0,0,0,
                                                           5,0,0,0,0,0,0,7,3,
                                                           0,0,2,0,1,0,0,0,0,
                                                           0,0,0,0,4,0,0,0,9};
                                        
                                          printGrid(grid);
                                          resolve(grid, 0);
                                          printGrid(grid);
                                        
                                          return EXIT_SUCCESS;
                                        }
                                        


                                        0 0 0  0 0 0  0 0 0
                                        0 0 0  0 0 3  0 8 5
                                        0 0 1  0 2 0  0 0 0
                                        
                                        0 0 0  5 0 7  0 0 0
                                        0 0 4  0 0 0  1 0 0
                                        0 9 0  0 0 0  0 0 0
                                        
                                        5 0 0  0 0 0  0 7 3
                                        0 0 2  0 1 0  0 0 0
                                        0 0 0  0 4 0  0 0 9
                                        -----------
                                        9 8 7  6 5 4  3 2 1
                                        2 4 6  1 7 3  9 8 5
                                        3 5 1  9 2 8  7 4 6
                                        
                                        1 2 8  5 3 7  6 9 4
                                        6 3 4  8 9 2  1 5 7
                                        7 9 5  4 6 1  8 3 2
                                        
                                        5 1 9  2 8 6  4 7 3
                                        4 7 2  3 1 9  5 6 8
                                        8 6 3  7 4 5  2 1 9
                                        -----------
                                        
                                        Process returned 0 (0x0)   execution time : 24.806 s
                                        Press any key to continue.


                                        Je crois donc que tu as modifié l'ordre de la grille, ou quelque chose comme ça...

                                        Sinon, voici une autre grille de test qui peut poser des problèmes à certains codes (celui avec tri préalable des cases, si ma mémoire est bonne) :
                                        int grille[N_2][N_2] =
                                            {
                                                {0,0,0,0,0,0,0,1,2},
                                                {0,0,0,0,0,0,0,0,3},
                                                {0,0,2,3,0,0,4,0,0},
                                                {0,0,1,8,0,0,0,0,5},
                                                {0,6,0,0,7,0,8,0,0},
                                                {0,0,0,0,0,9,0,0,0},
                                                {0,0,8,5,0,0,0,0,0},
                                                {9,0,0,0,4,0,5,0,0},
                                                {4,7,0,0,0,6,0,0,0}
                                            };
                                        


                                        Sinon, +1 pour le voeu d'avoir une interface commune. Je crois que ce n'est pas imposé pour donner une plus grande liberté de codage, mais c'est vrai que ça devient difficile de faire des benchs...

                                        EDIT :
                                        Aussi, pour bien se rendre compte que le problème du sudoku est NP-Complet, et vu que beaucoup de codes postés ici sont assez génériques, je suggère aux membres d'essayer de passer à la dimension supérieure (16x16), histoire de s'en convaincre... :p
                                        Attention tout de même, ça fait 256 cases au total contre 81, et je pense que ça va prendre plusieurs heures de calcul en moyenne, voire pire dans certains cas. :-° Il est possible d'utiliser des grilles relativement pleines, pour éviter de tomber dans ce genre d’excès.
                                        • Partager sur Facebook
                                        • Partager sur Twitter
                                          23 septembre 2011 à 10:01:05

                                          C'est quoi ce benchmark qui consiste à tester la fonction qu'une seule fois?
                                          yoch: 0.000
                                          GurneyH: 0.000
                                          Ah bah oui c'est très parlant là :D
                                          • Partager sur Facebook
                                          • Partager sur Twitter
                                            23 septembre 2011 à 11:06:00

                                            Citation : GurneyH

                                            Bonjour, j'ai essayé defaire un bench des codes présentés pour le moment(hormis pour Marc dont le fonctionnement du code est un peu différent).


                                            Ah? Pourtant c'est un backtracking de base.
                                            • Partager sur Facebook
                                            • Partager sur Twitter
                                              23 septembre 2011 à 11:56:51

                                              Citation : Mr21

                                              C'est quoi ce benchmark qui consiste à tester la fonction qu'une seule fois?
                                              yoch: 0.000
                                              GurneyH: 0.000
                                              Ah bah oui c'est très parlant là :D



                                              Tu as raison. ;)
                                              Mais c'était surtout pour voir les cas pouvant prendre plusieurs secondes, et j'ai pondu ça rapidement, même pas certain que ce soit correct(voir la remarque de Yoch sur les perfs du code de Pouet).


                                              Citation : Marc Mongenet

                                              Citation : GurneyH

                                              Bonjour, j'ai essayé defaire un bench des codes présentés pour le moment(hormis pour Marc dont le fonctionnement du code est un peu différent).


                                              Ah? Pourtant c'est un backtracking de base.



                                              J'ai dû mal comprendre ton code sur l'instant, tu ne t'arrêtes pas à la première grille trouvée, non?

                                              edit:

                                              Alors le bench est un peu biaisé totalement faux.
                                              le code de Pouet ressort avec la grille d'origine, et le mien avec des grilles incomplètes... :(
                                              Je regarde le problême.
                                              • Partager sur Facebook
                                              • Partager sur Twitter
                                              Zeste de Savoir, le site qui en a dans le citron !
                                                23 septembre 2011 à 12:20:53

                                                Citation : Mr21

                                                C'est quoi ce benchmark qui consiste à tester la fonction qu'une seule fois?
                                                yoch: 0.000
                                                GurneyH: 0.000
                                                Ah bah oui c'est très parlant là :D


                                                L'ennui, c'est que pour faire un benchmark correct, il faudrait des tas de grilles (je dirais de l'ordre de quelques milliers), donc impensable de le faire a la main...

                                                Ce qui serait possible, c'est d'utiliser un générateur automatique de sudokus (j'en ai un si vous voulez, mais pour que ce soit équitable il faudrait employer un logiciel tiers, reconnu et éprouvé), mais ca va demander un petit effort d'adaptation...
                                                • Partager sur Facebook
                                                • Partager sur Twitter
                                                  23 septembre 2011 à 12:41:18

                                                  yeap, d'ailleurs le sujet qu'on a eu à l'école nous demandait un binaire qui lit un fichier de ce type:

                                                  |------------------|
                                                  |                  |
                                                  |           3   8 5|
                                                  |     1   2        |
                                                  |       5   7      |
                                                  |     4       1    |
                                                  |   9              |
                                                  | 5             7 3|
                                                  |     2   1        |
                                                  |         4       9|
                                                  |------------------|
                                                  |------------------|
                                                  | 9     1         5|
                                                  |     5   9   2   1|
                                                  | 8       4        |
                                                  |         8        |
                                                  |       7          |
                                                  |         2 6     9|
                                                  | 2     3         6|
                                                  |       2     9    |
                                                  |     1 9   4 5 7  |
                                                  |------------------|
                                                  |------------------|
                                                  |               3 1|
                                                  | 6       2        |
                                                  |         7        |
                                                  |   5   1   8      |
                                                  | 2           6    |
                                                  |       3       7  |
                                                  |         4   2    |
                                                  |   3   5          |
                                                  | 7                |
                                                  |------------------|
                                                  Le programme devait afficher la même chose en résolu.
                                                  Ce qui fait que c'était prévu pour tester pleins de maps ^^
                                                  • Partager sur Facebook
                                                  • Partager sur Twitter
                                                    23 septembre 2011 à 12:44:03

                                                    Citation : GurneyH

                                                    J'ai dû mal comprendre ton code sur l'instant, tu ne t'arrêtes pas à la première grille trouvée, non?


                                                    Ah oui, effectivement, je ne m'arrête pas. Du coup ça me rend plus lent. Désolé du dérangement.
                                                    • Partager sur Facebook
                                                    • Partager sur Twitter
                                                      23 septembre 2011 à 13:05:19

                                                      Ce genre de liste me parait convenir pour un bench un peu plus sérieux (1465 grilles qui sont donnés comme humainement très difficiles).

                                                      Pour les plus exigeants, je propose cette liste de 49151 ( :-° ) sudokus minimaux (17 cases dévoilées), au format légèrement différent.

                                                      EDIT :
                                                      J'ai adapté mon main pour la seconde liste de sudokus et j'ai effectué un benchmark. Comme c'est un peu long, je termine le test après les 2000 premières grilles. Voici mes résultats :

                                                      ....................2000 grilles en 46.349s


                                                      Ce qui donne en moyenne 0.023s par grille.
                                                      Avec la première liste, j'obtiens encore mieux (normal, ce sont des sudokus difficiles pour humains, mais représentant un arbre de recherche plus petit pour un backtracking) :
                                                      ..............1466 grilles en 5.198s


                                                      Soit en moyenne 0.0035s par grille ! :)


                                                      Voici le main, pour les intéressés :
                                                      #define SZBUF   100
                                                      int main (void)
                                                      {
                                                          FILE* fp = fopen("shorters_sudokus.txt", "r");
                                                          if (fp == NULL)
                                                          {
                                                              fprintf(stderr, "Impossible d'ouvrir le fichier");
                                                              exit(0);
                                                          }
                                                      
                                                          int grille[N_2][N_2] = {{0}};
                                                      
                                                          char buffer[SZBUF] = {0};
                                                          size_t elapsed = 0, counter = 0;
                                                          while ( counter < 2000 /*!feof(fp) */ )
                                                          {
                                                              // charge une grille
                                                              fgets(buffer, SZBUF, fp);
                                                              for (int i=0; i<N_2; i++)
                                                              {
                                                                  for (int j=0; j<N_2; j++)
                                                                  {
                                                                      grille[i][j] = buffer[i*N_2+j] - '0';
                                                                  }
                                                              }
                                                      
                                                              //affichage(grille);
                                                      
                                                              clock_t t1 = clock();
                                                              resolution (grille);
                                                              clock_t t2 = clock();
                                                      
                                                              elapsed += (t2-t1);
                                                              counter++;
                                                      
                                                              if (counter % 100 == 0) putchar('.');
                                                      
                                                              //affichage(grille);
                                                          }
                                                      
                                                          printf("%u grilles en %gs\n\n", counter, (double)elapsed/CLOCKS_PER_SEC);
                                                      
                                                          fclose(fp);
                                                      
                                                          return 0;
                                                      }
                                                      


                                                      EDIT 2 :
                                                      Je viens de retrouver la grille invalide soumise par Pouet Forever. L'auteur signale bien que c'est une grille invalide que son programme a généré (et qui lui a bouffé 1439 secondes avec un code python :lol: ).
                                                      • Partager sur Facebook
                                                      • Partager sur Twitter
                                                        23 septembre 2011 à 21:23:54

                                                        Salut,

                                                        Je viens de faire un petit programme qui marche normalement (en tout case je ne l'ai essaier que sur une seul grille).

                                                        Pour le niveau je pense que c'est 1, car j’évolue la valeur de chaque case de la grille et je regarder dans la collone, ligne et region s'il ya'a qu'une seul solution je retourne dans la premier case sinon je continue .

                                                        Le code :

                                                        #include <stdio.h>
                                                        #include <stdlib.h>
                                                        
                                                        int chercheDansLigne(char grille[][9], int ligne, int nbr);
                                                        int chercheDansCollone(char grille[][9], int collone, int nbr);
                                                        int chercheDansRegion(char grille[][9], int X, int Y, int nbr);
                                                        
                                                        int main()
                                                        {
                                                            char grille[9][9];
                                                            int i, j, k, entre, nbrT = 0, nbr = 0;
                                                            for(i = 0; i < 9; i++)
                                                            scanf("%1c%1c%1c%1c%1c%1c%1c%1c%1c%1c", &grille[i][0], &grille[i][1], &grille[i][2], &grille[i][3], &grille[i][4],
                                                                                        &grille[i][5], &grille[i][6], &grille[i][7], &grille[i][8], &entre);
                                                        
                                                            for(i = 0; i < 9; i++)
                                                                for(j = 0; j < 9; j++)
                                                                    grille[i][j] -= grille[i][j] == ' ' ? 32 : '0';
                                                        
                                                            for(i = 0; i < 9; i++)
                                                            {
                                                                for(j = 0; j < 9; j++)
                                                                {
                                                                    nbrT = 0, nbr = 0;
                                                                    if(grille[i][j] == 0)
                                                                    {
                                                                        for(k = 0; k < 10; k++)
                                                                        {
                                                                            if(!chercheDansLigne(grille, i, k) && !chercheDansCollone(grille, j, k) && !chercheDansRegion(grille, i, j , k))
                                                                            {
                                                                                nbrT++;
                                                                                nbr = k;
                                                                            }
                                                                        }
                                                                        if(nbrT == 1)
                                                                        {
                                                                            grille[i][j] = nbr;
                                                                            i = 0;
                                                                            j = 0;
                                                                        }
                                                                    }
                                                                }
                                                            }
                                                        
                                                            for(i = 0; i < 9; i++){
                                                                for(j = 0; j < 9; j++)
                                                                    printf("%d ",grille[i][j]);
                                                                    printf("\n");}
                                                        
                                                            return 0;
                                                        }
                                                        
                                                        int chercheDansLigne(char grille[][9], int ligne, int nbr)
                                                        {
                                                            int i;
                                                            for(i = 0; i < 9; i++)
                                                                if(grille[ligne][i] == nbr)
                                                                    return 1;
                                                        
                                                            return 0;
                                                        }
                                                        
                                                        int chercheDansCollone(char grille[][9], int collone, int nbr)
                                                        {
                                                            int i;
                                                            for(i = 0; i < 9; i++)
                                                                if(grille[i][collone] == nbr)
                                                                    return 1;
                                                        
                                                            return 0;
                                                        }
                                                        
                                                        int chercheDansRegion(char grille[][9], int X, int Y, int nbr)
                                                        {
                                                            int i, j;
                                                            for(i = ((int)floor(X / 3) * 3); i < ((int)floor(X / 3) * 3) + 3; i++)
                                                                for(j = ((int)floor(Y / 3) * 3); j < ((int)floor(Y / 3) * 3) + 3; j++)
                                                                    if(grille[i][j] == nbr)
                                                                        return 1;
                                                        
                                                            return 0;
                                                        }
                                                        



                                                        Sinon, j'aimerai avoir quellque commentaire pour l'améliorer.
                                                        • Partager sur Facebook
                                                        • Partager sur Twitter
                                                          23 septembre 2011 à 21:51:02

                                                          Ah, ouais, c'est sur ce site que je l'avais chopée. :)
                                                          J'ai dû manger le mot 'impossible'. :-°

                                                          Voilà le résultat de mon bench sur les 1465 grilles :

                                                          1465 grids solved in 565.23s
                                                          average : 0.56s


                                                          #include <ctype.h>
                                                          #include <stdlib.h>
                                                          #include <stdio.h>
                                                          #include <time.h>
                                                          
                                                          enum {
                                                            M = 3,
                                                            N = M * M,
                                                            NxN = N * N
                                                          };
                                                          
                                                          void printGrid(int * grid) {
                                                            int i;
                                                            
                                                            for (i = 0; i < NxN; i++) {
                                                              if (i != 0) {
                                                                if (i % N == 0)
                                                                  putchar('\n');
                                                                else if (i % M == 0)
                                                                  putchar(' ');
                                                                if (i % (N * M) == 0)
                                                                  putchar('\n');
                                                              }
                                                              
                                                              printf("%d ", grid[i]);
                                                            }
                                                            puts("");
                                                            puts("-----------");
                                                          }
                                                          
                                                          int isValid(int * grid, int n, int pos) {
                                                            int i, j;
                                                            int col, lin;
                                                            
                                                            col = pos % N;
                                                            lin = pos / N;
                                                            
                                                            /* Line, column */
                                                            for (i = 0; i < N; i++) {
                                                              if (grid[lin * N + i] == n ||
                                                                  grid[i * N + col] == n)
                                                                return 0;
                                                            }
                                                            
                                                            /* case */
                                                            col = (col / M) * M;
                                                            lin = (lin / M) * M;
                                                            
                                                            for (i = 0; i < M; i++) {
                                                              for (j = 0; j < M; j++) {
                                                                if (grid[(lin + i) * N + (col + j)] == n)
                                                                  return 0;
                                                              }
                                                            }
                                                            
                                                            return 1;
                                                          }
                                                          
                                                          int resolve(int * grid, int pos) {
                                                            int i, tmp;
                                                            
                                                            if (pos >= NxN)
                                                              return 1;
                                                            if (grid[pos] != 0)
                                                              return resolve(grid, pos + 1);
                                                            
                                                            for (i = 1; i <= N; i++) {
                                                              if (isValid(grid, i, pos)) {
                                                                grid[pos] = i;
                                                                
                                                                tmp = resolve(grid, pos + 1);
                                                                if (tmp != 0)
                                                                  return tmp;
                                                                
                                                                grid[pos] = 0;
                                                              }
                                                            }
                                                            
                                                            return 0;
                                                          }
                                                          
                                                          int main (void) {
                                                            FILE * f;
                                                            int grid[NxN] = { 0 };
                                                            size_t t1, t2, tmp, elapsed, average;
                                                            int i, cnt;
                                                            
                                                            f = fopen("sudoku1.txt", "r");
                                                            if (f == NULL) {
                                                              perror("fopen");
                                                              return EXIT_FAILURE;
                                                            }
                                                            
                                                            cnt = 0;
                                                            elapsed = average = 0;
                                                            while (!feof(f)) {
                                                              for (i = 0; i < NxN; i++) {
                                                                int c = fgetc(f);
                                                                
                                                                if (c == '\n') {
                                                                  i--;
                                                                  continue;
                                                                }
                                                                else if (c == EOF)
                                                                  goto end;
                                                                if (c == '.')
                                                                  grid[i] = 0;
                                                                else if (isdigit(c))
                                                                  grid[i] = c - '0';
                                                              }
                                                              
                                                              t1 = clock();
                                                              resolve(grid, 0);
                                                              t2 = clock();
                                                              
                                                              tmp = t2 - t1;
                                                              average = (average + tmp) / 2;
                                                              elapsed += tmp;
                                                              cnt++;
                                                            }
                                                            
                                                          end:
                                                            printf("%d grids solved in %.2fs\n", cnt, (double) elapsed / CLOCKS_PER_SEC);
                                                            printf("average : %.2fs\n", (double) average / CLOCKS_PER_SEC);
                                                            fclose(f);
                                                            return EXIT_SUCCESS;
                                                          }
                                                          


                                                          Ton code a résolu 1466 grilles, où est la dernière ? :lol:
                                                          • Partager sur Facebook
                                                          • Partager sur Twitter
                                                          Anonyme
                                                            23 septembre 2011 à 22:03:16

                                                            Vous me donnez envie de faire l'exo là les gars. :)

                                                            J'essayerai demain.
                                                            • Partager sur Facebook
                                                            • Partager sur Twitter

                                                            [FAIT][Défis] #3 : Des sudokus en folie !

                                                            × Après avoir cliqué sur "Répondre" vous serez invité à vous connecter pour que votre message soit publié.
                                                            × Attention, ce sujet est très ancien. Le déterrer n'est pas forcément approprié. Nous te conseillons de créer un nouveau sujet pour poser ta question.
                                                            • Editeur
                                                            • Markdown