#include <signal.h>                 /***  first Version:   July 1988    ***/
#include <stdio.h>                  /***  Author:  Achim Flammenkamp    ***/
#include <sys/times.h>              /***  last Version:    19.11.91     ***/
#include <time.h>                   /***   modified:         2.5.96     ***/
#include <unistd.h>
#define   PKT    6
#define   MAX    16
#define   STONE  (MAX*MAX-MAX)
#define   BLOCK  (STONE/2)
#ifndef  PROTO
#define   PROTO   "proto"
#endif
#ifndef  FIXPKT
#define   FIXPKT  "wache"
#endif
#define   TEXP    6    /**  4*TEXP + Log2(MANZ+1) <= 8*sizeof unsigned  **/
#define   MASK    ((1<<(2*TEXP))-1)
#define   SHIFT   (32-2*TEXP)
#define   MANZ    ((1<<8)-1)


#define   block_a_line(x1,y1)                                         \
          zei[x1]++;  spa[y1]++;                                      \
          frei_zei[x1]--;    frei_spa[y1]--;                          \
          start = &array[x1][y1][0][0];                               \
          for(l=0;l<anz;l++)                                          \
          {  index=start+elel[l];                                     \
             if ( !(m= *index>>(2*TEXP) &MANZ) )  continue;           \
             else if (m==1)                                           \
             {  addr = &matrix[0][0] + (kk= *index&MASK);             \
                if (!((*addr)++))                                     \
                {  (*frei_addrx[kk])--;                               \
                   (*frei_addry[kk])--;                               \
                }                                                     \
             }                                                        \
             else                                                     \
             {  h = *index>>SHIFT;                                    \
                for(addr = &matrix[0][0]+(*index&MASK); m--; addr+=h) \
                   if (!((*addr)++))                                  \
                   {  kk = addr - &matrix[0][0];                      \
                      (*frei_addrx[kk])--;                            \
                      (*frei_addry[kk])--;                            \
                   }                                                  \
             }                                                        \
          }                                                           \
          elel[anz]= MAX*(x1)+(y1);   anz++;

#define   unblock_a_line(x1,y1)                                       \
          anz--;   zei[x1]--;   spa[y1]--;                            \
          start = &array[x1][y1][0][0];                               \
          for(l=0;l<anz;l++)                                          \
          {  index=start+elel[l];                                     \
             if ( !(m= *index>>(2*TEXP) &MANZ) )  continue;           \
             else if (m==1)                                           \
             {  addr = &matrix[0][0] + (kk= *index&MASK);             \
                if (!(--(*addr)))                                     \
                {  (*frei_addrx[kk])++;                               \
                   (*frei_addry[kk])++;                               \
                }                                                     \
             }                                                        \
             else                                                     \
             {  h = *index>>SHIFT;                                    \
                for(addr = &matrix[0][0]+(*index&MASK); m--; addr+=h) \
                   if (!(--(*addr)))                                  \
                   {  kk = addr - &matrix[0][0];                      \
                      (*frei_addrx[kk])++;                            \
                      (*frei_addry[kk])++;                            \
                   }                                                  \
             }                                                        \
          }                                                           \
          matrix[x1][y1] -= BLOCK;                                    \
          *(stpt++) = &matrix[x1][y1];


/****
   matrix is das grid   das die blockierungszahl an jeder position hat
array is ein MAX^4 feld und hat f"ur jedes (xh,yh) - (xi,yi)  Koordianten Paar
folgende Info:  Bits (2*TEXP)-(2*TEXP+8-1): anzahl zu sperrender Felder
        Bits  0-(2*TEXP-1): start addressenoffset f"ur matrix
        Bits SHIFT-(32-1): addressincrement in matrix zur n"achsten position
zei und spa    zaehlen die Anzahl der Marken in jeweiliger Zeilen bzw. Spalte
frei_zei & frei_spa    zaehlen die Anzahl nichtgeblockter Felder in der
                       jeweiligen Zeile bzw. Spalte
elel   enth"alt address offset um array effizienter zu benutzen
*****/
unsigned  matrix[MAX][MAX],  spa[MAX],  zei[MAX],
          frei_zei[MAX], frei_spa[MAX], elel[2*MAX], array[MAX][MAX][MAX][MAX],
          *stack[MAX*MAX], **stpt,  *frei_addrx[MAX*MAX], *frei_addry[MAX*MAX];
