/*Réalisé par
  Laurent Mortroux
  rue Porte Grumsel 6
  4020 Liège
  Belgique*/

#include <stdio.h>
#include <conio.h>

#define Cote 10
#define Max 9
#define Valide 55

int **PTableau=NULL;
int **PSoluce=NULL;

main()
{
void Initialisation_Lignes_Possibles(int Tableau[Cote][Cote], int Soluce[Cote][Cote], int Ligne_Valides[Valide][Cote], int *Max_Comb);
int Teste_Si_Grille_Juste(int Max_Ligne);

int Tableau[Cote][Cote];int Soluce[Cote][Cote];int Ligne_Valides[Valide][Cote];
register int L0,L1,L2,L3,L4,L5,L6,L7,L8,OK,I,J;
int Max_Comb,Blanc_Ninimal,Cases_Blanches;
float Temp;

Max_Comb=0;
Blanc_Ninimal=50;

clrscr();
printf("Attendez");

Initialisation_Lignes_Possibles(Tableau,Soluce,Ligne_Valides,&Max_Comb);
PTableau=(int **)Tableau;

for (L0=0;L0<Max_Comb;++L0)            /*Teste toute les possibilitée*/
   {
   PTableau[0]=Ligne_Valides[L0];
   for (L1=0;L1<Max_Comb;++L1)
      {
      PTableau[1]=Ligne_Valides[L1];
      for (L2=0;L2<Max_Comb;++L2)
	 {
	 PTableau[2]=Ligne_Valides[L2];
	 for (L3=0;L3<Max_Comb;++L3)
	    {
	    PTableau[3]=Ligne_Valides[L3];
	    if (Teste_Si_Grille_Juste(4)){
	    for (L4=0;L4<Max_Comb;++L4)
	       {
	       PTableau[4]=Ligne_Valides[L4];
	       if (Teste_Si_Grille_Juste(5)){
		  for (L5=0;L5<Max_Comb;++L5)
		     {
		     PTableau[5]=Ligne_Valides[L5];
		     if (Teste_Si_Grille_Juste(6)){
		     for (L6=0;L6<Max_Comb;++L6)
			{
			PTableau[6]=Ligne_Valides[L6];
			if (Teste_Si_Grille_Juste(7)){
			for (L7=0;L7<Max_Comb;++L7)
			   {
			   PTableau[7]=Ligne_Valides[L7];
			   if (Teste_Si_Grille_Juste(8)){
			   for (L8=0;L8<Max_Comb;++L8)
			      {
/*Copie Ligne ds Tableau*/    PTableau[8]=Ligne_Valides[L8];
/*Teste Si grille est OK*/    OK=-1; OK=Teste_Si_Grille_Juste(9);
/*Compte cases blanches*/     Cases_Blanches=0;
			      for (I=0;I<Max;I++)
				 {
				 Cases_Blanches=Cases_Blanches+*(*(PTableau+I)+9);
				 }
/*Teste meilleur soluce*/     if (Blanc_Ninimal>Cases_Blanches && OK==1)
				 {
				  Blanc_Ninimal=Cases_Blanches;
				  for (J=0;J<Max;J++)
				     {
/*Copie la solution*/                PSoluce[J]=PTableau[J];
				     }
				 }
			      }
			      }
			   }
			   }
			}
			}
		     }
		     }
	       }
	       }
	    }
	 }
      }
   }

clrscr();
for(I=0;I<Max;I++)
   {
   for(J=0;J<Max;J++)
      {
      printf(" %d ",*(*(PSoluce+I)+J));
      }
   printf("\n");
   }
printf(" Solution avec %d cases blanches.\n",Blanc_Ninimal);
}

int Teste_Si_Grille_Juste(int Max_Ligne)
{
register int I,J;
for (I=0;I<Max_Ligne;++I)
   {
   for (J=0;J<Max;++J)
      {
      if (I>2 && *(*(PTableau+I)+J)==0)
	 {
	 if (*(*(PTableau+I-1)+J)==0 && *(*(PTableau+I-2)+J)==0 && *(*(PTableau+I-3)+J)==0)
	    {return 0;}

	 if (J<6 && *(*(PTableau+I-1)+J+1)==0 && *(*(PTableau+I-2)+J+2)==0 && *(*(PTableau+I-3)+J+3)==0)
	    {return 0;}

	 if (J>2 && *(*(PTableau+I-1)+J-1)==0 && *(*(PTableau+I-2)+J-2)==0 && *(*(PTableau+I-3)+J-3)==0)
	    {return 0;}
	 }
      }
   }
return 1;
}

void Initialisation_Lignes_Possibles(int Tableau[Cote][Cote], int Soluce[Cote][Cote], int Ligne_Valides[Valide][Cote], int *Max_Comb)
{
int Ligne[Max]={0,0,0,0,0,0,0,0,0};
register int I,J,Case_Blanches,Case_Noir;

for (Ligne[0]=0;Ligne[0]<2;++Ligne[0])
   {
   for (Ligne[1]=0;Ligne[1]<2;++Ligne[1])
      {
      for (Ligne[2]=0;Ligne[2]<2;++Ligne[2])
	 {
	 for (Ligne[3]=0;Ligne[3]<2;++Ligne[3])
	    {
	    for (Ligne[4]=0;Ligne[4]<2;++Ligne[4])
	       {
	       for (Ligne[5]=0;Ligne[5]<2;++Ligne[5])
		  {
		  for (Ligne[6]=0;Ligne[6]<2;++Ligne[6])
		     {
		     for (Ligne[7]=0;Ligne[7]<2;++Ligne[7])
			{
			for (Ligne[8]=0;Ligne[8]<2;++Ligne[8])
			   {
			   Case_Noir=0;
			   Case_Blanches=0;
			   for(I=8;I>-1;I--)
			      {
			      if (Ligne[I]==1 && Case_Noir<4)
				 {
				 Case_Noir=0;
				 ++Case_Blanches;
				 }
			      else
				 {
				 ++Case_Noir;
				 }
			      }
			   if (Case_Noir<4 && Case_Blanches<4)
			      {
			      for(I=0;I<Max;I++)    /*Copie de la ligne valide*/
				 {
				 Ligne_Valides[*Max_Comb][I]=Ligne[I];
				 }
			      Ligne_Valides[*Max_Comb][9]=Case_Blanches;
			      *Max_Comb=*Max_Comb+1;
			      }
			   }
			}
		     }
		  }
	       }
	    }
	 }
      }
   }
}