#include <signal.h>                            /***   version 2026-03-17   ***/
#include <stdio.h>                             /***   Achim Flammenkamp    ***/
#include <signal.h>                            /***  new version: 21.4.96  ***/
#ifndef  MAX                                   /***    Date:   15.05.90    ***/
#define   MAX   96   // must be even and < 128
#endif
#define   STONE  (MAX*MAX-MAX)
#define   BLOCK  (STONE/2)
#define   D_TEXP  13
#define   MASK   ((1<<D_TEXP)-1)
#define   MANZ   ((1<<6)-1)
#define   SHIFT  (32-D_TEXP)
// array[][][][] has 32 bits divided into 3 consecutive blocks:  MASK:MANZ:SHIFT
// MASK:   lowest D_TEXP-bits code the address-offset relativ to matrix[0][0]
// MANZ:   central  8 bits code the number of to block points
// SHIFT:  higest D_TEXP-bits code the address-increament to next blocked point
// if MAX <= 64 , this is  12:8:12  // MANZ must be only at most 6 bits
// if MAX <= 90 , this is  12:7:13  // increament is always <= MAX*MAX/3
// if MAX <= 128, this is  13:6:13  // use only the lower left quarter of matrix


#define   block_a_line(x1,y1)                                         \
          spa[y1]++;                                                  \
          start= &array[x1][y1][0][0];                                \
          for(l=0;l<anz;l++)                                          \
          {  index=start+elel[l];                                     \
             if (!(m= *index>>D_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);

#define   unblock_a_line(x1,y1)                                       \
          anz--;                                                      \
          spa[y1]--;                                                  \
          start= &array[x1][y1][0][0];                                \
          for(l=0;l<anz;l++)                                          \
          {  index=start+elel[l];                                     \
             if (!(m= *index>>D_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])++;                            \
                   }                                                  \
             }                                                        \
          }


static unsigned  matrix[MAX][MAX], spa[MAX], frei_zei[MAX],
                 frei_spa[MAX], elel[2*MAX],  array[MAX][MAX][MAX][MAX];
static unsigned long  cases, count, level;
static unsigned  solution, anz, n, n2, flag, max_deep;
static unsigned  *stack[MAX*MAX], **stpt,  *frei_addrx[MAX*MAX],
                 *frei_addry[MAX*MAX];
static FILE  *fp;


