/*     QUADRI2.C     */
/*  par David Paven  */
/* ================= */

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <time.h>

/* Constantes */
/* ========== */
#define COTE       9    /* Côté du carré */
#define ALIGNE     3    /* Alignement maximum autorisé */
#define MASQUE     15   /* Pour vérifier l'alignement : 2^(ALIGNE+1) - 1 */
#define NBLIGNEMAX 512  /* Nombre maximum de lignes à générer */

/* Structure */
/* ========= */
struct sLigne
{
  int  count;
  int* first;
};

typedef struct sLigne tLigne;

/* Variables globales */
/* ================== */
int g_nDebutCB   = 18;  /* Nombre minimum de cases blanches */
int g_nFinCB     = 30;  /* Nombre maximum de cases blanches */

int g_nLigne     =  0;  /* Nombre de ligne */

long g_nNbCombin =  0;  /* Nombre de Combinaisons */

int*    g_pnGrille = NULL; /* Grille */
int*    g_pnListe  = NULL; /* Liste des lignes */
tLigne* g_psIndex  = NULL; /* Index de la liste */
int*    g_pnCombin = NULL; /* Combinaisons de cases blanches */

time_t g_begintime, g_starttime, g_endtime;

/* Prototypes */
/* ========== */
int C(int p_nN, int p_nP);
int initIndex(void);
int creationListe(void);
int compteCB(int p_nLigne);
int testLigne(int p_nLigne);
int recherche(int p_nCB);
int parcours(int p_nPos, int p_nCB);
int testGrilles(int p_nPos);
int testAddLigne(int p_nPos);
int afficheLigne(int p_nVal);
int affichageLignes(void);
int affichageGrille(void);


int main (int p_argc, char* p_argv[])
{
  int nCB = 0;

  if (p_argc > 2)
  {
    fprintf(stdout, "\nUsage : %s [<nombre_case_blanche>]\n", p_argv[0]);
    exit(1);
  }

  if (p_argc == 2)
  {
    /* Limite recherche au nombre de cases blanches donné en paramètre */
    g_nDebutCB = atoi(p_argv[1]);
    g_nFinCB = atoi(p_argv[1]);
  }

  fprintf(stdout, "\nRésolution du problème de quadrillage");
  fprintf(stdout, "\nCalcul en cours ... veuillez patienter\n");

  time(&g_begintime);

  g_starttime = g_begintime;

  /* Initialisation de la grille */
  g_pnGrille = (int*)malloc(COTE * sizeof(int));

  /* Initialisation de la liste des lignes */
  g_pnListe = (int*)malloc(NBLIGNEMAX * sizeof(int));

  /* Initialisation de l'index des lignes */
  initIndex();

  /* Initialisation de la combinaison de cases blanches */
  g_pnCombin = (int*)malloc(COTE * sizeof(int));

  fprintf(stdout, "\nGénération de la liste des lignes");

  /* Création de la liste des lignes */
  creationListe();

  fprintf(stdout, "\nGénération terminée\n");

  for(nCB = g_nDebutCB; nCB <= g_nFinCB; nCB++)
  {
    time(&g_endtime);

    fprintf(stdout, "\nRecherche avec %i cases blanches... Temps : %i\n", nCB, g_endtime - g_starttime);

    g_starttime = g_endtime;

    if (recherche(nCB) == 1)
    {
	/* Optimum trouvé, inutile de continuer */

      time(&g_endtime);

      fprintf(stdout, "\nTemps total écoulé : %i\n", g_endtime - g_begintime);

      exit(0);
    }
  }

  time(&g_endtime);

  fprintf(stdout, "\nTemps total écoulé : %i\n", g_endtime - g_begintime);

  return(0);
}

int C(int p_nN, int p_nP)
{
  if((p_nN == 0) || (p_nN == p_nP))
  {
    return 1;
  }
  else
  {
    return(C(p_nN-1, p_nP-1) + C(p_nN-1, p_nP));
  }
}