unsigned  solution, n, nn, n2, anz, flag, sym_pkt;
unsigned long  cases, count, level, CLK_TCK;
unsigned  restart[PKT], rerun, deep_anz, pkt;
FILE  *fp, *pp;
char  comm[80], filename[32];
static struct tms time_buffer;
#define   VERT  128
#define   HORI   64
#define   ROTA   32
#define   LEFT   16
#define   RIGH    8
#define   ANTI    4
#define   MAIN    2


int sym_test(int *code)
{
int  h, i, j, k, r, s, ii, jj;
   for (k=1+(n&1);k<=n;k+=2)
   {
      i = j = n2;
      i -= k/2;
      r = -k/2;
      s = 0;
      if (!(n&1))
      {
         i--;  j--;
         if (!r)  s = k/2;
      }
      ii = n-1-i;
      jj = n-1-j;
      for (h=4*k;h;h--)
      {
         if (!matrix[i][j])     return(0);  /* Identitaet                   */
         if (!matrix[ii][j])    return(0);  /* Spiegelung an y-Achse        */
         if (!matrix[i][jj])    return(0);  /* Spiegelung an x-Achse        */
         if (!matrix[ii][jj])   return(0);  /* 180-Grad Rotation            */
         if (!matrix[j][ii])    return(0);  /*  90-Grad Rotation positiv    */
         if (!matrix[jj][i])    return(0);  /*  90-Grad Rotation negativ    */
         if (!matrix[jj][ii])   return(0);  /* Spiegelung an Nebendiagonale */
         if (!matrix[j][i])     return(0);  /* Spiegelung an Hauptdiagonale */
         if (matrix[i][j] >= STONE)
         {
            if ((*code&128) && matrix[ii][j] < STONE)  *code &= ~128;
            if ((*code&64) && matrix[i][jj] < STONE)   *code &= ~64;
            if ((*code&32) && matrix[ii][jj] < STONE)  *code &= ~32;
            if ((*code&16) && matrix[j][ii] < STONE)   *code &= ~16;
            if ((*code& 8) && matrix[jj][i] < STONE)   *code &= ~8;
            if ((*code& 4) && matrix[jj][ii] < STONE)  *code &= ~4;
            if ((*code& 2) && matrix[j][i] < STONE)    *code &= ~2;
            if (*code==1)  return(0);
         }
         else  /**  if (matrix[i][j])  **/
         {
            if ((*code&128) && matrix[ii][j] >= STONE)  return(-1);
            if ((*code&64) && matrix[i][jj] >= STONE)   return(-1);
            if ((*code&32) && matrix[ii][jj] >= STONE)  return(-1);
            if ((*code&16) && matrix[j][ii] >= STONE)   return(-1);
            if ((*code& 8) && matrix[jj][i] >= STONE)   return(-1);
            if ((*code& 4) && matrix[jj][ii] >= STONE)  return(-1);
            if ((*code& 2) && matrix[j][i] >= STONE)    return(-1);
         }
         if (r>0)       {  j++;  r--;  jj--;  if (!r)  s = -k;  }
         else if (r<0)  {  j--;  r++;  jj++;  if (!r)  s = k;  }
         if (s>0)       {  i++;  s--;  ii--;  if (!s)  r = k;  }
         else if (s<0)  {  i--;  s++;  ii++;  if (!s)  r = -k;  }
      }
   }
   return(0);
}


