/**************************************************************************/
/*                                                                        */
/*  Copyright (C) Jean-Christophe Filliatre                               */
/*                                                                        */
/*  This software is free software; you can redistribute it and/or        */
/*  modify it under the terms of the GNU General Public                   */
/*  License version 3.                                                    */
/*                                                                        */
/*  This software is distributed in the hope that it will be useful,      */
/*  but WITHOUT ANY WARRANTY; without even the implied warranty of        */
/*  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.                  */
/*                                                                        */
/**************************************************************************/

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

/* typedef unsigned long ulong; */

typedef struct s_grille {
        unsigned long int haut;
        unsigned long int bas;
        } grille;                 /* grille == position */

typedef struct s_point {
        unsigned char x;
        unsigned char y;
        } point;

grille pos[12][336];              /* tableau des positions */
grille pos_ok[12][336];           /* tableau des bonnes positions */

int nb_pos[12];
int nb_pos_ok[12];
int cur_pos[12];
int nb_sol;
char dummy[255];

/* declaration des fonctions */

void initialisation(void);
void affiche_position(grille);
void enregistre(int,ulong,ulong,ulong,ulong,ulong,int,int);
void essayer(int,grille);
void affiche_solution(int[],int);
void print_cur_pos(void);
int  verif_tableau(unsigned char t[8][8]);
int verif_grille(grille);
void affiche_tableau(unsigned char t[8][8]);
void positions_ok(grille);

/* pgm principal */

main()
{
        grille pos_i;

        pos_i.haut = 0X00002010UL;
        pos_i.bas  = 0X08040000UL;
	
        initialisation();               /* creation des positions */

        printf("\nGrille de depart :\n");
        affiche_position(pos_i);
        /* scanf("%s",dummy); */

        printf("Verification position initiale : ");
        if (verif_grille(pos_i)) printf("ok\n"); else printf("pas ok !\n");

        printf("Elimination des positions incorrectes...\n");
        positions_ok(pos_i);
        /* scanf("%s",dummy); */

        printf("Recherche des solutions...(Return)\n");

        essayer(0,pos_i);

        printf("\nNombre de solution : %d\n",nb_sol);
        /* scanf("%s",dummy); */

        return 0;
}

/* l'algorithme : un bon vieux backtracking ! */

void essayer(int n, grille u)
{
        int i;
        grille g;

        if (n<11) {
                /*
                printf("  la grille d'entree pour n=%d est :\n",n);
                affiche_position(u);
                printf("  et le test des aires est ");
                */
                if (verif_grille(u)==0) {
                        /* printf("test negatif !\n"); */
                        return ;
                }
        }
        if (n==12) {
                nb_sol++;
                affiche_solution(cur_pos,12);
                /* scanf("%s",dummy); */
        } else {
	  for(i=0; i<nb_pos_ok[n]; i++) {
	                /*
                        if (i % 30 == 0) {
                                print_cur_pos();
                        }
			*/
                        if (((u.haut & pos_ok[n][i].haut) | (u.bas & pos_ok[n][i].bas))==0) {
                                g.haut = u.haut | pos_ok[n][i].haut;
                                g.bas  = u.bas  | pos_ok[n][i].bas;
                                cur_pos[n] = i;
                                essayer(n+1,g);
                        }
                }
        }
}

/* ne conserve que les bonnes positions */
void positions_ok(grille pos_i)
{
        int i,j;
        grille g;

        for (i=0; i<12; i++) {
                nb_pos_ok[i] = 0;
                for (j=0; j<nb_pos[i]; j++) {
                        g.haut = pos[i][j].haut | pos_i.haut;
                        g.bas  = pos[i][j].bas  | pos_i.bas;
                        if (verif_grille(g)) {
                                pos_ok[i][nb_pos_ok[i]] = pos[i][j];
                                nb_pos_ok[i]++;
                        } else {
                                printf(".");
                        }
                }
        }
        printf("\n");
        for(i=0; i<12; i++)
                printf("nb pos. ok penta %2d : %4d \n",i,nb_pos_ok[i]);
}

