3MMALG11 Sudoku

De Ensiwiki
Aller à : navigation, rechercher
AttentionCette page est maintenue uniquement par les enseignants. Afin de ne pas perturber le déroulement des cours, elle n'a pas vocation à être modifiée par les élèves. Mais si vous avez des modifications à proposer, merci d'en discuter ou d'envoyer un e-mail aux auteurs de la page (cf. historique)

Résolution d'une grille de Sudoku

Le but de l'exercice est de programmer une procédure de résolution pour le jeu du Sudoku. Le principe de ce jeu consiste à partir d'une grille 9x9 dans laquelle certaines cases sont déjà remplies :

Algo1 Soutien Sudoku Init.png

et de remplir cette grille complètement avec des chiffres compris 1 et 9, en respectant les contraintes suivantes :

  • chaque bloc de 3x3 (délimités en gras dans l'image ci-dessus) doit contenir chaque chiffre une et une seule fois ;
  • chaque ligne de la grille doit contenir chaque chiffre une et une seule fois ;
  • chaque colonne de la grille doit contenir chaque chiffre une et une seule fois.

Une grille de Sudoku valide est construite de façon à garantir qu'il y a une et une seule solution :

Algo1 Soutien Sudoku Sol.png

Pour résoudre ce problème, on va utiliser un algorithme fonctionnant sur le même principe que celui utilisé dans l'exercice sur les N reines par exemple : pour chaque case de la grille, on place une valeur valide, on essaie de résoudre le reste de la grille, et si on n'y arrive pas, on revient en arrière pour essayer une autre valeur.

Vous devez donc compléter le code ci-dessous en implantant la procédure récursive CalculeSolution (copier-coller ce code dans un fichier sudoku.adb) :

with Ada.Text_IO;
use Ada.Text_IO;

procedure Sudoku is

   Taille: constant Integer := 9;
   TailleBloc: constant Integer := 3;

   CaseVide: constant Integer := 0;
   subtype ValCase is Integer range 0 .. 9;
   subtype ValJeu is Integer range 1 .. 9;

   type Plateau is array(0 .. Taille - 1, 0 .. Taille - 1) of ValCase;

   Grille1 : Plateau := ((0, 0, 4, 0, 0, 0, 9, 2, 1),
                         (0, 0, 1, 9, 0, 4, 0, 6, 0),
                         (6, 0, 0, 0, 1, 0, 0, 0, 0),
                         (0, 0, 7, 1, 9, 0, 0, 0, 0),
                         (1, 0, 0, 3, 0, 7, 0, 0, 5),
                         (0, 0, 0, 0, 5, 8, 7, 0, 0),
                         (0, 0, 0, 0, 4, 0, 0, 0, 3),
                         (0, 3, 0, 2, 0, 5, 1, 0, 0),
                         (7, 1, 8, 0, 0, 0, 4, 0, 0));

   Sol1 : constant Plateau := ((3, 7, 4, 5, 8, 6, 9, 2, 1),
                               (8, 5, 1, 9, 2, 4, 3, 6, 7),
                               (6, 9, 2, 7, 1, 3, 5, 8, 4),
                               (5, 4, 7, 1, 9, 2, 8, 3, 6),
                               (1, 8, 9, 3, 6, 7, 2, 4, 5),
                               (2, 6, 3, 4, 5, 8, 7, 1, 9),
                               (9, 2, 5, 8, 4, 1, 6, 7, 3),
                               (4, 3, 6, 2, 7, 5, 1, 9, 8),
                               (7, 1, 8, 6, 3, 9, 4, 5, 2));

   Grille2 : Plateau := ((5, 0, 3, 7, 9, 0, 0, 0, 4),
                         (0, 1, 0, 0, 0, 5, 7, 0, 0),
                         (9, 4, 0, 0, 0, 0, 0, 0, 2),
                         (8, 0, 0, 0, 1, 0, 3, 6, 0),
                         (0, 9, 6, 0, 0, 0, 4, 2, 0),
                         (0, 3, 5, 0, 4, 0, 0, 0, 1),
                         (3, 0, 0, 0, 0, 0, 0, 4, 6),
                         (0, 0, 1, 8, 0, 0, 0, 3, 0),
                         (4, 0, 0, 0, 6, 3, 2, 0, 8));

   Sol2 : constant Plateau := ((5, 8, 3, 7, 9, 2, 6, 1, 4),
                               (6, 1, 2, 4, 8, 5, 7, 9, 3),
                               (9, 4, 7, 6, 3, 1, 8, 5, 2),
                               (8, 2, 4, 9, 1, 7, 3, 6, 5),
                               (1, 9, 6, 3, 5, 8, 4, 2, 7),
                               (7, 3, 5, 2, 4, 6, 9, 8, 1),
                               (3, 7, 8, 5, 2, 9, 1, 4, 6),
                               (2, 6, 1, 8, 7, 4, 5, 3, 9),
                               (4, 5, 9, 1, 6, 3, 2, 7, 8));

   Grille3 : Plateau := ((1, 0, 8, 0, 9, 0, 0, 0, 0),
                         (2, 0, 0, 3, 0, 8, 0, 9, 6),
                         (0, 9, 0, 0, 0, 0, 4, 0, 0),
                         (4, 0, 6, 0, 0, 9, 0, 3, 0),
                         (0, 1, 0, 2, 0, 5, 0, 6, 0),
                         (0, 8, 0, 6, 0, 0, 2, 0, 1),
                         (0, 0, 1, 0, 0, 0, 0, 4, 0),
                         (3, 6, 0, 9, 0, 4, 0, 0, 7),
                         (0, 0, 0, 0, 6, 0, 3, 0, 5));

   Sol3 : constant Plateau := ((1, 3, 8, 4, 9, 6, 7, 5, 2),
                               (2, 5, 4, 3, 7, 8, 1, 9, 6),
                               (6, 9, 7, 5, 2, 1, 4, 8, 3),
                               (4, 2, 6, 7, 1, 9, 5, 3, 8),
                               (7, 1, 3, 2, 8, 5, 9, 6, 4),
                               (9, 8, 5, 6, 4, 3, 2, 7, 1),
                               (5, 7, 1, 8, 3, 2, 6, 4, 9),
                               (3, 6, 2, 9, 5, 4, 8, 1, 7),
                               (8, 4, 9, 1, 6, 7, 3, 2, 5));

   Grille4 : Plateau := ((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));

   Sol4 : constant Plateau := ((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));

   procedure AfficheGrille(Grille: in Plateau) is
      procedure AfficheLigne is
      begin
         for I in 1 .. Taille * 2 + (Taille / TailleBloc) * 2 + 1 loop
            Put("-");
         end loop;
         New_Line;
      end AfficheLigne;
      function CarVal(V: ValCase) return Character is
      begin
         if V = CaseVide then
            return ' ';
         else
            return Character'Val(V + Character'Pos('0'));
         end if;
      end CarVal;
   begin
      for L in Grille'Range(1) loop
         if L mod TailleBloc = 0 then
            AfficheLigne;
         end if;
         for C in Grille'Range(2) loop
            if C mod TailleBloc = 0 then
               Put("| ");
            end if;
            Put(CarVal(Grille(L,C)) & " ");
         end loop;
         Put_Line("|");
      end loop;
      AfficheLigne;
   end AfficheGrille;

   procedure RemplitGrille(Grille: in out Plateau) is

      --  Un coup est possible ssi V n'apparait pas deja :
      --    * sur la meme ligne
      --    * sur la meme colonne
      --    * ni dans le meme bloc 3x3
      function CoupPossible(L, C: Integer; V: ValCase) return Boolean is
         function DebutBloc(X: Integer) return Integer is
         begin
            return (X / TailleBloc) * TailleBloc;
         end DebutBloc;
      begin
         --  On cherche sur la ligne
         for I in Grille'Range(2) loop
            if Grille(L, I) = V then
               return False;
            end if;
         end loop;
         --  On cherche sur la colonne
         for I in Grille'Range(1) loop
            if Grille(I, C) = V then
               return False;
            end if;
         end loop;
         --  On cherche dans le bloc
         for I in 0 .. TailleBloc  - 1 loop
            for J in 0 .. TailleBloc - 1 loop
               if Grille(DebutBloc(L) + I, DebutBloc(C) + J) = V then
                  return False;
               end if;
            end loop;
         end loop;
         return True;
      end CoupPossible;

      Trouve: exception;

      procedure CalculeSolution(L, C: Integer) is
      begin
         --  A COMPLETER !!
         null;
      end CalculeSolution;

   begin
      Put_Line("Grille initiale :");
      AfficheGrille(Grille); New_Line;
      Put_Line("Calcul de la solution...");
      CalculeSolution(0, 0);
      Put_Line("ERREUR : la grille initiale n'a pas de solution !");
   exception
      when Trouve => null; --  c'est le point de sortie normal
   end RemplitGrille;

   procedure TestGrille(Grille: in out Plateau; Sol: Plateau; Msg: String) is
   begin
      Put_Line("***** " & Msg & " *****"); New_Line;
      RemplitGrille(Grille);
      if Grille /= Sol then
         Put_Line("ERREUR : la solution trouvee est fausse !");
      else
         AfficheGrille(Grille);
      end if;
      New_Line; New_Line;
   end TestGrille;

begin
   TestGrille(Grille1, Sol1, "Exemple 1");
   TestGrille(Grille2, Sol2, "Exemple 2");
   TestGrille(Grille3, Sol3, "Exemple 3");
   TestGrille(Grille4, Sol4, "Exemple tres lent");
end Sudoku;

On donne dans le code 4 exemples de grilles avec leurs solutions. A votre avis, pourquoi la dernière nécessite-t'elle autant de temps pour être résolue ?