/* pent.c -- find pentomino solutions */

/* Copyright (C) 2002 Grant P. Maizels, Sydney, Australia. */
/* All Rights Reserved. */

#include <stdio.h>

/* Board */
typedef unsigned long long ull;
int x, y;              /* Board Dimensions */
ull brd;         /* board 64bit */
ull tries;       /* move count */
int found;
int pp;                /* pieces placed */
int por[12];           /* piece orientaion */

char *let;             /* letter representation */

/* Valid Moves on Board */
ull vmap[12][60*8]; /* only first vmcnt[i] of each vmap[i] are used */
int vmcnt[12];         /* Count of valid maps for piece */
int drops[12];         /* Count of maps dropped for symetry */
int dropv[12];         /* Count of maps dropeed for voids with spaces not a
                             multiple of 5 */
int bit();
ull mirrorh();
ull mirrorv();
void trymap();

/* 5x5 Representations of pieces */
long pm[12];           /* piece map */
long opm[12][8];       /* oriented piece map */
char vopm[12];         /* valid oriented piece map */
long rot90(), rev();
int bit_25();

void prnt_status();
void show_map();
void show_vmap();

main(argc, argv)
int argc;
char **argv;
{
   char *optim = "";
   if(argc <= 1)
      x = 10;
   else
      x = atoi(argv[1]);
   if(x < 3 || x > 20 || 60%x != 0) {
      fprintf(stderr, "BAD x value %d\n", x);
      exit(1);
   }

#ifdef CHKVD
   optim = " optim = CHKVD";
#endif
   printf("%s: %d x %d%s\n\n", argv[0], x, 60/x, optim);
   init();
   prnt_status();
   game();
}

game(){
   brd = 0;
   pp = 0;
   move(0);
   printf("DONE %d found %ld tries\n", found, tries);
}