/* Initialisation de l'index sur les lignes */
int initIndex()
{
  int nCount = 0;
  int nDecal = 0;

  /* Initialisation de l'Index sur les lignes */
  g_psIndex = (tLigne*)malloc((COTE + 1) * sizeof(tLigne));

  /* Les décalages successifs sont les sommes des nombres maximums */
  /* de ligne dans chaque catégorie : C(n, p) avec n = COTE        */ 
  /* Soit : 0, 1, 10, 46, 130, 256, 382, 466, 502, 511             */

  for(nCount = 0; nCount <= COTE; nCount++)
  {
    g_psIndex[nCount].count = 0;
    
    if (nCount > 0)
    {
      nDecal += C(COTE, nCount - 1);
    }

    g_psIndex[nCount].first = g_pnListe + nDecal;
  }

  return(0);
}

/* Création de la liste des lignes */
int creationListe()
{
  int     nLigne  = 0;
  int     nCB     = 0;
  tLigne* psIndex = g_psIndex;

  /* On génère toutes les lignes possibles */
  for(nLigne = 0; nLigne < NBLIGNEMAX; nLigne++)
  {
    if (testLigne(nLigne) == 1)
    {
      nCB = compteCB(nLigne);

      *(psIndex[nCB].first + psIndex[nCB].count) = nLigne;
      psIndex[nCB].count += 1;

      g_nLigne += 1;
    }
  }

  return(0);
}

/* Compte les cases blanches d'une ligne */
int compteCB(int p_nLigne)
{
  int nTest  = 0;
  int nCumul = 0;

  for (nTest = 0; nTest < COTE; nTest++)
  {
    if ((p_nLigne & 1) == 0)
    {
      nCumul++;
    }

    p_nLigne /= 2;
  }

  return(nCumul);
}

/* Vérification qu'une ligne à générer respecte la règle */
int testLigne(int p_nLigne)
{
  int nTest;

  for (nTest = 1; nTest <= (COTE - ALIGNE); nTest++)
  {
    if ((p_nLigne & MASQUE) == MASQUE)
    {
      return(-1);
    }

    p_nLigne /= 2;
  }

  return(1);
}

/* Parcours et teste les répartitions de cases blanches */
/* possibles pour un nombre de cases blanches donné */
int recherche(int p_nCB)
{
  int nOK    = 0;
  int nLigne = 0;

  /* Au moins 2 blancs par lignes */
  if (p_nCB < (2 * COTE))
  {
    return(0);
  }

  /* Initialisation à 2 blancs par ligne */
  for(nLigne = 0; nLigne < COTE; nLigne++)
  {
     g_pnCombin[nLigne] = 2;
  }

  /* Enlève les cases blanches déjà allouées */
  p_nCB -= 2 * COTE;

  nOK = parcours(0, p_nCB);

  return(nOK);
}

/* Parcours des répartitions des cases blanches */
int parcours(int p_nPos, int p_nCB)
{
  int nCount  = 0;
  int nOK     = 0;
  int nOldVal = 0;
  int nMax    = 0;

  /* Si on a fini de répartir les CB ... */
  if(p_nCB == 0)
  {
    g_nNbCombin++;

    /* ... on teste les grilles possibles */
    nOK = testGrilles(0);

    return(nOK);
  }

  /* Si on est à la dernière ligne */
  if(p_nPos == (COTE - 1))
  {
    /* On met le reste des CB */
    g_pnCombin[p_nPos] += p_nCB;

    /* Si c'est possible ... */
    if(g_pnCombin[p_nPos] <= COTE)
    {
      g_nNbCombin++;

      /* ... on teste la répartition obtenue */
      nOK = testGrilles(0);
    }

    g_pnCombin[p_nPos] -= p_nCB;

    return(nOK);
  }

  /* Sauver valeur initiale de la combinaison */
  nOldVal = g_pnCombin[p_nPos];

  nMax = (p_nCB <= (COTE - nOldVal))?p_nCB:(COTE - nOldVal);

  /* On teste récursivement les différents remplissages */
  for(nCount = 0; nCount <= nMax; nCount++)
  {
    nOK = nOK | parcours(p_nPos + 1, p_nCB - nCount);

    g_pnCombin[p_nPos]++;
  }

  /* Restaurer valeur initiale de la combinaison */
  g_pnCombin[p_nPos] = nOldVal;

  return(nOK);
}