void solution_found(int code)
{
int  i, j;
int  vert, hori, rot2, left, right, haupt, neben;
char  *sym_zei,  line[2*MAX+2];
   vert  = code&VERT;
   hori  = code&HORI;
   rot2  = code&ROTA;
   left  = code&LEFT;
   right = code&RIGH;
   neben = code&ANTI;
   haupt = code&MAIN;
   for (i=0;i<2*n;i++)
      line[i]=' ';
   line[i]='\0';
   if (vert && hori && rot2 && left && right)  sym_zei="full";
   else if (vert && hori && !left && !right)  sym_zei="ort2";
   else if (!vert && !hori && neben && haupt)  sym_zei="dia2";
   else if (left && right)  sym_zei="rot4";
   else if (vert || hori)  sym_zei="ort1";
   else if (haupt || neben)  sym_zei="dia1";
   else if (rot2)  sym_zei="rot2";
   else  sym_zei="iden";
   fprintf(fp,"%3u. L\366sung:     Sym.-Gruppe  %s\n",++solution,sym_zei);
   for (i=0;i<n;i++)
   {  for (j=0;j<n;j++)
         line[2*j+1] = (matrix[i][j] < STONE ? '.' : 'o');
      fprintf(fp,"%s\n",line);
   }
   fflush(fp);
   return;
}


void set_next_stone(int sym_code)
{
int  h, i, j, k, l;
unsigned  m, kk, ni, nj;
unsigned  *addr, *index, *start;
unsigned  **frpt = stpt;
int  code, better;
   cases ++;
   if (anz==n+n)
   {  code = sym_code;
      if (code == 1  ||  !sym_test(&code))
         solution_found(code);
      level += anz;
      return;
   }
   k = n+n+1;
   for (h=0;h<n;h++)
      if (spa[h] == 1)
      {  if ((m = frei_spa[h]) == 0)
         {  level+=anz;  return;  }
         m += m;
         if (m < k  || m == k  &&  (h>=n2?h-n2:n2-h) < l)
         {  k = m;  j = h;  l = (h>=n2?h-n2:n2-h); }
      }
      else if (spa[h] == 0)
      {  if ((m = frei_spa[h]) <= 1)
         {  level+=anz;  return;  }
         if (m < k  || m == k  &&  (h>=n2?h-n2:n2-h) < l)
         {  k = m;  j = h;  l = (h>=n2?h-n2:n2-h); }
      }
   kk = k;
   k = n+n+1;
   for (h=0;h<n;h++)
      if (zei[h] == 1)
      {  if ((m = frei_zei[h]) == 0)
         {  level+=anz;  return;  }
         m += m;
         if (m < k  || m == k  &&  (h>=n2?h-n2:n2-h) < l)
         {  k = m;  i = h;  l = (h>=n2?h-n2:n2-h); }
      }
      else if (zei[h] == 0)
      {  if ((m = frei_zei[h]) <= 1)
         {  level+=anz;  return;  }
         if (m < k  || m == k  &&  (h>=n2?h-n2:n2-h) < l)
         {  k = m;  i = h;  l = (h>=n2?h-n2:n2-h); }
      }
   if (better = (kk < k))  i=n2;   else  j=n2;
   count++;
   for (k=0; k < (int)n && -k < (int)n ; k= -k, k += (k>0 ? 1 : -1 ) )
   {  if (better)  i+=k;   else  j+=k;
      if (matrix[i][j])   continue;
      {
         ni = n-1-i;
         nj = n-1-j;
         if (anz < deep_anz)
         {  times (&time_buffer);
            fprintf(fp,"%10lu pos  %10lu cas  %2u(%2u,%2u,%3d) (%u)  %lu sec\n",
                    cases-count, cases, anz, i, j, k, solution, time_buffer.tms_utime / CLK_TCK);
            fflush(fp);
            if (!rerun)
            {  restart[h=(anz)/sym_pkt] = (k>=0?k:-k);
               while(++h<pkt)  restart[h] = 0;
               for(m=0;comm[m];m++) ;
               for(h=0;h<pkt;h++,m+=3)
                  sprintf(comm+m,"%2u ",restart[h]);
               if (pp = fopen(filename,"r+"))
               {  fprintf(pp,"%s&\n",comm);
                  fclose(pp);
               }
               comm[m-3*pkt] = '\0';
            }
         }
         matrix[i][j] += STONE;
         code = sym_code;
         if (anz >= nn || code==1  ||  !sym_test(&code) )
         {  
            block_a_line (i,j);
            if (!rerun)
               set_next_stone(code);
            else
            {  if ( (k>=0?k:-k) >= restart[(anz)/sym_pkt-1] )
               {  --rerun;
                  restart[(anz)/sym_pkt-1] = (k>=0?k:-k);
                  set_next_stone(code);
               }
            }
            unblock_a_line (i,j);
         }
         else
         {  
            matrix[i][j] -= STONE;
         }
      }
   }
   while (stpt > frpt)
   {  addr = *(--stpt);
      if (! (*addr -= BLOCK) )
      {  kk = addr - &matrix[0][0];
         (*frei_addry[kk])++;
         (*frei_addrx[kk])++;
      }
   }
return;
}


