//mingw32 sur W7 gcc 4.8.1
//gcc -Wall -Wextra -std=c99 -march=native -Ofast -flto -fomit-frame-pointer -pipe -o Solitaire.exe Solitaire.c && Solitaire.exe
#include <stdio.h>
#include <string.h>
#include <windows.h>
#define TRUE     1
#define FALSE    0
#define VIDE     0
#define BILLE    1
#define INTERDIT 2
//
#define USESYM 1 //Utilisation des symétries
#define INFINI 1 //Arrêt ou non dès qu'une solution est trouvée
//#define PRINT  0 //Ecritures ou non Résultats
//#define PRINTDEP 0//10000000000

unsigned long long DEPLACEMENTS=0; //Nombre total de déplacements
unsigned long long MULTDEP=0;      //Multiple de PRINTDEP déplacements
unsigned long long SOL1=0;         //Nombre de solutions avec le nb souhaité de billes restantes  et  la position finale souhaitée
unsigned long long SOL2=0;         //Nombre de solutions avec le nb souhaité de billes restantes sans la position finale souhaitée
unsigned long long SYMETRIES=0;    //Nombre de symétries

#define DIM       7           //Dimension du plateau de jeu depuis l'indice 1
#define DIMm1    (DIM   - 1)  //Dimension du plateau de jeu depuis l'indice 0
#define DIMdemi   4           //Demi Dimension du plateau de jeu depuis l'indice 1
#define DIMdemim1 (DIMdemi-1) //Demi Dimension du plateau de jeu depuis l'indice 0
#define BILLESWIN 1           //Nombre souhaité de billes restantes
#define LWIN     3            //Ligne   finale souhaitée (si 1 bille restante)
#define CWIN     3            //Colonne finale souhaitée (si 1 bille restante)

/*
// Solitaire Anglais
//40 861 647 040 079 968 Solutions
short  P[DIM][DIM]={ {2,2,1,1,1,2,2},
                     {2,2,1,1,1,2,2},
                     {1,1,1,1,1,1,1},
                     {1,1,1,0,1,1,1},
                     {1,1,1,1,1,1,1},
                     {2,2,1,1,1,2,2},
                     {2,2,1,1,1,2,2} };
*/

// Grande Pyramide
short  P[DIM][DIM]={ {2,2,0,0,0,2,2},
                     {2,2,0,1,0,2,2},
                     {0,0,1,1,1,0,0},
                     {0,1,1,1,1,1,0},
                     {1,1,1,1,1,1,1},
                     {2,2,0,0,0,2,2},
                     {2,2,0,0,0,2,2} };
/*
// Petit Diamant
short  P[DIM][DIM]={ {2,2,0,0,0,2,2},
                     {2,2,0,1,0,2,2},
                     {0,0,1,1,1,0,0},
                     {0,1,1,0,1,1,0},
                     {0,0,1,1,1,0,0},
                     {2,2,0,1,0,2,2},
                     {2,2,0,0,0,2,2} };

// Fire Place
short  P[DIM][DIM]={ {2,2,1,1,1,2,2},
                     {2,2,1,1,1,2,2},
                     {0,0,1,1,1,0,0},
                     {0,0,1,0,1,0,0},
                     {0,0,0,0,0,0,0},
                     {2,2,0,0,0,2,2},
                     {2,2,0,0,0,2,2} };

// Cross
short  P[DIM][DIM]={ {2,2,0,0,0,2,2},
                     {2,2,0,1,0,2,2},
                     {0,0,1,1,1,0,0},
                     {0,0,0,1,0,0,0},
                     {0,0,0,1,0,0,0},
                     {2,2,0,0,0,2,2},
                     {2,2,0,0,0,2,2} };


// Plus
short  P[DIM][DIM]={ {2,2,0,0,0,2,2},
                     {2,2,0,1,0,2,2},
                     {0,0,0,1,0,0,0},
                     {0,1,1,1,1,1,0},
                     {0,0,0,1,0,0,0},
                     {2,2,0,1,0,2,2},
                     {2,2,0,0,0,2,2} };
*/

