/**********************************************************************/
/*    DAVID-P.C      ( OPTIMISONS LES PETIS CARRES VIRUS N°11 page 6 )*/
/*--------------------------------------------------------------------*/
/*    Fonction       : Etude de remplissage  d'un carré de 9x9        */
/*                     avec 3 carrés maxi noircis de suite en         */
/*                     ligne, colonne, et diagonales                  */
/*--------------------------------------------------------------------*/
/*    Auteurs        : LUCIEN BEAULIEU                                */
/*    (BORLAND TURBO C)                                               */
/*    dernière modif.: Wed  06/01/99 15:00:37                         */
/**********************************************************************/

/*== Intégrer fichiers Include =======================================*/
#include <stdlib.h>
#include <stdio.h>
#include <string.h>

/*== Typedefs ========================================================*/

/*== Prototypes ======================================================*/
void choix1(int ligne0);
void choixsol(int numligne);
int  okligne(int ligne);
int  OKoblik(int ligne);
void affichesol(void);
void affRetenu(void);
int  compteX(void);
void RazLigne(void);

int setlignes(void);
/*== Constantes ======================================================*/

/*== Variables globales ==============================================*/
int  maxchoix=0, choix0=0, choixfin=0;
char choixligne[72][10], RAZ[10]="         ";

char solution[9][10]  ={"         ", "         ", "         ",
                        "         ", "         ", "         ",
                        "         ", "         ", "         "};
int nbsol=0, minsol=81, nbX;
int retenu[9]={99,99,99,99,99,99,99,99,99};

/**********************************************************************/
/**                       PROGRAMME PRINCIPAL                        **/
/**********************************************************************/

void main(int argc, char *argv[])
{ int param;

  printf("Noircir un carré de 9x9 avec 3 maxi de suite (L.BEAULIEU 6/1/1999)\n");
  setlignes();
  if (argc)
   { param=atoi(argv[1]);
     if (param>0)
        { if (param<maxchoix)
             choix0=param;
        }
     if (argc>2)
        { param=atoi(argv[2]);
          if (param>0)
             { if (param<maxchoix)
                  choixfin=param;
             }
        }
   }

  choix1(choix0); RazLigne();
  printf("Solution maximum à %i cases noircies\n",81-minsol);
}

/*--------------------------------------------------------------------*/
/*  Procedure d'entrée qui choisit la première ligne et appelle suiv. */
/*--------------------------------------------------------------------*/
void choix1(int ligne0) /* numero ligne 0 */
{ int ligne, i;

   for (ligne=ligne0;ligne<choixfin+1;ligne++)
    { strcpy(solution[0], choixligne[ligne]);
      retenu[0]=ligne;
      for (i=0, fprintf(stderr,"En cours: ["); i<9; i++)
          fprintf(stderr,"%2i,",retenu[i]); fprintf(stderr,"]");
      fprintf(stderr," (%i sol. maxi:%i X)",nbsol,81-minsol);
      fprintf(stderr,"   \r");
      choixsol(1); /* recursion ligne suivante */
    }
   strcpy(solution[0], RAZ); /* ligne vide */
   retenu[0]=99;
}

/*--------------------------------------------------------------------*/
/*  Procedure recursive qui choisit une ligne                         */
/*--------------------------------------------------------------------*/
void choixsol(int numligne) /* numero nouvelle ligne */
{ int ligne, i;

   for (ligne=0;ligne<maxchoix;ligne++)
    { strcpy(solution[numligne], choixligne[ligne]);
      retenu[numligne]=ligne;
      for (i=0, fprintf(stderr,"En cours: ["); i<9; i++)
          fprintf(stderr,"%2i,",retenu[i]); fprintf(stderr,"]");
      fprintf(stderr," (%i sol. maxi:%i X)",nbsol,81-minsol);
      fprintf(stderr,"   \r");
      if ( okligne(numligne) && OKoblik(numligne) )
         {
           if (numligne==8) /* fini ! */
              {
                nbX=compteX();
                if (nbX<=minsol)
                  { nbsol++; affichesol();
                    if (nbsol>19) exit(1);
                  }

              }
           else
              choixsol(numligne+1); /* recursion ligne suivante */
         }
    }
   strcpy(solution[numligne], RAZ); /* ligne vide */
   retenu[numligne]=99;
}

