Partage
  • Partager sur Facebook
  • Partager sur Twitter

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

Venez vous entraîner !

    16 septembre 2011 à 18:40:10

    Bonjour à tous les zéros,

    Cette semaine, nous vous proposons un nouveau défi à réaliser un C, un solveur du célèbre jeu du sudoku !

    Si vous souhaitez plus de renseignements sur les défis, rendez vous sur le topic de recensement des défis, vous y trouverez également les règles principales.

    Cet exercice a été écrit par GuilOooo, un grand merci à lui !

    Des sudokus en folie !



    Salut,

    Aujourd'hui, nous voyons un exercice archi-classique.

    Mise en situation



    Il n'est plus besoin de présenter le célèbre jeu de Sudoku.
    Nous allons créer un programme en console capable de résoudre des grilles de Sudoku, en utilisant des méthodes de plus en plus évoluées.

    Énoncé



    Votre programme lira, sur l'entrée standard, une grille incomplète de Sudoku 9×9, avec 9 cases par ligne. Les chiffres sont écrits tels quels, et les cases blanches sont représentées par des espaces.

    Exemple :
    1 3456789
    789 23456
    456789 23
    3456789 2
    9 2345678
    6789 2345
    56789 234
    23456789 
    89 234567


    Vous devez alors afficher le même sudoku, complété (si la solution existe).

    Exemple :
    123456789
    789123456
    456789123
    345678912
    912345678
    678912345
    567891234
    234567891
    891234567



    Les sudokus auront tous une taille 9×9. Vous pouvez donc raisonnablement utiliser un brute-force. Il existe des algorithmes plus fins pour la résolution, utilisez la méthode que vous sentez le mieux ! :)

    Niveau 1 :

    Pour le niveau le plus simple, contentez-vous de résoudre la grille de la façon qui vous plaît le mieux. Un simple brute-force suffit. :)

    Niveau 2 :

    Ici, nous allons un peu corser les choses. Le but sera maintenant de résoudre le sudoku par une méthode plus efficace, impliquant le backtracking. Yoch, membre habitué de ce forum, a écrit un tutoriel à ce sujet. Le but est donc de lire et comprendre la méthode, mais pas les codes sources. Le but est de les récrire vous-mêmes, sans lire ce qui existe déjà.

    Vous pouvez également vous renseigner au sujet du backtracking sur Wikipédia, ou partout ailleurs sur le web. :)

    Niveau 3 :

    Pour ce dernier niveau, il vous est demandé de faire une résolution pas à pas. À chaque étape, vous devez remplir une seule case libre de la grille, en expliquant pourquoi. Votre explication n'a cependant pas besoin d'être très détaillée. ;)

    Conclusion



    Les Sudokus ont déjà fait l'objet de nombreux exercices, mais j'ose espérer que certains d'entre vous ne l'auront jamais codé. :)

    Bon courage à tous !

    GuilOooo

    S'il y a quelque chose que vous ne comprenez pas, n'hésitez pas à poser votre question sur ce sujet, nous vous répondrons avec plaisir ! :)


    Participants



    Participants Code
    Shaddan Niveau 2
    Pouet_forever Niveau 2
    GurneyH Niveau 2
    yoch Niveau 2
    Marc Mongenet Niveau 2
    kaka551 Niveau 1
    Niveau 2
    • Partager sur Facebook
    • Partager sur Twitter
    Anonyme
      16 septembre 2011 à 19:35:31

      L'exo à l'air pas mal, mais un exo par semaine, c'est pas un peu trop ? Parce que j'ai même pas encore fini le 1er.
      • Partager sur Facebook
      • Partager sur Twitter
        16 septembre 2011 à 23:06:26

        +1

        Je pense que un toutes les 1 semaine et demi ou toutes les 2 semaines serait préférable. :)
        • Partager sur Facebook
        • Partager sur Twitter
        Anonyme
          16 septembre 2011 à 23:12:00

          Je suis d'accord, deux semaines ça me parait raisonnable.
          • Partager sur Facebook
          • Partager sur Twitter
            17 septembre 2011 à 19:10:58

            Il y a 52 exos de prévus, donc il y en a pour déjà un an si on tourne à 1 exo/semaine. :)

            En fait, plus sérieusement, je pense que l'on pourrait en discuter, mais plutôt sur le topic dédié aux exos. Quoiqu'il en soit, on pourrait justifier le rythme un peu soutenu de publication, vu que l'objectif est surtout de contenter tout le monde (il y en a qui finissent vite, il y en a aussi qui ne seront pas intéressés par chaque exo, etc., donc il en faut un peu pour tout le monde).

            De toute les manières, il est parfaitement possible de faire l'exo quand on veut, il n'y a aucun impératif de ce coté. ;)

            Après, c'est sûr que si ça ne convient pas, on changera...
            • Partager sur Facebook
            • Partager sur Twitter
              17 septembre 2011 à 19:48:12

              C'est quoi la différence entre brute force et backtracking?

              Nan parce que selon moi le backtracking expliqué par yoch (à moins que je n'ai pas tout saisi est déjà du brute force)

              Vous incitez les membres à faire un programme qui va tester la grille en mettant dans un premier temps toutes les cases vides à 1 jusqu'à la dernière et tester une fois la grille remplit si elle valide?
              Ensuite c'est la dernière case que l'on a mis à 1 que l'on va mettre à 2, et on reeeteste si c'est valide?

              Ça va jamais marcher ça...
              • Partager sur Facebook
              • Partager sur Twitter
                17 septembre 2011 à 19:58:23

                Citation : Mr21

                C'est quoi la différence entre brute force et backtracking?


                C'est simple.

                Ca c'est un brute force:

                Citation : Mr21

                Vous incitez les membres à faire un programme qui va tester la grille en mettant dans un premier temps toutes les cases vides à 1 jusqu'à la dernière et tester une fois la grille remplit si elle valide?
                Ensuite c'est la dernière case que l'on a mis à 1 que l'on va mettre à 2, et on reeeteste si c'est valide?




                Ca c'est un backtrack :tuto yoch
                • Partager sur Facebook
                • Partager sur Twitter
                  17 septembre 2011 à 20:11:53

                  Oui bah oui, mais pourquoi inciter les membres à perdre leur temps à faire une solution qui ne marchera pas dans les cas où beaucoup de cases sont vides.

                  Passons directement au backtracking non?
                  Et c'est ensuite que le backtracking doit-être optimisé.

                  Dans les défis passés, les gens faisaient tout les niveaux étape par étape, alors que là typiquement le niveau 1 est à éviter :S

                  ---

                  Je sais pas si la question à déjà été traité dans le groupe qui s'occupe de ça, mais pourquoi vous ne donneriez pas dès le début les fichiers de base?
                  Genre un main préparé avec les fonctions qui s'occupent de lire sur l'entrée standard et tout.
                  Histoire que les gens perdent moins de temps sur les trucs chiant du C tout en se concentrant plus sur l'algo.
                  • Partager sur Facebook
                  • Partager sur Twitter
                    17 septembre 2011 à 20:22:18

                    C'est souvent comme ça que ça marche : on commence par faire l'algo le plus simple/intuitif possible, pour enchaîner sur des choses plus complexes.
                    C'est comme si tu disais à un débutant: ça sert à rien d'apprendre un tri insertion, c'est trop lent. Autant commencer par un quicksort super optimisé.

                    Je te signale au passage que pour passer du brute force au backtrack, il n'y qu'un petit pas à faire, donc ce n'est absolument pas du temps perdu.


                    Citation : Mr21



                    Je sais pas si la question à déjà été traité dans le groupe qui s'occupe de ça, mais pourquoi vous ne donneriez pas dès le début les fichiers de base?
                    Genre un main préparé avec les fonctions qui s'occupent de lire sur l'entrée standard et tout.
                    Histoire que les gens perdent moins de temps sur les trucs chiant du C tout en se concentrant plus sur l'algo.

                    Parce que ça se fait en 3 lignes peut-être?
                    • Partager sur Facebook
                    • Partager sur Twitter
                      17 septembre 2011 à 20:37:57

                      En même temps, on est pas trop là pour s'engueuler sur discuter de ces choses la, Mr21, si tu as des remarques, contacte _Fender_, yoch ou encore GuilOooo.
                      Tu peux aussi faire ta remarque en public sur le topic dédier (a chercher dans le forum C ).


                      _ _ _ _
                      Sinon, je suis de l'avis de TD, le niveau 1 est utile, mais c'est un fonctionnement différent des anciens exercices, on ne dois pas se basé sur le premier exo pour faire le second.
                      • Partager sur Facebook
                      • Partager sur Twitter
                      🍊 - Étudiant - Codeur en C | Zeste de Savoir apprenez avec une communauté | Articles  - ♡ Copying is an act of love.
                        17 septembre 2011 à 20:47:25

                        Citation : @che

                        Sinon, je suis de l'avis de TD, le niveau 1 est utile, mais c'est un fonctionnement différent des anciens exercices, on ne dois pas se basé sur le premier exo pour faire le second.

                        Bha tu n'es pas de mon avis alors. :-°

                        Par contre j'ai une question pour le niveau 3 : qu'est-ce qu'on entend par "explications". Il faudrait qu'on nous montre un exemple.
                        J'ai quand même un gros doute sur la faisabilité de ce niveau. :o
                        • Partager sur Facebook
                        • Partager sur Twitter
                          17 septembre 2011 à 20:53:39

                          @Mr21 :
                          Je suis globalement de ton avis, pour faire un brute-force qui aie des chances de terminer en temps raisonnable, il faut un minimum de réflexion (surtout pas l'algo naïf qui va tester les combinaisons que l'on sait invalides). Même avec cette réflexion préalable, je ne suis absolument pas certain que c'est faisable, mais c'est à voir...

                          Je comprends toutefois que le backtracking n'étant pas forcément intuitif pour tout le monde, le premier niveau ait été proposé, mais je conseillerai peut-être de le faire sur des grilles 4x4 :-°

                          Quoi qu'il en soit, il y a diverses niveaux même avec un backtracking, et il existe même d'autres méthodes plus évoluées permettant de résoudre des grilles inaccessibles au backtracking... J'en parlerais, s'il y a des intéressés.

                          Aussi, le niveau 3 est vraiment intéressant. :)

                          PS : je trouve au contraire que ce topic est parfaitement adapté pour en discuter. Ainsi, les participants seront informés.

                          EDIT :

                          Citation : Twisted Destiny

                          Par contre j'ai une question pour le niveau 3 : qu'est-ce qu'on entend par "explications". Il faudrait qu'on nous montre un exemple.
                          J'ai quand même un gros doute sur la faisabilité de ce niveau. :o


                          Personnellement, je pense que c'est la partie la plus intéressante, et franchement assez abordable. Disons que même si tu n'implémente pas toutes les variantes de résolution "humaines" (swordfish, jellyfish et autres :p ), mettre au point un système correct avec 3/4 résolutions de base est vraiment intéressant d'un point de vue algorithmique, et tout à fait à la portée d'une personne capable de faire le niveau 2. J'essaierai de le faire si je trouve le temps.
                          (pour ce qui est de l'explication à mettre, je ne sais pas trop moi même, enfin bon je ne croie pas que ce soit le plus difficile, au pire je me contenterai de donner simplement le niveau de résolution employé...)
                          • Partager sur Facebook
                          • Partager sur Twitter
                            18 septembre 2011 à 14:20:11

                            Le niveau 1 ne me paraissant pas très intéressant, voici pour l'instant ma solution (vraiment pas optimisée pour un sou) pour le niveau 2.

                            #include <stdio.h>
                            #include <stdlib.h>
                            
                            #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 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)
                                      solve(grid, row, col + 1, sol);
                                    else
                                      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 get_grid(Grid grid)
                            {
                              int i, j;
                              for(i = 0; i < SIZE; i++, getchar())
                                for(j = 0; j < SIZE; j++)
                                {
                                  int tmp = getchar();
                                  grid[i][j] = tmp == ' ' ? 0 : tmp - '0';
                                }
                            }
                            
                            void print_grid(Grid grid)
                            {
                              int i, j;
                              for(i = 0; i < SIZE; i++, printf("\n"))
                                for(j = 0; j < SIZE; j++)
                                  printf("%d", grid[i][j]);
                              printf("\n");
                            }
                            
                            int main(void)
                            {
                              Grid grid, sol;
                            
                              get_grid(grid);
                              print_grid(grid);
                              solve(grid, 0, 0, sol);
                              print_grid(sol);
                            
                              return EXIT_SUCCESS;  
                            }
                            

                            C'est un backtracking le plus naïf qui soit : on teste une valeur, si ça marche on fait un appel récursif, et en sortant de l'appel, on remet l'ancienne valeur pour ne pas être bloqué si la solution n'était pas valide. Si lors de l'appel récursif le nombre de lignes est supérieur à la taille du tableau, c'est qu'on a fini donc on copie la solution trouvée avant que toutes les valeurs soient remises à leurs valeurs de départ à la sortie de l'appel récursif.

                            A l'exécution ça donne:

                            ~/Dropbox/Programming/C/sudoku$ ./a.out < grille1.txt 
                            900007100
                            000802070
                            570163000
                            005400936
                            001000200
                            326009800
                            000916083
                            060305000
                            003200001
                            
                            932547168
                            614892375
                            578163429
                            785421936
                            491638257
                            326759814
                            247916583
                            169385742
                            853274691



                            Pour cette grille ça s'exécute assez vite (moins d'une seconde) mais je pense que pour une grille un peu plus compliquée ça risque de n'en pas finir, donc je vais essayer d'améliorer un peu ça et de bosser sur le niveau 3 si j'ai le temps.
                            Je suis évidemment ouvert à tout commentaire.
                            • Partager sur Facebook
                            • Partager sur Twitter
                              18 septembre 2011 à 15:08:06

                              Salut,

                              Quelques remarques vite fait :

                              - On dirait que ton backtracking n'est pas "au courant" si une solution est déjà trouvée ou non. Si c'est bien le cas, c'est dommage, il peut perdre pas mal de temps à tourner dans le vide une fois que la solution est déjà trouvée.
                              - Je ne vois pas comment tu fais la distinction entre les cases vides et les cases pleines.
                              - ...

                              En fait, je viens de voir que tu gère tout ça dans la fonction check_case(). Pas très intuitif selon moi, mais bon...

                              Citation : Shaddan

                              Pour cette grille ça s'exécute assez vite (moins d'une seconde) mais je pense que pour une grille un peu plus compliquée ça risque de n'en pas finir, donc je vais essayer d'améliorer un peu ça [...].


                              Pourquoi ça ne finirait pas ? Tu veux dire que ça va prendre un certain temps à finir ?

                              Si tu es intéressé, il y a un bon "pire des cas" pour algos trop naïfs sur cette page.

                              Aussi, je te suggère d’intégrer une mesure du temps d’exécution dans le code, ainsi tu pourras facilement constater s'il y a progrès ou régression.
                              • Partager sur Facebook
                              • Partager sur Twitter
                                18 septembre 2011 à 15:23:42

                                Étant sous Linux il peut utiliser la commande time devant son binaire tout simplement.

                                Me souvient à l'école on a du le faire cet exo (donc ton tuto ce jour là a du prendre quelques vues je suppose) on avait fait un premier jet avec le backtracking, avec "le pire cas" --> 60sec.
                                On compile avec -o3 --> 20sec \o/
                                • Partager sur Facebook
                                • Partager sur Twitter
                                  18 septembre 2011 à 15:29:17

                                  Citation : Mr21

                                  Me souvient à l'école on a du le faire cet exo (donc ton tuto ce jour là a du prendre quelques vues je suppose) on avait fait un premier jet avec le backtracking, avec "le pire cas" --> 60sec.


                                  Le second jet, c'était quoi ? De compiler avec -o3, ou carrément une autre methode / optimisation ?
                                  • Partager sur Facebook
                                  • Partager sur Twitter
                                    18 septembre 2011 à 15:35:04

                                    Et bien nan, tout le monde le connait ce flag, donc ça revenait au même.

                                    Le second jet bah c'était de rendre le backtracking le plus court possible en trouvant des cases comme un humain (votre niveau 3 donc).

                                    Au final résoudre un grand nombre de fois cette map se faisait en instant'

                                    Je voulais mentionner le fait que -o3 est un peu magique des fois.
                                    • Partager sur Facebook
                                    • Partager sur Twitter
                                      18 septembre 2011 à 18:04:11

                                      Tiens, j'ai retrouvé un témoignage amusant d'un élève d'EPITECH.
                                      • Partager sur Facebook
                                      • Partager sur Twitter
                                        18 septembre 2011 à 18:29:17

                                        C'est presque le même programme tout les ans ouai.

                                        La fork bombe n'a pas dû lui rapporter beaucoup de points sur ce coup là :S
                                        J'aimerai voir le commentaire du correcteur :D

                                        Ce "rush" est une mini-compétition de vitesse d'execution des algos il doit parler de ça quand il parle du server.
                                        • Partager sur Facebook
                                        • Partager sur Twitter
                                          18 septembre 2011 à 19:23:01

                                          @Mr21 :
                                          Au fait, si tu as déjà fait cet exo, n'aurais tu pas un code que tu puisse nous montrer ? ;)

                                          Pour revenir à ce que tu disais plus haut :

                                          Le couplage "backtracking + démarche humaine" est une technique couramment employée, mais selon moi injustifiée dans notre cas : on peut facilement conserver l'approche exclusivement "backtracking" tout en optimisant l'algo. Je pense que c'est d'ailleurs assez pédagogique de constater qu'il puisse y avoir plusieurs niveau de backtracking pour un même problème.

                                          Par exemple, j'avais lu à l'époque ce document sur le problème des N reines. Il est très intéressant de remarquer la multiplicité des approches disponibles et l'écart entre elles.

                                          Concernant le sudoku, il existe une technique pour accélérer (et uniformiser) le temps d’exécution du backtracking, technique à laquelle je fais allusion dans mon tuto. :)
                                          • Partager sur Facebook
                                          • Partager sur Twitter
                                            18 septembre 2011 à 19:45:07

                                            Cet exos était à faire à deux.
                                            Et c'est mon binôme qui a les sources mais jpeux les retrouver, je n'aurais qu'a modifier le truc, pour que ça lise de la même manière que le sujet ici.
                                            • Partager sur Facebook
                                            • Partager sur Twitter
                                              18 septembre 2011 à 19:51:55

                                              Cet exo m'intéresse beaucoup, mais j'ai de moins en moins de temps pour le faire :'(

                                              Je ne pense pas que je pourrais le faire cette semaine ...
                                              • Partager sur Facebook
                                              • Partager sur Twitter
                                              🍊 - Étudiant - Codeur en C | Zeste de Savoir apprenez avec une communauté | Articles  - ♡ Copying is an act of love.
                                                18 septembre 2011 à 20:41:31

                                                yoch > Combien de temps met ton programme pour résoudre cette grille :

                                                5 8 
                                                   6 1 43
                                                         
                                                 1 5     
                                                   1 6   
                                                3       5
                                                53     61
                                                        4

                                                J'ai vu qu'on pouvait résoudre le truc en posant le truc comme un problème linéaire, c'est sympa comme truc et ça permet de résoudre n'importe quelle grille hyper rapidement. :) Par contre il faut tout pondre pour résoudre les équations. :-°
                                                J'ai pensé à faire une modélisation 3D de la grille, mais je ne suis pas sûr que ça soit mieux parce qu'on va faire plein d'affectations. :s

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

                                                #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 };
                                                  
                                                  printGrid(grid);
                                                  resolve(grid, 0);
                                                  printGrid(grid);
                                                  
                                                  return EXIT_SUCCESS;
                                                }
                                                


                                                Edit: Combien vous pensez avoir de participants à partir de ce 'défi' ? :-°
                                                Aurant zmol et le jeu de la vie, il n'y avait pas trop besoin de connaître d'algo, tandis que là, c'est plus trop pour débutant. :lol:
                                                • Partager sur Facebook
                                                • Partager sur Twitter
                                                  18 septembre 2011 à 20:59:15

                                                  Petite remarque, mais qui m'embête vraiment beaucoup : pourquoi demander de représenter les cases vides par des ESPACES. Je suis désolé mais c'est vraiment horrible, autant pour lire l'entrée (c'est le bordel avec scanf, getchar &co) que pour visualiser la grille (on se tue les yeux lorsque la grille est presque vide).


                                                  A part ça, je trouve qu'on devrait rajouter un 4e niveau (de toute façon presque personne va faire le 3 je pense) : Celui qui a l'algo le plus rapide gagne. :D
                                                  • Partager sur Facebook
                                                  • Partager sur Twitter
                                                    18 septembre 2011 à 21:03:05

                                                    Pour l'algo le plus rapide, je pense que l'algo que j'ai dit plus haut devrait être le plus rapide (programmation linéaire). :)
                                                    Sur les grilles les plus dures il tape aux alentours de 1s à tout casser. :)

                                                    +1 pour les espaces, j'avais des . avant mais j'ai remplacé pour coller à l'exo. :-°
                                                    • Partager sur Facebook
                                                    • Partager sur Twitter
                                                      18 septembre 2011 à 21:07:39

                                                      Pouet as-tu un lien? Ca à l'air assez mathématique tel que tu le décris.


                                                      Ca serait bien que tout le monde partage des liens sur les différents algorithmes pour résoudre les sudoku...(et qu'on les regroupe sur le 1er post quoi).
                                                      • Partager sur Facebook
                                                      • Partager sur Twitter
                                                        18 septembre 2011 à 21:15:57

                                                        En effet, c'est mathématique. :)
                                                        Il suffit de taper 'résolution sudoku programmation linéaire' sur google et il y a plein de liens intéressants. Ce lien, en français, est assez bien étoffé et avec des exemples et un exemple de code en C++ à la fin. Il donne aussi une représentation du cube que je voulais faire. :)
                                                        J'ai d'autres liens, mais je n'ai pas fini de les lire. ^^
                                                        • Partager sur Facebook
                                                        • Partager sur Twitter
                                                          18 septembre 2011 à 21:31:27

                                                          Citation : Pouet_forever

                                                          yoch > Combien de temps met ton programme pour résoudre cette grille :

                                                          5 8 
                                                             6 1 43
                                                                   
                                                           1 5     
                                                             1 6   
                                                          3       5
                                                          53     61
                                                                  4



                                                          Tel quel, il n'y a pas de solution, il manque une ligne (j'ai essayé aussi de mettre une ligne vide en début ou en fin, et il n'existe pas de solution non plus :-° ). Y a pas une erreur quelque part ?

                                                          Citation : Pouet_forever

                                                          Pour l'algo le plus rapide, je pense que l'algo que j'ai dit plus haut devrait être le plus rapide (programmation linéaire). :)
                                                          Sur les grilles les plus dures il tape aux alentours de 1s à tout casser. :)


                                                          Je n'ai pas bien saisi l'algo, mais 1 seconde, c'est enorme pour résoudre un 9x9... :-°

                                                          Je crois que le meilleur algo connu pour résoudre les sudokus, si on généralise le problème (n'importe quelle taille de grille), est en ramenant le problème au "problème de couverture exacte", et en utilisant l'algo des dancings-links de D. Knuth. Ce n'est pas mortel à implémenter (en plus, ça peut résoudre des tas d'autres trucs que les sudokus :p ), mais c'est quand même plutôt technique.
                                                          Mais pour les sudoku 9x9, il n'y a aucun intérêt pratique, car un bon backtracking résout n'importe quelle grille en quelques millisecondes (plus vite même qu'un DLX d’après mes expérimentations).

                                                          • Partager sur Facebook
                                                          • Partager sur Twitter
                                                            18 septembre 2011 à 21:41:57

                                                            1 seconde c'est peut-être énorme, mais c'est le pire des cas que je cite. :)
                                                            Dans plus de 99% des cas c'est quelques millisecondes. ;)
                                                            Tu dis que le backtracking résous tout en quelques millisecondes, je serais curieux de voir ton programme confronté à certaines grilles (notamment celle que je propose). Il y a toujours quelques grilles qui pose problème et où je suis persuadé que ton code flanchera (au dessus de la barre des 20s). ;)
                                                            Bon, après je n'ai pas fait de recherches approfondies sur le sujet, je vais regarder ce que tu proposes. :)

                                                            La grille c'est ça (zcode qui supprime les espaces...) :

                                                            .....5.8.
                                                            ...6.1.43
                                                            .........
                                                            .1.5.....
                                                            ...1.6...
                                                            3.......5
                                                            53.....61
                                                            ........4
                                                            .........
                                                            • Partager sur Facebook
                                                            • Partager sur Twitter
                                                              18 septembre 2011 à 22:26:46

                                                              Soit j'ai mal copié ta grille, soit elle est fausse, soit mon programme a un gros souci. :-°
                                                              Bref, pour l'instant mon programme me renvoie la grille telle quelle, c.a.d qu'il ne trouve pas de solution.

                                                              Bon, je verrai ça demain, je vais dormir...
                                                              • 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