//Affichage du plateau de jeu
void Draw(short billes) {
  int i=0,j=0;

  for (i=0;i<DIM;i++) {
    for (j=billes;j>1;j--) {printf("  ");}
    for (j=0;j<DIM;j++) {
      switch(P[i][j]) {
        case VIDE    : printf(" "); break;
        case BILLE   : printf("O"); break;
        case INTERDIT: printf("/"); break;
      }
    }
  if(!i) {printf(" %i",billes);}
    printf ("\n");
  }
}

//Jouer un plateau de jeu
short Jouer(short billes) {

  int i=0,j=0;
  int imax=DIM,jmax=DIM,jstart=0,jstop=DIM;
  int symv=0,symd1=0,symh=0,symd2=0;
  short gagnant=0;    //etat du coup courant
  short billes2=0;    //Nombre suivant de billes
  short balayees=0;   //Nombre de billes balayées

  // if(PRINTDEP) {
    // //Affichage du nombre courant de déplacement tous les PRINTDEP
    // if(DEPLACEMENTS>=PRINTDEP) {
      // DEPLACEMENTS=DEPLACEMENTS-PRINTDEP;
      // ++MULTDEP;
      // printf("%llu deplacements testes (%llu/%llu)\n",MULTDEP*PRINTDEP+DEPLACEMENTS,SOL1,SOL2);
      // fflush(stdout);
    // }
  // }
  
  //Recherche de Symétries
  if(0 || USESYM) {
    //Recherche d'une symétrie selon l'axe vertical
    symv=1;
    for(i=0;i<DIM;++i){
      for(j=0;j<DIMdemim1;++j){
        if(P[i][j]!=P[i][DIMm1-j]) {
          symv=0;
          break;
        }
      }
      if(!symv) break;
    }
    //Recherche d'une symétrie selon la diagonale NO
    symd1=1;
    for(i=0;i<DIMm1;++i){
      for(j=i+1;j<DIM;++j){
        if(P[i][j]!=P[j][i]) {
          symd1=0;
          break;
        }
      }
      if(!symd1) break;
    }
    //Recherche d'une symétrie selon l'axe horizontal
    symh=1;
    if(!(symv&&symd1)) {
      for(i=0;i<DIMdemim1;++i){
        for(j=0;j<DIM;++j){
          if(P[i][j]!=P[DIMm1-i][j]) {
            symh=0;
            break;
          }
        }
        if(!symh) break;
      }
    }
    //Recherche d'une symétrie selon la diagonale NE
    symd2=1;
    if(!(symv&&symd1)) {
      for(i=0;i<DIMm1;++i){
        for(j=0;j<(DIM-(i+1));++j){
          if(P[i][j]!=P[DIMm1-j][DIMm1-i]) {
            symd2=0;
            break;
          }
        }
        if(!symd2) break;
      }
    }
    //Recenssement des symétries
    SYMETRIES+=symv+symd1+symh+symd2;
    //Bornes du plateau à balayer
    if(symh || (symd1&&symd2)) imax=DIMdemi;
    if(symv)                   jmax=DIMdemi;jstop=jmax;
  }

  //Balayage plateau à DIM lignes DIM colonnes
  for (i=0;i<imax;++i) {
    //Bornes du plateau à balayer
    if(USESYM){
      if(symd1) jstart=i;
      if(symd2) jstop=min(DIM-i,jmax);
    }
    for (j=jstart;j<jstop;++j) {
      if(P[i][j]==BILLE) { //bille présente
        //Ouest
        if(j-2>-1  && !(symd1&&j==i) && P[i][j-1]==BILLE && P[i][j-2]==VIDE) {//Test déplacement à effectuer
          billes2=billes-1;
          ++DEPLACEMENTS;
          //Test si le coup est gagnant
          gagnant=0; 
          if(billes2==BILLESWIN) {
            gagnant=2;
            ++SOL2;
            if(BILLESWIN==1 && LWIN==i && CWIN==j-2) {
              gagnant=1;
              ++SOL1;
            } //fin position souhaitée
            // if(PRINT) {
              // printf("%llu/%llu solution(s) trouvee(s) a %llu deplacements\n",SOL1,SOL2,DEPLACEMENTS);
              // //Déplacement
              // P[i][j]=VIDE; P[i][j-1]=VIDE; P[i][j-2]=BILLE;
              // //affichage
              // Draw(billes2);
              // //Retour au plateau précédent
              // P[i][j]=BILLE;P[i][j-1]=BILLE;P[i][j-2]=VIDE;
            // }
          //coup non gagnant
          }else{
            //Déplacement
            P[i][j]=VIDE; P[i][j-1]=VIDE; P[i][j-2]=BILLE;
            //Nouveau plateau à jouer
            gagnant=Jouer(billes2);
            //affichage
            // if(PRINT && gagnant!=0) {Draw(billes2);}
            //Retour au plateau précédent
            P[i][j]=BILLE;P[i][j-1]=BILLE;P[i][j-2]=VIDE;
          }
          if(!INFINI&&gagnant==1) {return(gagnant);} //arrêt de la recherche
        } //fin Ouest
        //Sud
        if(i+2<DIM && !((symd1&&j==i)||(symh&&i==DIMdemim1)||(symd2&&j==DIMm1-i)) && P[i+1][j]==BILLE && P[i+2][j]==VIDE) {//Test déplacement à effectuer
          billes2=billes-1;
          ++DEPLACEMENTS;
          //Test si le coup est gagnant
          gagnant=0;
          if(billes2==BILLESWIN) {
            gagnant=2;
            ++SOL2;
            if(BILLESWIN==1 && LWIN==i+2 && CWIN==j) {
            gagnant=1;
            ++SOL1;
            } //fin position souhaitée
            // if(PRINT) {
              // printf("%llu/%llu solution(s) trouvee(s) a %llu deplacements\n",SOL1,SOL2,DEPLACEMENTS);
              // //Déplacement
              // P[i][j]=VIDE; P[i+1][j]=VIDE; P[i+2][j]=BILLE;
              // //affichage
              // Draw(billes2);
              // //Retour au plateau précédent
              // P[i][j]=BILLE;P[i+1][j]=BILLE;P[i+2][j]=VIDE;
            // }
          //coup non gagnant
          }else{
            //Déplacement
            P[i][j]=VIDE; P[i+1][j]=VIDE; P[i+2][j]=BILLE;
            //Nouveau plateau à jouer
            gagnant=Jouer(billes2);
            //affichage
            // if(PRINT && gagnant!=0) {Draw(billes2);}
            //Retour au plateau précédent
            P[i][j]=BILLE;P[i+1][j]=BILLE;P[i+2][j]=VIDE;
          }
          if(!INFINI&&gagnant==1) {return(gagnant);} //arrêt de la recherche
        } //fin Sud
        //Est
        if(j+2<DIM && !((symv&&j==DIMdemim1)||(symd2&&j==DIMm1-i)) && P[i][j+1]==BILLE && P[i][j+2]==VIDE) {//Test déplacement à effectuer
          billes2=billes-1;
          ++DEPLACEMENTS;
          //Test si le coup est gagnant
          gagnant=0;
          if(billes2==BILLESWIN) {
            gagnant=2;
            ++SOL2;
            if(BILLESWIN==1 && LWIN==i && CWIN==j+2) {
              gagnant=1;
              ++SOL1;
            } //fin position souhaitée
            // if(PRINT) {
              // printf("%llu/%llu solution(s) trouvee(s) a %llu deplacements\n",SOL1,SOL2,DEPLACEMENTS);
              // //Déplacement
              // P[i][j]=VIDE; P[i][j+1]=VIDE; P[i][j+2]=BILLE;
              // //affichage
              // Draw(billes2);
              // //Retour au plateau précédent
              // P[i][j]=BILLE;P[i][j+1]=BILLE;P[i][j+2]=VIDE;
            // }
          //coup non gagnant
          }else{
            //Déplacement
            P[i][j]=VIDE; P[i][j+1]=VIDE; P[i][j+2]=BILLE;
            //Nouveau plateau à jouer
            gagnant=Jouer(billes2);
            //affichage
            // if(PRINT && gagnant!=0) {Draw(billes2);}
            //Retour au plateau précédent
            P[i][j]=BILLE;P[i][j+1]=BILLE;P[i][j+2]=VIDE;
          }
          if(!INFINI&&gagnant==1) {return(gagnant);} //arrêt de la recherche
        } //fin Est
        //Nord
        if(i-2>-1  && P[i-1][j]==BILLE && P[i-2][j]==VIDE) {//Test déplacement à effectuer
          billes2=billes-1;
          ++DEPLACEMENTS;
          //Test si le coup est gagnant
          gagnant=0;
          if(billes2==BILLESWIN) {
            gagnant=2;
            ++SOL2;
            if(BILLESWIN==1 && LWIN==i-2 && CWIN==j) {
              gagnant=1;
              ++SOL1;
            } //fin position souhaitée
            // if(PRINT) {
               // printf("%llu/%llu solution(s) trouvee(s) a %llu deplacements\n",SOL1,SOL2,DEPLACEMENTS);
              // //Déplacement
              // P[i][j]=VIDE; P[i-1][j]=VIDE; P[i-2][j]=BILLE;
              // //affichage
              // Draw(billes2);
              // // c=getchar();
              // //Retour au plateau précédent
              // P[i][j]=BILLE;P[i-1][j]=BILLE;P[i-2][j]=VIDE;
            // }
          //coup non gagnant
          }else{
            //Déplacement
            P[i][j]=VIDE; P[i-1][j]=VIDE; P[i-2][j]=BILLE;
            //Nouveau plateau à jouer
            gagnant=Jouer(billes2);
            //affichage
            // if(PRINT && gagnant!=0) {Draw(billes2);}
            //Retour au plateau précédent
            P[i][j]=BILLE;P[i-1][j]=BILLE;P[i-2][j]=VIDE;
          }
          if(!INFINI&&gagnant==1) {return(gagnant);} //arrêt de la recherche
        } //fin Nord
        ++balayees;
        if(balayees==billes) {return(gagnant);} //arrêt anticipé du balayage s'il ne reste plus de billes à balayer
      } //fin bille
    } //fin lignes
  } //fin colonnes
return(gagnant);
}//fin Jouer