static void solution_found(int code)
{
int  i, j;
char  *sym_zei,  line[2*MAX+2];
   sym_zei="full";
   for (i=0;i<2*n;i++)
      line[i]= ' ';
   line[i]= '\0';
   fprintf(fp,"%3u. Lösung:     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;
}

#define  check_rot_line(x1,y1,x2,y2)                                   \
         index= &array[x1][y1][x2][y2];                                \
         if (m= *index>>D_TEXP &MANZ)                                  \
         {  h= *index >> SHIFT;                                        \
            for (addr= &matrix[0][0]+ (*index&MASK); m; addr+=h, m--)  \
               if (*addr>=STONE)  break;                               \
            if (m) continue;                                           \
         }

static void set_next_stone(int sym_code)
{
int  i, j, k, l;
unsigned  h, m, kk, ni, nj;
unsigned  *addr, *index, *start;
unsigned  **frpt= stpt;
   cases++;
   if (anz > max_deep)
      max_deep=anz;
   if (anz==n+n - 2*(n&3))
   {  if (n&3)  // 4 missing on long diagonals
      {  for (h=0;h<n2;h++)
            if (!matrix[h][h])
               break;
         if (h == n2)
            return;
         matrix[h][h] += STONE;
         matrix[h][n-1-h] += STONE;
         matrix[n-1-h][h] += STONE;
         matrix[n-1-h][n-1-h] += STONE;
         level += anz;
         anz += 4;
         if (anz > max_deep)
            max_deep=anz;
      }
      solution_found(sym_code);
      level += anz;
      if (n&3)
      {
         anz -= 4;
         matrix[h][h] -= STONE;
         matrix[h][n-1-h] -= STONE;
         matrix[n-1-h][h] -= STONE;
         matrix[n-1-h][n-1-h] -= STONE;
      }
      return;
   }
   j= n;
   k= n+1;
   for (h=0;h<n2;h++)
      if (!spa[h])
      {  if (!(m= frei_spa[h]+frei_zei[h])) 
         {  level+=anz;
            return;
         }
         if (m == 1 && !matrix[h][h])
            continue;  // never choose long diagonal, may occur only if n%4 == 2
         if (m < k  || m == k  &&  n2-h < l)
         {  k = m;  j = h;  l = n2-h;  }
      }
   if (j==n)
      return;
   count++;
   for (k=0; k<n2; k++)
   {  if (n2-1-k >= j)
         i=n2-1-k;
      else
         j=n2-1-k;
      if (!matrix[i][j] && i!=j)  // never choose long diagonal
      {  ni= n-1-i;
         nj= n-1-j;
         check_rot_line(i,j,nj,i);
         check_rot_line(i,j,j,ni);
         check_rot_line(ni,nj,nj,i);
         check_rot_line(ni,nj,j,ni);
         matrix[nj][i] += STONE;
         matrix[j][ni] += STONE;
         matrix[ni][nj] += STONE;
         matrix[i][nj] += STONE;
         matrix[ni][j] += STONE;
         matrix[nj][ni] += STONE;
         matrix[j][i] += STONE;
         matrix[i][j] += STONE;
         block_a_line(nj,i);
         block_a_line(j,ni);
         block_a_line(ni,nj);
         block_a_line(i,nj);
         block_a_line(ni,j);
         block_a_line(nj,ni);
         block_a_line(j,i);
         frei_spa[j]--;
         frei_zei[i]--;
         block_a_line (i,j);
         set_next_stone(sym_code);
         unblock_a_line (i,j);
         matrix[i][j] -= BLOCK;
         *(stpt++)= &matrix[i][j];
         unblock_a_line(j,i);
         matrix[j][i] -= STONE;
         unblock_a_line(nj,ni);
         matrix[nj][ni] -= STONE;
         unblock_a_line(ni,j);
         matrix[ni][j] -= STONE;
         unblock_a_line(i,nj);
         matrix[i][nj] -= STONE;
         unblock_a_line(ni,nj);
         matrix[ni][nj] -= STONE;
         unblock_a_line(j,ni);
         matrix[j][ni] -= STONE;
         unblock_a_line(nj,i);
         matrix[nj][i] -= STONE;
      }
   }
   while (stpt > frpt)
   {  addr= *(--stpt);
      *addr -= BLOCK;
      kk= addr - &matrix[0][0];
      if (! *addr)
      {  (*frei_addry[kk])++;
         (*frei_addrx[kk])++;
      }
   }
return;
}
#undef  check_rot_line


static int init_array() // each array[][][][] has 32 bits divided into 3 consecutive          
{                 // blocks: MASK(lowest bits):MANZ(central):SHIFT(highest bits)
int  h, i, j, k, m, dx, dy, xx, yy;
unsigned  *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++, pointer++)
      {  if (h > j || h==j && i > k)
         {  *pointer= array[j][k][h][i];
            continue;
         }
         *pointer= 0;
         dx = j-h;  // always >= 0
         dy = k-i;
         if (!dx && !dy)
            continue;
         xx= dx;
         yy= dy>=0 ? dy : -dy;
         if (xx > yy)
         {  m=xx;  xx=yy;  yy=m;  }
         while (xx)
         {  m=yy%xx;  yy=xx;  xx=m;  }
         dx /= yy;
         dy /= yy;

         xx= h;  yy= i;
         if (dx)
         {  if (dy > 0)
            {  if (dx >= n2 || dy >= n2)
                  continue;
               m= (xx/dx <= yy/dy ? xx/dx : yy/dy);
               xx -= dx*m;
               yy -= dy*m;
               while (xx==h && yy==i || xx==j && yy==k)
               {  xx+=dx;  yy+=dy;  }
               if (xx >= n2 || yy >= n2)
                  continue;
            }
            else if (dy < 0)
            {  if (dx >= n2 || -dy >= n2)
                  continue;
               if (yy >= n2)
                  m= -((yy-n2)/(-dy)+1);
               else
               {  m= (n2-yy-1)/(-dy);
                  if(xx/dx < m)  m= xx/dx;
               }
               xx -= dx*m;
               yy -= dy*m;
               while (xx==h && yy==i || xx==j && yy==k)
               {  xx+=dx;  yy+=dy;  };
               if (xx >= n2 || yy < 0)
                  continue;
            }
            else
            {  if (dx >= n2)
                  continue;
               m= xx/dx;
               xx -= dx*m;
               while (xx==h && yy==i || xx==j && yy==k)
               {  xx+=dx;  }
               if (xx >= n2)
                  continue;
            }
            *pointer= &matrix[xx][yy] - &matrix[0][0];
            if (*pointer > MASK)
            {  fprintf(stderr,"MASK overflow\n");  return 1; }
            if (dx*MAX + dy >= 1<<(32-SHIFT))
            {  fprintf(stderr,"SHIFT underflow\n");  return 2; }
            *pointer |= (dx*MAX + dy) << SHIFT;
            for(m=1; xx < n2 && yy < n2 && yy >= 0; m++)
            {  xx += dx;  yy += dy;
            }
            do {
               xx -= dx;  yy -= dy;
            } while (--m && (xx==h && yy==i || xx==j && yy==k));
            if (m==3  && (xx-dx==h && yy-dy==i || xx-dx==j && yy-dy==k))
               m=2,   *pointer += (dx*MAX + dy) << SHIFT,  dx+=dx,  dy+=dy;
            if (m==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))
               m=2,   *pointer += 2*(dx*MAX+dy) << SHIFT,  dx+=2*dx,  dy+=2*dy;
            if (m==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))
               m=3,   *pointer += (dx*MAX + dy) << SHIFT,  dx+=dx,  dy+=dy;
         }
         else  // dx == 0
         {  // always dy > 0
            if (xx >= n2)
               continue;
            if (dy >= n2)
               continue;
            while ((yy-=dy) >=0);
            do {
               yy+=dy;
            }  while (yy==i || yy==k);
            if (yy >= n2)
               continue;
            *pointer= &matrix[xx][yy] - &matrix[0][0];
            if (*pointer > MASK)
            {  fprintf(stderr,"MASK overflow\n");  return 1; }
            if (dy >= 1<<(32-SHIFT))
            {  fprintf(stderr,"SHIFT underflow\n");  return 2; }
            *pointer |= dy<<SHIFT;
            for (m=1;yy<n2;m++)
               yy+=dy;
            do {
               yy-=dy;
            }  while (--m  && (yy==i || yy==k));
            if (m==3  &&  (yy-dy==i || yy-dy==k))
               m=2,   *pointer += dy << SHIFT,   dy += dy;
            if (m==4  &&  (yy-dy==i || yy-dy==k)  && (yy-2*dy==i || yy-2*dy==k))
               m=2,   *pointer += 2*dy << SHIFT,   dy += 2*dy;
            if (m==5  &&  (yy-dy==i || yy-dy==k)  && (yy-3*dy==i || yy-3*dy==k))
               m=3,   *pointer += dy << SHIFT,   dy += dy;
         }
         if (m > MANZ)
         {  fprintf(stderr,"MANZ overflow\n");  return 3; }
         if (m)
         {
            xx = (*pointer&MASK) / MAX;
            yy = (*pointer&MASK) % MAX;
            if (xx < yy  ||  n <= xx+yy  ||  2*xx >= n)
            {  do
               {  xx += dx;  yy += dy;
                  m--;
               } while (m  &&  (xx < yy  ||  n <= xx+yy  ||  2*xx >= n));
               *pointer &= ~MASK;
               *pointer |= xx*MAX + yy & MASK;
            }
            *pointer |=  m<<(D_TEXP);
            while (m  &&  (xx >= yy  &&  n > xx+yy  && 2*xx < n))
            {  xx += dx;  yy += dy;
               m--;
            }
            *pointer -=  m<<(D_TEXP);
         }
      }