/*--------------------------------------------------------------------*/
/*  Procedure qui vérifie les obliques                                */
/*--------------------------------------------------------------------*/
int OKoblik(int ligne)  /* de 0 jusqu'a 'ligne' maxi incluse */
{ int i, echec, nb, diag;
  if (ligne<3) return 1;
  /* verifie la première direction de diagonale */
  /* verifie le 1er triangle */
  for (diag=0; diag <=ligne; diag++ )
    { for (i=nb=echec=0; diag+i<=ligne ; i++)
          if (solution[diag+i][i]=='¦')
             { if (++nb>3) { echec=1; break; }
             }
          else nb=0;
      if (echec) return 0;
    }
  /* verifie le parallelo */
  for (diag=0; diag+ligne <9; diag++ )
    { for (i=nb=echec=0; i<=ligne ; i++)
          if (solution[i][diag+i]=='¦')
             { if (++nb>3) { echec=1; break; }
             }
          else nb=0;
      if (echec) return 0;
    }
  /* verifie le 2eme triangle */
  for (diag=9-ligne; diag <9; diag++ )
    { for (i=nb=echec=0; diag+i<9 ; i++)
          if (solution[i][diag+i]=='¦')
             { if (++nb>3) { echec=1; break; }
             }
          else nb=0;
      if (echec) return 0;
    }

  /* verifie la deuxième direction de diagonale */
  /* verifie le 1er triangle */
  for (diag=0; diag <=ligne; diag++ )
    { for (i=nb=echec=0; i<=diag; i++)
          if (solution[diag-i][i]=='¦')
             { if (++nb>3) { echec=1; break; }
             }
          else nb=0;
      if (echec) return 0;
    }
  /* verifie le parallelo */
  for (diag=0; diag+ligne <9; diag++ )
    { for (i=nb=echec=0; i<=ligne ; i++)
          if (solution[i][diag-i]=='¦')
             { if (++nb>3) { echec=1; break; }
             }
          else nb=0;
      if (echec) return 0;
    }
  /* verifie le 2eme triangle */
  for (diag=9-ligne; diag <9; diag++ )
    { for (i=nb=echec=0; diag+i<9 ; i++)
          if (solution[ligne-i][diag+i]=='¦')
             { if (++nb>3) { echec=1; break; }
             }
          else nb=0;
      if (echec) return 0;
    }

 return 1;
}

/*--------------------------------------------------------------------*/
/*  Procedure qui vérifie les lignes choisies                         */
/*--------------------------------------------------------------------*/
int okligne(int ligne)
{ int colonne, i, nb;
  for (colonne=0; colonne<9; colonne++)
    { /* Le début des colonnes a-t-il la condition 3 cases ? */
      for (i=0, nb=0; i<=ligne; i++)
          if (solution[i][colonne]=='¦')
             { if (++nb>3) return 0; }
          else
             nb=0;
    }
 return 1;
}

/*--------------------------------------------------------------------*/
/*  Affiche le rectangle solution                                     */
/*--------------------------------------------------------------------*/
void affRetenu(void)
{ int i;
  for (i=0, printf("Solution: ["); i<9; i++)
      { printf("%2i",retenu[i]);
        if (i<8) printf(",");
      }
  printf("]\n");
}

/*--------------------------------------------------------------------*/
/*  Affiche le rectangle solution                                     */
/*--------------------------------------------------------------------*/
void RazLigne(void)
{ printf("\r                                                          \r");
}

/*--------------------------------------------------------------------*/
/*  Affiche le rectangle solution                                     */
/*--------------------------------------------------------------------*/
void affichesol(void)
{ int ligne, colonne;
  char car;
  RazLigne();
  printf("\n=============== SOLUTION n°%i\n",nbsol);
  printf("+-----------------------------------+\n");
  for (ligne=0;ligne<9;ligne++)
      { for (colonne=0, printf("¦"); colonne<9 ; colonne++)
            { car=solution[ligne][colonne];
              if (car=='X') car=' ';
              printf(" %c ¦",car);
            } printf("\n");
        if (ligne<9-1)
           printf("+---+---+---+---+---+---+---+---+---¦\n");
      }
  printf("+-----------------------------------+\n");
  printf("Il y a %i cases '¦' (maxi en cours à %i cases)\n",81-nbX, 81-minsol);
  printf("=====================================\n");
}

/*--------------------------------------------------------------------*/
/*  Compte les X de la solution                                       */
/*--------------------------------------------------------------------*/
int compteX(void)
{ int nb=0, ligne, colonne;
  for (ligne=0;ligne<9;ligne++)
    for (colonne=0; colonne<9; colonne++)
      if (solution[ligne][colonne]=='X') nb++;
  if (nb<minsol) minsol=nb;
  return nb;
}

/*--------------------------------------------------------------------*/
/*  Procedure de construction des lignes à choisir                    */
/*--------------------------------------------------------------------*/
int setlignes(void)
{ int choix1, choix2, choix3, nbcar, i, ok;
  char ligne[10], vide[10]="¦¦¦¦¦¦¦¦¦";

  /* Construction des lignes à 2 'X' */
  for (choix1=0; choix1<8; choix1++)
      for (choix2=choix1+1;choix2<9;choix2++)
          { strcpy(ligne,vide); ligne[choix1]='X'; ligne[choix2]='X';
            /* verification de la ligne construite */
            for (i=0, nbcar=0, ok=1; i<9; i++)
                { if (ligne[i]=='¦')
                     { if (++nbcar>3) { ok=0; break; }
                     }
                  else
                     nbcar=0;
                }
            if (ok)
               { strcpy(choixligne[maxchoix++],ligne);
                 /* printf("Ligne [%i]= '%s'\n",maxchoix-1,ligne); */
               }
          }
  /* Construction des lignes à 3 'X' */
  for (choix1=0; choix1<7; choix1++)
    for (choix2=choix1+1;choix2<8;choix2++)
      for (choix3=choix2+1;choix3<9;choix3++)
          { strcpy(ligne,vide);
            ligne[choix1]='X'; ligne[choix2]='X';  ligne[choix3]='X';
            /* verification de la ligne construite */
            for (i=0, nbcar=0, ok=1; i<9; i++)
                { if (ligne[i]=='¦')
                     { if (++nbcar>3) { ok=0; break; }
                     }
                  else
                     nbcar=0;
                }
            if (ok)
               { strcpy(choixligne[maxchoix++],ligne);
                 /* printf("Ligne [%i]= '%s'\n",maxchoix-1,ligne); */
               }
          }
  choixfin=maxchoix;
 return maxchoix;
}