move(x)
int x;
{
   ull sve;
   int i;

   if(pp == 12) {
      show_map();
      return;
   }
   for(i=0; i<vmcnt[x]; i++) {
      tries++;
      sve = brd;
      if((brd&vmap[x][i]) == 0) {
         brd |= vmap[x][i];
#ifdef CHKVD
         if(! badvoid(brd)) {
#else
         if(1) {
#endif
	    por[x] = i;
	    pp++;
            if(pp == 12)
               found++;
	    move(x+1);
	    pp--;
         } 
      }
      brd = sve;
   }
}

init(){
   int i, j, k, v;

   y = 60 / x;
   let = "XIUVTLZYNPWF";
   pm[0] = 0x00023880;
   pm[1] = 0x00007C00;
   pm[2] = 0x00053800;
   pm[3] = 0x00001C84;
   pm[4] = 0x00071080;
   pm[5] = 0x0000BC00;
   pm[6] = 0x000610C0;
   pm[7] = 0x00023C00;
   pm[8] = 0x00061C00;
   pm[9] = 0x00063800;
   pm[10] = 0x000430C0;
   pm[11] = 0x00043880;

   for(i=0;i<12;i++) {
      opm[i][0] = pm[i];
      opm[i][1] = rot90(opm[i][0]);
      opm[i][2] = rot90(opm[i][1]);
      opm[i][3] = rot90(opm[i][2]);
      opm[i][4] = rev(opm[i][0]);
      opm[i][5] = rev(opm[i][1]);
      opm[i][6] = rev(opm[i][2]);
      opm[i][7] = rev(opm[i][3]);
      vopm[i]=1; /* first always valid and would fail test below */
      for(j=1;j<8;j++) {
         v = 1;
         for(k=0;k<j;k++)
	    if(opm[i][j] == opm[i][k])
               v = 0;
         vopm[i] |= (v<<j);
      }
   }
   for(i=0;i<12;i++)
      vmcnt[i] = 0;
   for(i=0;i<12;i++)
      for(j=0;j<60;j++)
         for(k=0;k<8;k++)
            if(vopm[i]&(1<<k))
               trymap(i, k, j);
}

/* board valid positions - not optimised */

int bit(p, v)
int p;
ull v;
{
   return (v&(((ull)1)<<p))?1:0;
}

void trymap(pce, orient, m)
int pce; /* piece number 0 - 11 */
int m; /* location on board 0 - 59 */
{
   ull map = 0;
   int i, mx, my, px, py, mpx, mpy, b;
   mx = m % x;
   my = m / x;
   for(px=0; px<5; px++)
      for(py=0; py<5; py++) {
         b = bit_25(px+py*5, opm[pce][orient]);
         mpx = mx - 2 + px;
         mpy = my - 2 + py;
         if (b == 1 && (mpx < 0 || mpx >= x || mpy < 0 || mpy >= y)) {
            return;
         }
         if (b == 1)
            map |= ((ull)1)<<(mpx+mpy*x);
      }
   /* Symetry check for piece 0 only */
   if(pce == 0) {
      for(i=0; i<vmcnt[pce]; i++)
         if ((mirrorh(map) == vmap[pce][i]) ||
             (mirrorh(mirrorv(map)) == vmap[pce][i]) ||
             (mirrorv(map) == vmap[pce][i])) {
            drops[pce]++;
            return;
         }
   }
   /* Void check each void should have a multiple of 5 squares */
   if(badvoid(map)) {
      dropv[pce]++;
      return;
   }
   vmap[pce][vmcnt[pce]++] = map;
}

/* badvoid - look for groups of joining clear squares 
   with a count not divisable by 5 */
int badvoid(m)
ull m;
{
   ull vm; /* void map - all found viods */
   ull fm; /* current found void map */
   int i;

   vm = 0;
   fm = 0;
   for(i=0;i<60;i++) {
      if(bit(i, m)==0&&bit(i, vm)==0) {
         fm = 0;
         chkpos(i, &fm, &m, 0, ".");
      }
      if(bitcnt(fm)%5 !=0) {
         return 1;
      } 
      vm |= fm;
   }
   return 0;
}

chkpos(i, mp, vmp, z, p)
int i;
ull *mp;
ull *vmp;
int z;
char *p;
{
   *mp |= ((ull)1)<<i;
   /* process up */
   if(i-x >= 0 && bit(i-x,*mp)==0&&bit(i-x,*vmp)==0)
      chkpos(i-x, mp, vmp, z+1, "^");
   /* process left */
   if(i%x>0 && bit(i-1,*mp)==0&&bit(i-1,*vmp)==0)
      chkpos(i-1, mp, vmp, z+1, "<");
   /* process right */
   if((i+1)%x>0 && bit(i+1,*mp)==0&&bit(i+1,*vmp)==0)
      chkpos(i+1, mp, vmp, z+1, ">");
   /* process down */
   if(i+x < 60 && bit(i+x,*mp)==0&&bit(i+x,*vmp)==0)
      chkpos(i+x, mp, vmp, z+1, "v");
}

int bitcnt(m)
ull m;
{
  int c = 0;
  ull u;
  u = (ull) m;
  for(c=0; u!=0; u>>=((ull)1))
    if(u&((ull)1))
       c++;
  return c;
}

ull mirrorv(m)
ull m;
{
   ull r = 0;
   int j;

   for(j=0;j<60;j++) {
      if(bit((j/x)*x+x-1-j%x, m))
        r = r|(((ull)1)<<j);
   }
   return r;
}

ull mirrorh(m)
ull m;
{
   ull r = 0;
   int j;

   for(j=0;j<60;j++) {
      if(bit((y-1-j/x)*x+j%x, m))
        r = r|(((ull)1)<<j);
   }
   return r;
}

/* piece map manipulation not optimised */

long rot90(p)
long p;
{
   long r = 0;
   int j;

   for(j=0;j<25;j++) {
      if(bit_25(j/5+(4-j%5)*5, p))
        r = r|(1<<j);
   }
   return r;
}

long rev(p)
long p;
{
   long r = 0;
   int j;

   for(j=0;j<25;j++) {
      if(bit_25((j/5)*5+4-j%5, p))
        r = r|(1<<j);
   }
   return r;
}

int bit_25(p, v)
int p;
long v;
{
   return (v&(1<<p))?1:0;
}

/* output */

void prnt_status()
{
   int i, j, k;
   printf("pent: x = %d, y = %d\n", x, y);
  
   /* Print all valid orientations of pentominoes */ 
   for(i=0;i<12;i++) {
      printf("\nPentomino %d %c (%d Valid moves) Drops (%ds, %dv)\n",
         i, let[i], vmcnt[i], drops[i], dropv[i]);
      for(k=0;k<8;k++) {
         if(vopm[i]&(1<<k)) {
            if((opm[i][k] & 1<<12) != 1<<12) /* Middle pixel not set */
               printf("BAD BAD Pentomino. Middle pixel not set!\n");
	    for(j=0;j<25;j++) {
	       if(j%5 == 0)
		  printf("\n");
	       printf("%c", (bit_25(j, opm[i][k]))?let[i]:' ');
	    }
	    printf("\n");
	 }
      }
   }
   
   for(i=0;i<12;i++)
      for(j=0;j<vmcnt[i];j++) {
         printf("\nValid Board %d for piece %d %c",
            j, i, let[i]);
         show_vmap(vmap[i][j]);
      }
}

void show_vmap(m)
ull m;
{
   int j;

   for(j=0;j<60;j++) {
      if(j%x == 0)
	 printf("\n");
      printf("%c", (bit(j, m))?'O':'.');
   }
   printf("\n");
}

void show_map()
{
   int i, j;
   char l[20][21];
   for(i=0; i<y; i++) {
      for(j=0; j<x; j++)
         l[i][j] = ' ';
      l[i][x] = '\0';
   }
      
   for(i=0; i<pp; i++) {
      for(j=0;j<60;j++)
         if(bit(j, vmap[i][por[i]]))
           l[j/x][j%x] = let[i];
   } 
   printf("\nFOUND %d\n", found);
   for(i=0; i<y; i++)
      printf("%s\n", l[i]);
}