return 0;
}


int main(int argc, char *argv[])
{
int   i, j;
char  *sym_zei, filename[9];
if (argc <= 1)
   do {
      printf("n (<=%u) ? ",MAX);  scanf("%u",&n);
   }  while (n > MAX || !n);
else if (!sscanf(argv[1],"%u",&n)  ||  !n  ||  n > MAX)
   return  fprintf(stderr,"invalid value for n\n"), -1;
n2= n/2;
sprintf(filename,"full_%.2u",n);  // if n >= 100 filename is 9 characters long
if (argc <= 2)
do {
  printf("S (7 = *) ? ");
  scanf("%u",&flag);
}  while (flag != 7);
else if (!sscanf(argv[2],"%u",&flag)  ||  flag != 7)
   return  fprintf(stderr,"invalid symmetry symbol\n"), -1;
signal(SIGHUP, SIG_IGN);
if (i=init_array())
   return  i;
for (i=0;i<n2;i++)
{  spa[i]= 0;
   frei_zei[i]= i;
   frei_spa[i]= n2 - i - !(n&3);
}
for (i=0;i<n;i++)
   for (j=0;j<n;j++)
      matrix[i][j]= 0;
if (!(n&3))
   for (j=0;j<n;j++)
      matrix[j][j]= BLOCK;
for (i=0;i<n2;i++)
   for (j=0;j<n2;j++)
   {  frei_addrx[MAX*i+j]= frei_zei + i;
      frei_addry[MAX*i+j]= frei_spa + j;
   }
// to avoid counting stones on the long diagonal double
// we direct their counter to outside the considered range
for (j=0;j<n2;j++)
   frei_addrx[MAX*j+j]= frei_spa + MAX-1;
if (argc <= 3 || !(fp=fopen(filename,"a")) )
   fp= stdout;
count= cases= solution= anz= level= max_deep= 0;
stpt= stack;
sym_zei= "full";
if (!(n&1))
   set_next_stone(1);
fprintf(fp,"N=%2u(%s)   %u solutions found    %lu positions in %lu cases checked\n",
        n, sym_zei, solution, cases-count, cases );
if (cases-count)
   fprintf(fp,"average number of stones on board %lu  max. number = %u\n",
           level/(cases-count), max_deep);
return  0;
}