int main(unsigned argc, char *argv[])
{

int   h, i, j, k, l;
int  dx, dy, xx, yy;
unsigned  *pointer;
char  *sym_zei;
if (8*sizeof(unsigned) < 4*TEXP + 8)
   return  fprintf(stderr,"sizeof unsigned too small. Decrease TEXP\n"), -3;
if (argc <= 1)
   do {
      printf("n (<=%u) ? ",MAX);  scanf("%u",&n);
   }  while (n > MAX || n > 1<<TEXP || n < 2);
else if (!sscanf(argv[1],"%u",&n)  ||  !n  ||  n > MAX  ||  n > 1<<TEXP)
   return  fprintf(stderr,"invalid value for n\n"), -1;
nn = n-1;
n2 = n/2;
sym_zei = (char*) &h;
if (argc <= 2)
do {
   printf("S (0 = .) ");
   scanf("%1s",sym_zei);
   if (*sym_zei =='0' || '.' == *sym_zei)
      flag = 0;
} while (flag != 0);
else
{  sscanf(argv[2],"%1s",sym_zei);
   if (*sym_zei =='0' || '.' == *sym_zei)
      flag = 0;
   else
      return  fprintf(stderr,"invalid symmetry symbol\n"), -1;
}
sym_pkt = 1;
signal (SIGHUP, SIG_IGN);  /**  nohup  **/
CLK_TCK = sysconf(_SC_CLK_TCK);
pointer = &array[0][0][0][0];
for (h=0;h<n;h++, pointer = &array[h][0][0][0])
for (i=0;i<n;i++, pointer = &array[h][i][0][0])
for (j=0;j<n;j++,pointer+=(MAX-n))
   for (k=0;k<n;k++)
   {  if (h > j || h==j && i > k)
      {  *pointer = array[j][k][h][i];
         pointer++;
         continue;
      }
      dx = h-j;  dy = i-k;
      xx = (dx>=0?dx:-dx);
      yy = (dy>=0?dy:-dy);
      if (dx || dy)
      {  if (xx > yy)  {  l=xx;  xx=yy;  yy=l;  }
         while (xx)  {  l=yy%xx;  yy=xx;  xx=l;  }
         dx /= yy;
         dy /= yy;
      }
      xx = h;  yy = i;
      if (dx)
      {  if (dx < 0)
         dx = -dx,  dy = -dy;
         while ( ( (xx-=dx) | (yy-=dy) ) >= 0)  if (yy >= n)  break;
         do {
            xx+=dx;  yy+=dy;
         }  while (xx==h && yy==i || xx==j && yy==k);
         *pointer = &matrix[xx][yy] - &matrix[0][0]  & MASK;
         *pointer |= (dx*MAX + dy) << SHIFT;
         for (l=1;xx<n&&yy<n&&yy>=0;l++)  xx+=dx,  yy+=dy;
         do {
            xx-=dx;  yy-=dy;
            if (! --l)  break;
         }  while (xx==h && yy==i || xx==j && yy==k);
         if (l==3  &&  (xx-dx==h && yy-dy==i || xx-dx==j && yy-dy==k))
            l=2,   *pointer += (dx*MAX + dy) << SHIFT;
         if (l==4  &&  (xx-dx==h && yy-dy==i || xx-dx==j && yy-dy==k)  &&
                       (xx-2*dx==h && yy-2*dy==i || xx-2*dx==j && yy-2*dy==k) )
            l=2,   *pointer += 2*(dx*MAX + dy) << SHIFT;
         if (l==5  &&  (xx-dx==h && yy-dy==i || xx-dx==j && yy-dy==k)  &&
                       (xx-3*dx==h && yy-3*dy==i || xx-3*dx==j && yy-3*dy==k) )
            l=3,   *pointer += (dx*MAX + dy) << SHIFT;
         *pointer |=  l<<(2*TEXP);
      }
      else if (dy)
      {  if (dy < 0)
         dy = -dy;
         while ((yy-=dy) >=0);
         do {
            yy+=dy;
         }  while (yy==i || yy==k);
         *pointer = &matrix[xx][yy] - &matrix[0][0]  & MASK;
         *pointer |= dy<<SHIFT;
         for (l=1;yy<n;l++)  yy+=dy;
         do {
            yy-=dy;
            if (! --l)  break;
         }  while (yy==i || yy==k);
         if (l==3  &&  (yy-dy==i || yy-dy==k))
            l=2,   *pointer += dy << SHIFT;
         if (l==4  &&  (yy-dy==i || yy-dy==k)  &&  (yy-2*dy==i || yy-2*dy==k) )
            l=2,   *pointer += 2*dy << SHIFT;
         if (l==5  &&  (yy-dy==i || yy-dy==k)  &&  (yy-3*dy==i || yy-3*dy==k) )
            l=3,   *pointer += dy << SHIFT;
         *pointer |=  l<<(2*TEXP);
      }
      else
         *pointer = &matrix[xx][yy] - &matrix[0][0]  & MASK;
      pointer++;
   }

for (i=0;i<n;i++)
{  zei[i] = spa[i] = 0;
   frei_zei[i] = frei_spa[i] = n;
}
for (i=0;i<n;i++)
   for (j=0;j<n;j++)
      matrix[i][j] = 0;
for (i=0;i<n;i++)
   for (j=0;j<n;j++)
   {  frei_addrx[MAX*i+j] = frei_zei + i;
      frei_addry[MAX*i+j] = frei_spa + j;
   }
sprintf(filename,"%s_N%.2u",PROTO,n);
if (argc <=3 || !(fp=fopen(filename,"a")) )  fp = stdout;
sprintf(filename,"%s_N%.2u",FIXPKT,n);
if (argc > 3)
{  if (1!=sscanf(argv[3],"%u",&deep_anz))
      deep_anz = 0;
   sprintf(comm,"%s %2u %1u %u ", argv[0], n, flag, deep_anz);
   deep_anz *= sym_pkt;
}
rerun = pkt = (argc > 4 ? (argc-4>PKT ? PKT :argc-4) : 0);
for (h=0;h<pkt;h++)
   sscanf(argv[4+h],"%u",&restart[h]);

count = cases = solution = anz = level = 0;
stpt = stack;
if ((n&1) && (flag==1 || flag==4))
{  matrix[n2][n2] += BLOCK;
   frei_zei[n2]--;    frei_spa[n2]--;
}
if ( !(n&1) ||  flag!=3 && flag!=5 && flag!=6 && flag!=7 )
   set_next_stone (255);
sym_zei = "iden";
fprintf(fp,"N=%2u(%s)   %u solutions found   %lu positions in %lu cases checked\n",
        n, sym_zei, solution, cases-count, cases );
times (&time_buffer);
if (cases-count)
   fprintf(fp,"average number of stones on board %lu   %lu sec\n",
           level/(cases-count) , time_buffer.tms_utime/CLK_TCK );
return  0;
}