//Routine principale
//int main(int argc, char *argv[]) {
int main() {
  int i=0,j=0;
  short billes=0; //Nombre courant de billes
  short gagnant=0; //etat du coup courant
  SYSTEMTIME str_t;
  LARGE_INTEGER freq, time1,time2;
  double time;

  //Calcul nb de billes
  for (i=0;i<DIM;i++) {
    for (j=0;j<DIM;j++) {
      if(P[i][j]==BILLE) {billes++;}
    }
  }

  GetSystemTime(&str_t);
  printf("Le %2d-%2d-%4d %c %dh%d   \n",str_t.wDay,str_t.wMonth,str_t.wYear,133,(str_t.wHour+2),str_t.wMinute); //Affichage de l'heure courante
  printf("Resolution du plateau suivant avec %i billes\n",billes);
  if(BILLESWIN==1) {printf("Pour %i bille restante en %i,%i\n",BILLESWIN,LWIN,CWIN); }
  else             {printf("Pour %i billes restantes\n"       ,BILLESWIN);           }
  Draw(1); //Affichage du plateau de jeu
  fflush(stdout);

  QueryPerformanceFrequency(&freq);
  QueryPerformanceCounter(&time1);
  //Résolution
  gagnant=Jouer(billes);
  QueryPerformanceCounter(&time2);
  time = (double) (time2.QuadPart - time1.QuadPart) / (double)(freq.QuadPart);
  //Calcul du nombre de déplacements
  //if(PRINTDEP) {DEPLACEMENTS=MULTDEP*PRINTDEP+DEPLACEMENTS;}


  if(SOL2==0) {printf("Aucune solution trouvee\n");}
  else{
    //if(PRINT) {Draw(billes);}
    printf("%llu/%llu solution(s) trouvee(s)\n",SOL1,SOL2);
  }
  printf("%llu deplacements analyses en %f s (%e par s)\n",DEPLACEMENTS,time,(double) DEPLACEMENTS/time);

return 0;
}