/* verifie si un tableau a toutes ses zones vides connexes d'aire
 * multiple de 5.                                                 */

int verif_tableau(unsigned char t[8][8])
{
        unsigned char ip,i,j,s;
        point pile[64];
        point p;


        for (i=0; i<8; i++)
          for(j=0; j<8; j++)
            if (t[i][j]==0) {
                ip = 0; s = 1;
                t[i][j] = 1;
                ip++; pile[ip].x = i; pile[ip].y = j;
                while (ip > 0) {
                        p = pile[ip]; ip--;
                        if (p.x+1<8) if (t[p.x+1][p.y]==0) {
                                s++; ip++;
                                t[p.x+1][p.y] = 1;
                                pile[ip].x = p.x+1; pile[ip].y = p.y; } ;
                        if (p.y+1<8) if (t[p.x][p.y+1]==0) {
                                s++; ip++;
                                t[p.x][p.y+1] = 1;
                                pile[ip].x = p.x; pile[ip].y = p.y+1; } ;
                        if (p.x-1>=0) if (t[p.x-1][p.y]==0) {
                                s++; ip++;
                                t[p.x-1][p.y] = 1;
                                pile[ip].x = p.x-1; pile[ip].y = p.y; } ;
                        if (p.y-1>=0) if (t[p.x][p.y-1]==0) {
                                s++; ip++;
                                t[p.x][p.y-1] = 1;
                                pile[ip].x = p.x; pile[ip].y = p.y-1; } ;
                }
                if (s % 5 != 0)
                        return 0;
            } ;
        return 1;
}

/* verifie grille (en utilisant verif_tableau) */
int verif_grille(grille g)
{
        int i,j;
        unsigned char t[8][8];

        for(i=31; i>=0; i--) {
                t[i % 8][i / 8] = (g.haut & 1);
                g.haut >>= 1;
        }
        for(i=31; i>=0; i--) {
                t[i % 8][4+(i / 8)] = (g.bas & 1);
                g.bas >>= 1;
        }
        return verif_tableau(t);
}

/* affiche un tableau 8x8 */
void affiche_tableau(unsigned char t[8][8])
{
        unsigned char i,j;

        for(j=0; j<8; j++) {
          for(i=0; i<8; i++)
                printf("%2d",t[i][j]);
          printf("\n");
        }
}

/* affiche la position courante */
void print_cur_pos()
{
        int i;

        for (i=0; i<12; i++)
                printf("%3d ",cur_pos[i]);
        printf(" nb.sol.: %5d\n",nb_sol);
}

/* initialisation : creation des positions */

