WITH Ada.Text_IO, Ada.Integer_Text_IO;
USE Ada.Text_IO, Ada.Integer_Text_IO;

PROCEDURE Sudoku IS

   --------------------------- ETAPE 1 : DECLARATION DES TYPES ---------------------------

   TYPE TCarre IS ARRAY (Integer RANGE 1 .. 9, Integer RANGE 1 .. 9) OF Integer;
   TYPE TPossibles IS ARRAY (Integer RANGE 1 .. 9) OF Boolean;
   TYPE TVectPossibles IS
      RECORD
         Nb   : Integer;
         Vect : Tpossibles;
      END RECORD;
   TYPE TCube IS ARRAY (Integer RANGE 1 .. 9, Integer RANGE 1 .. 9) OF TVectPossibles;
   TYPE TVectCarre IS ARRAY (1 .. 40) OF Tcarre;
   TYPE TVectCoord IS ARRAY (1 .. 40, 1 .. 4) OF Integer;


   --------------------------- DECLARATION DES VARIABLES ---------------------------

   Sudoku  : TvectPossibles;
   Grille,
   Grille2 : TCarre;
   Cube    : TCube;
   X,
   Y,
   Z       : Integer;


   --------------------------- ETAPE 2 : Procédures et fonctions de base de la grille de jeu ---------------------------
   PROCEDURE Affiche (
         Mat : IN     TCarre) IS
      X : Integer := 0;
   BEGIN
      FOR I IN 1..9 LOOP
         FOR J IN 1..9 LOOP
            X := Mat(I,J);
            Put(X,0);
            Put("  ");
         END LOOP;
         New_Line(2);
      END LOOP;
   END Affiche;

   PROCEDURE Recopie (
         Mat  : IN     TCarre;
         Mat2 :    OUT TCarre) IS
   BEGIN
      FOR I IN 1..9 LOOP
         FOR J IN 1..9 LOOP
            Mat2(I,J) := Mat(I,J);
         END LOOP;
      END LOOP;
   END Recopie;

   FUNCTION PlusDeCasesNulles (
         Mat : IN     TCarre)
     RETURN Boolean IS
      Flag : Boolean := True;
   BEGIN
      FOR I IN 1..9 LOOP
         FOR J IN 1..9 LOOP
            IF (Mat(I,J) = 0) THEN
               Flag := False;
            END IF;
         END LOOP;
      END LOOP;
      RETURN (Flag);
   END PlusDeCasesNulles;

   --------------------------- ETAPE 3 : Existence d'une valeur dans une unité ---------------------------

   FUNCTION ExisteDansLigne (
         Mat    : IN     TCarre;
         NumLig : IN     Integer;
         X      : IN     Integer)
     RETURN Boolean IS
      Flag : Boolean := True;
   BEGIN
      FOR I IN 1..9 LOOP
         IF (Mat(I,NumLig) = X) THEN
            Flag := False;
         END IF;
      END LOOP;
      RETURN (Flag);
   END ExisteDansLigne;

   FUNCTION ExisteDansColonne (
         Mat    : IN     TCarre;
         NumCol : IN     Integer;
         X      : IN     Integer)
     RETURN Boolean IS
      Flag : Boolean := True;
   BEGIN
      FOR I IN 1..9 LOOP
         IF (Mat(NumCol,I) = X) THEN
            Flag := False;
         END IF;
      END LOOP;
      RETURN (Flag);
   END ExisteDansColonne;

   FUNCTION ExisteDansRegion (
         Mat : IN     TCarre;
         X   : IN     Integer;
         K   : IN     Integer;
         L   : IN     Integer)
     RETURN Boolean IS
      Flag : Boolean := False;
      Lig  : Integer := K;
      Col  : Integer := L;
   BEGIN
      Lig := (Lig-1)/3 * 3 ;
      Col := (Col-1)/3 * 3 ;
      FOR I IN 1+Lig .. 3+Lig LOOP
         FOR J IN 1+Col .. 3+Col LOOP
            IF Mat (I,J)= X THEN
               Flag := True;
            END IF;
         END LOOP;
      END LOOP;
      RETURN Flag;
   END ExisteDansRegion;

   --------------------------- ETAPE 4 : Gestion des possibles ---------------------------

   PROCEDURE InitLesPossibles (
         T : IN OUT TVectPossibles) IS
   BEGIN
      FOR I IN 1..9 LOOP
         T.Vect(I) := False;
      END LOOP;
      T.Nb := 0;
   END InitLesPossibles;

   PROCEDURE InitCube (
         Cube : IN     TCube) IS
      X : TVectPossibles;
   BEGIN
      FOR I IN 1..9 LOOP
         FOR J IN 1..9 LOOP
            X := Cube(I,J);
            InitLesPossibles(X);
         END LOOP;
      END LOOP;
   END InitCube;

   PROCEDURE ValeursPossiblesDansRegion (
         Grille : IN     TCarre;
         K,
         L      : IN     Integer;
         Cub    : IN OUT TCube) IS
      -- Pré-requis : K et L doivent être égaux à 1, 4 ou 7
      N : Integer := 0;
   BEGIN
      FOR I IN K..K+2 LOOP
         FOR J IN L..L+2 LOOP
            N := 0;
            InitLesPossibles(Cub(I,J));
            IF Grille(I,J) = 0 THEN
               FOR X IN 1..9 LOOP
                  IF ExisteDansLigne(Grille, I, X) = False THEN
                     IF ExisteDansColonne(Grille, J, X) = False THEN
                        IF ExisteDansRegion(Grille, K, L, X) = False THEN
                           Cub(I,J).Vect(X) := True;
                           Cub(I,J).Nb := N + 1;
                        END IF;
                     END IF;
                  END IF;
               END LOOP;
            END IF;
         END LOOP;
      END LOOP;
   END ValeursPossiblesDansRegion;

   PROCEDURE ValeursPossiblesJeu (
         Grille : IN     TCarre;
         Cube   : IN OUT TCube) IS
   BEGIN
      FOR I IN 1..9 LOOP
         FOR J IN 1..9 LOOP
            ValeursPossiblesDansRegion(Grille,I,J,Cube);
         END LOOP;
      END LOOP;
   END ValeursPossiblesJeu;

   FUNCTION SeulPossibleDansLigne (
         Cub    : IN     TCube;
         Lig,
         Valeur : IN     Integer)
     RETURN Boolean IS
      -- si dans valeur possible y'a qu'une seule valeur juste alors flag = true
      Stock : Integer := 0;
   BEGIN
      FOR I IN 1..9 LOOP
         IF (Cub(Lig,I).Vect(Valeur)) THEN
            Stock := Stock + 1;
         END IF;
      END LOOP;
      RETURN(Stock = 1);
   END SeulPossibleDansLigne;

   FUNCTION SeulPossibleDansColonne (
         Cub    : IN     TCube;
         Col,
         Valeur : IN     Integer)
     RETURN Boolean IS
      Stock : Integer := 0;
   BEGIN
      FOR I IN 1..9 LOOP
         IF (Cub(I,Col).Vect(Valeur)) THEN
            Stock := Stock + 1;
         END IF;
      END LOOP;
      RETURN(Stock = 1);
   END SeulPossibleDansColonne;

   FUNCTION SeulPossibleDansRegion (
         Cub    : IN     TCube;
         Lig,
         Col,
         Valeur : IN     Integer)
     RETURN Boolean IS
      L     : Integer := Lig;
      K     : Integer := Col;
      Stock : Integer := 0;

   BEGIN
      L := (Lig-1)/3 * 3 ;
      K := (Col-1)/3 * 3 ;
      FOR I IN 1+Lig .. 3+Lig LOOP
         FOR J IN 1+Col .. 3+Col LOOP
            IF (Cub(I,J).Vect(Valeur)) THEN
               Stock := Stock + 1;
            END IF;
         END LOOP;
      END LOOP;
      RETURN (Stock = 1);
   END SeulPossibleDansRegion;

   --------------------------- ETAPE 5 : Jeu ---------------------------

   FUNCTION CandidatUnique (
         Lig,
         Col,
         Valeur : Integer;
         Cub    : TCube)
     RETURN Boolean IS
   BEGIN
      IF SeulPossibleDansLigne(Cub,Lig,Valeur) OR SeulPossibleDansColonne(
            Cub,Col,Valeur) OR SeulPossibleDansRegion(Cub,Lig,Col,Valeur) THEN
         RETURN(True);
      ELSE
         RETURN(False);
      END IF;
   END CandidatUnique;

   PROCEDURE VARIATION_COORD (
         Num : IN     Integer;
         K1,
         K2  :    OUT Integer) IS
   BEGIN
      IF (Num mod 3 = 1) THEN
         K1 := 1;
         K2 := 2;
      ELSIF (Num mod 3 = 2) THEN
         K1 := -1;
         K2 := 1;
      ELSE
         K1 := -1;
         K2 := -2;
      END IF;
   END VARIATION_COORD;

   FUNCTION PositionUnique (
         Mat_Carre : IN     TCarre;
         Lig,
         Col,
         Val       : IN     Integer)
     RETURN Boolean IS
      X1,
      X2,
      Lig1,
      Lig2,
      Col1,
      Col2 : Integer;
   BEGIN
      Variation_Coord(Lig,X1,X2);
      Lig1 := Lig + X1;
      Lig2 := Lig + X2;

      Variation_Coord(Col,X1,X2);
      Col1 := Col + X1;
      Col2 := Col + X2;

      RETURN ((ExisteDansLigne(Mat_Carre, Lig1, Val) AND ExisteDansLigne(
               Mat_Carre, Lig2, Val) AND ExisteDansColonne(Mat_Carre, Col1,
               Val) AND ExisteDansColonne(Mat_Carre, Col2, Val))
         OR  (ExisteDansLigne(Mat_Carre, Lig1, Val) AND ExisteDansLigne(
               Mat_Carre, Lig2, Val) AND Mat_Carre(Lig,Col1) /= 0 AND
            Mat_Carre(Lig,Col2) /= 0 )
         OR  (ExisteDansColonne(Mat_Carre, Col1, Val) AND
            ExisteDansColonne(Mat_Carre, Col2, Val) AND Mat_Carre(Lig1,
               Col ) /= 0 AND  Mat_Carre(Lig2,Col) /=0 ));
   END;

   --------------------------- PARTIE II Etape 2 ------------------------------
   PROCEDURE PROPOSE (
         C     : IN OUT TCarre;
         Cub   : IN     TCube;
         Lig,
         Col,
         Val   :    OUT Integer;
         Stop1 : IN OUT Boolean) IS
      I,
      J,
      K     : Integer := 1;
      Flag,
      Flag2 : Boolean := False;
   BEGIN
      WHILE Flag=False AND (I/=10) LOOP
         IF C(I,J)=0 THEN
            Lig:=I;
            Col:=J;
            Flag:=True;
            WHILE Flag2=False LOOP
               IF Cub(I,J).Vect(K) THEN
                  Val:=K;
                  Flag2:=True;
               ELSE
                  K:=K+1;
               END IF;
            END LOOP;
            Stop1:=True;
            C(I,J):=Val;
         ELSE
            J:=J+1;
            IF J=10 THEN
               I:=I+1;
               J:=1;
            END IF;
         END IF;
      END LOOP;
   END PROPOSE;

   PROCEDURE PROPOSE2 (
      C   : IN OUT TCarre;
      Cub : IN     TCube;
      Lig,
      Col : IN     Integer;
         Val : IN OUT Integer) IS
      Flag:Boolean:=False;
      K:Integer :=Val+1;
   BEGIN
      WHILE Flag=False OR K<10 LOOP
         IF Cub(Lig,Col).Vect(K) THEN
            Val:=K;
            Flag:=True;
         END IF;
         K:=K+1;
      END LOOP;
   END PROPOSE2;


   FUNCTION IL_EXISTE_CASE_SANS_CANDIDAT (C : IN TCarre; Cube : IN TCube) RETURN Boolean IS
      I,J : Integer := 1;
      Flag : Boolean := False;
   BEGIN
      WHILE (I >= 9) OR (Flag = False) LOOP
         WHILE (J >= 9) OR (Flag = False) LOOP
            IF (C(I,J) = 0) THEN
               Flag := True;
            END IF;
            J := J+1;
         END LOOP;
         I := I+1;
      END LOOP;
         RETURN(Cube(I,J).Nb = 0);
   END IL_EXISTE_CASE_SANS_CANDIDAT;

   --------------------------- PARTIE II Etape 3 ------------------------------





   --------------------------- PROCEDURE PRINCIPALE ---------------------------