/* Parcours les différentes combinaisons de lignes associées */
/* à la répartition des cases blanches courante */
/* Affiche les solutions valables rencontrées */
int testGrilles(int p_nPos)
{
  int  nCount  = 0;
  int  nOK     = 0;
  int  nMax    = 0;
  int* pnFirst = NULL;

  nMax = g_psIndex[g_pnCombin[p_nPos]].count;
  pnFirst = g_psIndex[g_pnCombin[p_nPos]].first;

  /* On teste récursivement les différents remplissages */
  for(nCount = 0; nCount < nMax; nCount++)
  {
    g_pnGrille[p_nPos] = *(pnFirst + nCount);

    /* Si la ligne ajouté est correcte ... */
    if(testAddLigne(p_nPos) == 1)
    {
      /* ... soit on continue avec la ligne suivante ... */
      if(p_nPos < (COTE - 1))
      {
        nOK = nOK | testGrilles(p_nPos + 1);
      }
      /* ... soit on est au bout et on a trouvé une solution */
      else
      {
        nOK = 1;
        affichageGrille();
      }
    }
  }

  return(nOK);
}

/* Vérifie que l'ajout de la dernière ligne est correct */
int testAddLigne(int p_nPos)
{
  int nColonne = 0;
  int nLigne   = 0;
  int nCumul   = 0;

  /* Aucun contrôle pour les premières lignes */
  if(p_nPos >= ALIGNE)
  {
    /* Pour chaque case de la ligne */
    for(nColonne = 0; nColonne < COTE; nColonne++)
    {
      /* Si c'est une case noircie */
      if(((g_pnGrille[p_nPos] >> (COTE - 1 - nColonne)) & 1) == 1)
      {
        /* On teste l'alignement vertical */
        for(nLigne = 1, nCumul = 0; nLigne <= ALIGNE; nLigne++)
        {
          nCumul += ((g_pnGrille[p_nPos - nLigne] >> (COTE - 1 - nColonne)) & 1);
        }

        if(nCumul == ALIGNE)
        {
          return(0); /* Pas bon */
        }

        if(nColonne >= ALIGNE)
        {
          /* On teste la diagonale HG-BD */
          for(nLigne = 1, nCumul = 0; nLigne <= ALIGNE; nLigne++)
          {
            nCumul += ((g_pnGrille[p_nPos - nLigne] >> (COTE - 1 - nColonne + nLigne)) & 1);
          }

          if(nCumul == ALIGNE)
          {
            return(0); /* Pas bon */
          }
        }

        if((COTE - 1 - nColonne) >= ALIGNE)
        {
          /* On teste la diagonale BG-HD */
          for(nLigne = 1, nCumul = 0; nLigne <= ALIGNE; nLigne++)
          {
            nCumul += ((g_pnGrille[p_nPos - nLigne] >> (COTE - 1 - nColonne - nLigne)) & 1);
          }

          if(nCumul == ALIGNE)
          {
            return(0); /* Pas bon */
          }
        }
      }
    }
  }

  return(1);  /* C'est bon */
}


int afficheLigne(int p_nVal)
{
  int nColonne = 0;

  for (nColonne = 0; nColonne < COTE; nColonne++)
  {
    if(((p_nVal >> (COTE - 1 - nColonne)) & 1) == 0)
    {
      fprintf(stdout, ".");
    }
    else
    {
      fprintf(stdout, "X");
    }
  }
  fprintf(stdout, "\n");

  return(0);
}

int affichageLignes()
{
  int nCB    = 0;
  int nLigne = 0;

  fprintf(stdout, "\n");  
  
  for(nCB = 0; nCB <= COTE; nCB++)
  {
    fprintf(stdout, "\nCases blanches : %i ; Nombre de lignes : %i\n", nCB, g_psIndex[nCB].count);

    for(nLigne = 0; nLigne < g_psIndex[nCB].count; nLigne++)
    {
      afficheLigne(*(g_psIndex[nCB].first + nLigne));
    }
  }

  return(0);
}

int affichageGrille()
{
  int nCumul = 0;
  int nLigne = 0;

  /* Comptabilise le nombre de cases blanches */
  for(nLigne = 0; nLigne < COTE; nLigne++)
  {
    nCumul += g_pnCombin[nLigne];
  }

  fprintf(stdout, "\nSolution a %i cases noircies\n", COTE * COTE - nCumul);
  
  for(nLigne = 0; nLigne < COTE; nLigne++)
  {
    afficheLigne(g_pnGrille[nLigne]);
  }

  return(0);
}