void initialisation()
{
        int i,j,dummy;

        printf("Initialisation...\n");
        for(i=0; i<12; i++) { nb_pos[i] = 0; };

        /* penta 0 */
        enregistre(0,128ul,128ul,128ul,128ul,128ul,8,4);
        enregistre(0,248ul,0ul,0ul,0ul,0ul,4,8);

        /* penta 1 */
        enregistre(1,192ul,128ul,192ul,0ul,0ul,7,6);
        enregistre(1,224ul,160ul,0ul,0ul,0ul,6,7);
        enregistre(1,192ul,64ul,192ul,0ul,0ul,7,6);
        enregistre(1,160ul,224ul,0ul,0ul,0ul,6,7);

        /* penta 2 */
        enregistre(2,64ul,224ul,64ul,0ul,0ul,6,6);

        /* penta 3; 
           les symétries du problème sont exploitées ici, manuellement */
        enregistre(3,128ul,192ul,192ul,0ul,0ul,7,6);
	if (0)
	  enregistre(3,224ul,192ul,0ul,0ul,0ul,6,7); /* rot 270 */
	if (0)
	  enregistre(3,192ul,192ul,64ul,0ul,0ul,7,6); /* rot 180 */
	if (0)
	  enregistre(3,96ul,224ul,0ul,0ul,0ul,6,7); /* rot 90 */
	if (1)
	  enregistre(3,64ul,192ul,192ul,0ul,0ul,7,6); /* sym V */
	if (0)
	  enregistre(3,192ul,224ul,0ul,0ul,0ul,6,7); /* sym D1 */
	if (0)
	  enregistre(3,192ul,192ul,128ul,0ul,0ul,7,6); /* sym H */
	if (0)
	  enregistre(3,224ul,96ul,0ul,0ul,0ul,6,7); /* sym D2 */

        /* penta 4 */
        enregistre(4,96ul,64ul,192ul,0ul,0ul,6,6);
        enregistre(4,128ul,224ul,32ul,0ul,0ul,6,6);
        enregistre(4,192ul,64ul,96ul,0ul,0ul,6,6);
        enregistre(4,32ul,224ul,128ul,0ul,0ul,6,6);

        /* penta 5 */
        enregistre(5,224ul,32ul,32ul,0ul,0ul,6,6);
        enregistre(5,32ul,32ul,224ul,0ul,0ul,6,6);
        enregistre(5,128ul,128ul,224ul,0ul,0ul,6,6);
        enregistre(5,224ul,128ul,128ul,0ul,0ul,6,6);

        /* penta 6 */
        enregistre(6,64ul,240ul,0ul,0ul,0ul,5,7);
        enregistre(6,128ul,192ul,128ul,128ul,0ul,7,5);
        enregistre(6,240ul,32ul,0ul,0ul,0ul,5,7);
        enregistre(6,64ul,64ul,192ul,64ul,0ul,7,5);
        enregistre(6,240ul,64ul,0ul,0ul,0ul,5,7);
        enregistre(6,64ul,192ul,64ul,64ul,0ul,7,5);
        enregistre(6,32ul,240ul,0ul,0ul,0ul,5,7);
        enregistre(6,128ul,128ul,192ul,128ul,0ul,7,5);

        /* penta 7 */
        enregistre(7,224ul,64ul,64ul,0ul,0ul,6,6);
        enregistre(7,32ul,224ul,32ul,0ul,0ul,6,6);
        enregistre(7,64ul,64ul,224ul,0ul,0ul,6,6);
        enregistre(7,128ul,224ul,128ul,0ul,0ul,6,6);

        /* penta 8 */
        enregistre(8,64ul,224ul,128ul,0ul,0ul,6,6);
        enregistre(8,192ul,96ul,64ul,0ul,0ul,6,6);
        enregistre(8,32ul,224ul,64ul,0ul,0ul,6,6);
        enregistre(8,64ul,192ul,96ul,0ul,0ul,6,6);
        enregistre(8,128ul,224ul,64ul,0ul,0ul,6,6);
        enregistre(8,96ul,192ul,64ul,0ul,0ul,6,6);
        enregistre(8,64ul,224ul,32ul,0ul,0ul,6,6);
        enregistre(8,64ul,96ul,192ul,0ul,0ul,6,6);

        /* penta 9 */
        enregistre(9,128ul,128ul,128ul,192ul,0ul,7,5);
        enregistre(9,240ul,128ul,0ul,0ul,0ul,5,7);
        enregistre(9,192ul,64ul,64ul,64ul,0ul,7,5);
        enregistre(9,16ul,240ul,0ul,0ul,0ul,5,7);
        enregistre(9,64ul,64ul,64ul,192ul,0ul,7,5);
        enregistre(9,128ul,240ul,0ul,0ul,0ul,5,7);
        enregistre(9,192ul,128ul,128ul,128ul,0ul,7,5);
        enregistre(9,240ul,16ul,0ul,0ul,0ul,5,7);

        /* penta 10 */
        enregistre(10,48ul,224ul,0ul,0ul,0ul,5,7);
        enregistre(10,128ul,128ul,192ul,64ul,0ul,7,5);
        enregistre(10,112ul,192ul,0ul,0ul,0ul,5,7);
        enregistre(10,128ul,192ul,64ul,64ul,0ul,7,5);
        enregistre(10,192ul,112ul,0ul,0ul,0ul,5,7);
        enregistre(10,64ul,192ul,128ul,128ul,0ul,7,5);
        enregistre(10,224ul,48ul,0ul,0ul,0ul,5,7);
        enregistre(10,64ul,64ul,192ul,128ul,0ul,7,5);

        /* penta 11 */
        enregistre(11,192ul,96ul,32ul,0ul,0ul,6,6);
        enregistre(11,32ul,96ul,192ul,0ul,0ul,6,6);
        enregistre(11,128ul,192ul,96ul,0ul,0ul,6,6);
        enregistre(11,96ul,192ul,128ul,0ul,0ul,6,6);

        for(i=0; i<12; i++)
                printf("nb pos. penta %2d : %4d \n",i,nb_pos[i]);

        /**** test des positions

        for(i=0; i<12; i++) {
                for(j=0; j<10; j++) {
                        affiche_position(pos[i][(rand()) % nb_pos[i]]);
                        scanf("%s",dummy);
                        printf("\n");
        } }
        ****/
}