BEGIN
   -- Initialisation matrice
--   Grille := ((0,0,0,0,4,0,5,0,0),(0,5,0,0,0,0,6,0,3),(6,0,1,5,0,0,0,0,0),
--      (0,0,0,1,9,0,0,6,0),(0,7,0,0,0,0,0,4,0),(0,8,0,0,6,2,0,0,0),
--      (0,0,0,0,0,8,4,0,9),(4,0,7,0,0,0,0,8,0),(0,0,3,0,2,0,0,0,0));

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

   -- EXEMPLES DE GRILLES:

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

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

   Put("Bienvenue");
   New_Line(2);
   Affiche(Grille);
   Recopie(Grille,Grille2);
   InitCube(Cube);
   WHILE(NOT(Plusdecasesnulles(Grille2))) LOOP
      FOR I IN 1..9 LOOP
         FOR J IN 1..9 LOOP
            Put ("Ligne ?");
            Get(X);
            Put ("Colonne ?");
            Get(Y);
            IF X<0 OR X>9 OR Y<0 OR Y>9 THEN
               Put ("Case invalide");
               New_Line;
            ELSE
               Put ("Chiffre ?");
               Get(Z);
               New_Line(3);
               IF Z<0 OR Z>9 THEN
                  Put("Chiffre invalide");
                  New_Line;
               END IF;
               IF ((ExisteDansLigne(Grille,X,Z)) OR (ExisteDansColonne(Grille,X,Z)) OR (ExisteDansRegion(Grille,X,Y,Z))) THEN
                     IF (ExisteDansLigne(Grille,X,Z)) THEN
                     Put("Valeur impossible car est present dans la ligne");
                     new_line;
                     END IF;
                     IF (ExisteDansColonne(Grille,X,Z)) THEN
                     Put("Valeur impossible car est present dans la colonne");
                     new_line;
                     END IF;
                     IF (ExisteDansRegion(Grille,X,Y,Z)) THEN
                     Put("Valeur impossible car est present dans la region");
                     new_line;
                     END IF;
                     ELSE
                  Grille2(X,Y):=Z;
                  Affiche(Grille2);
               END IF;
            END IF;
         END LOOP;
      END LOOP;
   END LOOP;

END Sudoku;