/* affiche une position */

void affiche_position(grille g)
{
        int tab[2][32];
        int i,j;

        for(i=0; i<32; i++) {
                tab[0][31-i] = (g.haut & 1);
                g.haut >>= 1;
        }
        for(i=0; i<32; i++) {
                tab[1][31-i] = (g.bas & 1);
                g.bas >>= 1;
        }
        for(j=0; j<2; j++) {
        for(i=0; i<32; i++) {
                if (tab[j][i]) printf("M "); else printf(". ");
                if (i % 8 == 7) printf("\n");
        } }
}

/* enregistre un pentacube dans une orientation donnee */

void enregistre(int p, ulong x1, ulong x2, ulong x3, ulong x4, ulong x5, int maxi, int maxj)
{
        int i,j,k;
        unsigned long t[8],s[8];
        unsigned long h,b;

        t[0] = x1; t[1] = x2; t[2] = x3; t[3] = x4; t[4] = x5;
        t[5] = 0ul; t[6] = 0ul; t[7] = 0ul;
        for(j=0; j<maxj; j++) {
                for(k=0; k<8; k++) { s[k] = t[k]; };
                for(i=0; i<maxi; i++) {
                        h = (s[0] << (24-i)) | (s[1] << (16-i)) | (s[2] << (8-i)) | (s[3] >> i);
                        b = (s[4] << (24-i)) | (s[5] << (16-i)) | (s[6] << (8-i)) | (s[7] >> i);
                        pos[p][nb_pos[p]].haut = h;
                        pos[p][nb_pos[p]].bas = b;
                        nb_pos[p]++;
                }
                for(k=7; k>0; k--) { t[k] = t[k-1]; }; t[0] = 0ul;
        };
}

/* affiche une solution */

void affiche_solution(int s[12], int m)
{
        int i,j;
        char p;
        char tab[2][32];
        unsigned long u;

        for(j=0; j<2; j++)
                for(i=0; i<32; i++)
                        tab[j][i] = ' ';

        for(p=0; p<m; p++) {

        u = pos_ok[p][s[p]].haut;
        for(i=0; i<32; i++) {
                if (u & 1) {tab[0][31-i] = 65+p; };
                u >>= 1;
        }
        u = pos_ok[p][s[p]].bas;
        for(i=0; i<32; i++) {
                if (u & 1) {tab[1][31-i] = 65+p; };
                u >>= 1;
        }
        }

        for(j=0; j<2; j++) {
	  for(i=0; i<32; i++) {
	    printf("%c ",tab[j][i]);
	    if (i % 8 == 7) printf("\n");
	  }
	}
	printf("\n");
}