/*
 *  File:    BorderedSquares.cpp
 *  Author:  S Harry White
 *  Created: 2009-02-15
 *  Updated: 2020-05-01
 *   Added howMany.
 *  Updated: 2020-07-09
 *    Add makeOddAbulWafa, makeOddSeki, makeOddStifel, makeOddTravers.
 *    Add input selection of method.
 *    Sort output in Frénicle standard form removing duplicates.
 *  Updated: 2021-12-29
 *    Replace & with && where necessary.
 *  Updated: 2023-01-05
 *    Change to compile with g++ for macOS.
 */

/*
 * Makes bordered magic squares of order n.
 */

#include <curses.h>
#include <errno.h>
#include <limits.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/stat.h>
#include <sys/types.h>
#include <time.h>
#include <unistd.h>

#define min(a,b) (((a)<(b))?(a):(b))
#define max(a,b) (((a)>(b))?(a):(b))

int **xSquare=NULL, **bSquare=NULL, **Squares=NULL, *square=NULL, *top=NULL, *left=NULL;
bool *numberUsed=NULL; const bool F=false, T=true;
const int startSize=12, startSquaresSize=1024;
int allocatedSize, allocatedSquaresSize, biggestValue, Sindex, sLen;
//======================================= allocate store ======================================

const char *storeAllocFail="Storage allocation failed"; bool bell=T;
bool reportError(const char *msg) {
//   -----------
  printf("%sError: %s.\n", bell ? "\a\n" : "",  msg);
  if (bell) bell=F; return F;
} // reportError

void freeInts(int **line) { if (*line!=NULL) { free(*line); *line=NULL; }}
//   --------

void freeSquare(int*** square, const int size) {
//   ----------
  if (*square!=NULL) {
    for (int i=0; i<size; i++) free((*square)[i]);
    free(*square); *square=NULL;
  }
} // freeSquare

void freeStore() {
//   ---------
  freeSquare(&xSquare, allocatedSize); freeSquare(&bSquare, allocatedSize);
  freeSquare(&Squares, allocatedSquaresSize); freeInts(&square); 
  freeInts(&top); freeInts(&left);
  if (numberUsed!=NULL) { free(numberUsed); numberUsed=NULL; }
  allocatedSize=0;
} // freeStore

bool allocateInts(int **line, const int size) {
//   ------------
  *line=(int*)malloc(size*sizeof(int)); return *line!=NULL;
} // allocateInts

bool allocateSquare(int*** square, const int size) {
//   --------------
  bool ok;

  *square=(int**) malloc(size*sizeof(int*));
  ok=(*square!=NULL);
  if (ok) {
    int numAllocated=size;
    for(int i=0; i<size; i++) {
      int *p=(int*) malloc(size*sizeof(int));
      (*square)[i]=p;
      if (p==NULL) { numAllocated=i; ok=F; break; }
    }
    if (!ok) freeSquare(square, numAllocated);
  }
  return ok;
} // allocateSquare 

bool allocateSquares(const int size) {
//   ---------------
  bool ok; int length=size*size;

  Squares=(int**) malloc(startSquaresSize*sizeof(int*));
  ok=(Squares!=NULL);
  if (ok) {
    int numAllocated=startSquaresSize;
    for(int i=0; i<startSquaresSize; i++) {
      int *p=(int*) malloc(length*sizeof(int)); (Squares)[i]=p;
      if (p==NULL) { numAllocated=i; ok=F; break; }
    }
    if (!ok) freeSquare(&Squares, numAllocated);
  }
  return ok;
} // allocateSquares

bool increaseSquares() {
//   ---------------
  bool ok;
  int length=allocatedSize*allocatedSize, // of square
      size=allocatedSquaresSize+allocatedSquaresSize,
      **t=(int**) malloc(size*sizeof(int*));
  if ((ok=(t!=NULL))) {
    for (int i=0; i<allocatedSquaresSize; i++) t[i]=Squares[i];
    free(Squares); Squares=t;
    int numAllocated=size;
    for(int i=allocatedSquaresSize; i<size; i++) {
      int *p=(int*) malloc(length*sizeof(int)); (Squares)[i]=p;
      if (p==NULL) { numAllocated=i; ok=F; break; }
    }
    if (!ok) freeSquare(&Squares, numAllocated);
  }
  if (ok) allocatedSquaresSize=size; else reportError(storeAllocFail);
  return ok;
} // increaseSquares

bool allocateStore(int size) {
//   -------------
  bool ok=T;

  if (size<startSize) size=startSize;
  if (size>allocatedSize) {
    freeStore();
    if ((ok=allocateSquare(&xSquare, size)))
      if ((ok=allocateSquare(&bSquare, size)))
        if ((ok=allocateSquares(size))) {
          allocatedSize=size; allocatedSquaresSize=startSquaresSize;
          if ((ok=allocateInts(&square, size*size)))
            if ((ok=allocateInts(&top, size)))
              if ((ok=allocateInts(&left, size)))
                if (ok) ok=(numberUsed=(bool *) malloc((size*size+1)*sizeof(bool)))!=NULL;
        
    }
    if (!ok) freeStore();
  }
  return ok;
} //allocateStore
//========================================= check squares =======================================

bool isCorrect(int **x, const int n) {
//   ---------
  const int nn=n*n, nnp1=nn+1, big=n%2==0 ? nn/2 : (nn-1)/2;
  if (biggestValue!=big) return F;
  const int chkSum=n%2==0 ? n/2*nnp1 : n*(nnp1/2); int sumX, sumY, sumXY=0, sumYX=0;

  for (int i=0; i<n; i++) {
    sumX=0; sumY=0;for (int j=0; j<n; j++) { sumX+=x[i][j]; sumY+=x[j][i]; }
    if ((sumX!=chkSum)|(sumY!=chkSum)) return F; sumXY+=x[i][n-i-1]; sumYX+=x[i][i];
  }
  return ((sumXY==chkSum)&(sumYX==chkSum));
} // isCorrect

bool isContiguous(int **x, const int n, const int m, int *first) {
//   ------------
  int low=*first, high=low+m+m-3, lo=INT_MAX, hi=INT_MIN;
  int o=(n-m)/2, l=o+m-1, t=0;

  // Corners
  t=min(x[o][o], x[l][l]); if (t<lo) lo=t; if (t>hi) hi=t;
  t=min(x[o][l], x[l][o]); if (t<lo) lo=t; if (t>hi) hi=t;

  // Top, bottom
  for (int c=o+1; c<l; ++c) { t=min(x[o][c], x[l][c]); if (t<lo) lo=t; if (t>hi) hi=t; }

  // Left, left
  for (int r=o+1; r<l; ++r) { t=min(x[r][o], x[r][l]); if (t<lo) lo=t; if (t>hi) hi=t; }
  if ((lo!=low)|(hi!=high) ) return F; *first=hi+1; return T;
} // isContiguous

bool isBordered(int **x, const int n) {
//   ----------
  int first=1; const int end=(n&1)?3:6;

  for (int m=n; m>=end; m-=2)if (!isContiguous(x, n, m, &first)) return F;
  return T;
} // isBordered
//========================================= output squares =======================================

int fieldWidth(const int n) {
//  ----------
  if (n==1) return 1; int i=n*n, width=1; while ((i/=10)!=0) ++width; return width;
} // fieldWidth

typedef bool (*t_fprintFW)(FILE *fp, const int i);

bool fprintFW1(FILE *fp, const int i) { return fprintf(fp, "%1d",  i)>0; }
bool fprintFW2(FILE *fp, const int i) { return fprintf(fp, "%2d",  i)>0; }
bool fprintFW3(FILE *fp, const int i) { return fprintf(fp, "%3d",  i)>0; }
bool fprintFW4(FILE *fp, const int i) { return fprintf(fp, "%4d",  i)>0; }
bool fprintFW5(FILE *fp, const int i) { return fprintf(fp, "%5d",  i)>0; }
bool fprintFW6(FILE *fp, const int i) { return fprintf(fp, "%6d",  i)>0; }
bool fprintFW7(FILE *fp, const int i) { return fprintf(fp, "%7d",  i)>0; }
bool fprintFW8(FILE *fp, const int i) { return fprintf(fp, "%8d",  i)>0; }
bool fprintFW9(FILE *fp, const int i) { return fprintf(fp, "%9d",  i)>0; }
bool fprintFWa(FILE *fp, const int i) { return fprintf(fp, "%10d", i)>0; }

static t_fprintFW fprintFW[]={ NULL,
  fprintFW1, fprintFW2, fprintFW3, fprintFW4, fprintFW5,
  fprintFW6, fprintFW7, fprintFW8, fprintFW9, fprintFWa
};
const int maxFieldWidth=10;
bool printSquare(int **x, const int n, FILE *wfp) {
//   -----------
  const int fw0=fieldWidth(n), fw=fw0+1; if (fw>maxFieldWidth) return F;
  for (int i=0; i<n; i++) {
    if (!fprintFW[fw0](wfp, x[i][0])) return F;
    for (int j=1; j<n; j++)   
      if (!fprintFW[fw](wfp, x[i][j])) return F;
    if (fputc('\n', wfp)==EOF) return F;
  }
  return fputc('\n', wfp)!=EOF;
} // printSquare

bool outputSquares(const int n, FILE *wfp) {
//   -------------
  const int m=n-1, fw0=fieldWidth(n), fw=fw0+1; if (fw>maxFieldWidth) return F;

  for (int i=0; i<Sindex; i++) {
    int *x=Squares[i], j=0, r=n, c;
    while (r--) {
      if (!fprintFW[fw0](wfp, x[j++])) return F;
      c=m; while (c--) if (!fprintFW[fw](wfp, x[j++])) return F;
      if (fputc('\n', wfp)==EOF) return F;
    }
    if (fputc('\n', wfp)==EOF) return F;
  }
  return T;
} // outputSquares
//================================= sort Frénicle ascending =================================

int cmpSquares(int *key, int *s) {
//  ----------
  int i=0;
  while(i++<sLen) if (*key<*s) return -1; else if (*key++>*s++) return 1; return 0;
} // cmpRowPerms

int findSquare(int *key, int *insertPoint) {
//  ----------
  int first=0, last=Sindex-1, middle;

  while (first<=last) {
    middle=(first+last)/2; int cmp=cmpSquares(key,Squares[middle]);
    if (cmp<0) last=middle-1; else if (cmp>0) first=middle+1; else return T;
  }
  *insertPoint=first; return F;
} // findSquare

bool insertSquare(int *sq, const int insertPoint, bool *storeFail) {
//   ------------
  if (Sindex==allocatedSquaresSize) if (!increaseSquares()) { *storeFail=T; return F; }
  int *p=Squares[Sindex];
  for (int i=Sindex; i>insertPoint; --i) Squares[i]=Squares[i-1];
  for (int i=0; i<sLen; ++i) p[i]=sq[i]; Squares[insertPoint]=p; ++Sindex; return T;
} // insertSquare

bool pushSquare(int **x, const int n, bool *storeFail) {
//   ----------
  int i=0, insertPoint;

  for (int r=0; r<n; ++r) for (int c=0; c<n; ++c) square[i++]=x[r][c];
  if (Sindex==0) insertPoint=0; else if (findSquare(square, &insertPoint)) return F;
  return insertSquare(square, insertPoint, storeFail);
} // pushSquare

#define fForm(iX, jX) for (int i=0; i<n; ++i) for (int j=0; j<n; ++j) t[iX][jX]=x[i][j]
#define xCopy() for (int i=0; i<n; ++i) for (int j=0; j<n; ++j) x[i][j]=t[i][j]

void putInFrenicleForm(int **x, const int n) {
//   -----------------
  const int m=n-1, l=n-2; bool inFrenicleForm=F;
  int **t=bSquare, minC=min(min(x[0][0], x[0][m]), min(x[m][0], x[m][m]));

  if (x[0][0]==minC) {
    if (x[0][1]<x[1][0]) inFrenicleForm=T;         else fForm(j,i);     /* YX */
  } else if (x[0][m]==minC) {
    if (x[1][m]<x[0][l]) fForm(m-j,i);   /* -90 */ else fForm(i,m-j);   /* Y  */
  } else if (x[m][m]==minC) {
    if (x[m][l]<x[l][m]) fForm(m-i,m-j); /* 180 */ else fForm(m-j,m-i); /* XY */
  } else { // x[m][0]==minC
    if (x[l][0]<x[m][1]) fForm(j,m-i);   /* 90  */ else fForm(m-i,j);   /* X  */
  }
  if (!inFrenicleForm) xCopy();
} // putInFrenicleForm

bool putSquare(int **x, const int n) {
//   ---------
  bool storeFail=F;
  putInFrenicleForm(x,n); pushSquare(x, n, &storeFail); return !storeFail;
} // putSquare
//======================================= common procedures ======================================

void seed_rand() { srand((unsigned int)time(NULL)); }

int random_(const int x) { return rand()%x; }

bool randomBool() { return random_(2)==0; }

typedef void (*t_Turn)(int **x, int **b, const int, const int, const int);
void no_Turn   (int **x, int **b, const int n, const int i, const int j) { x[i][j]    =b[i][j]; };
void rotate_90 (int **x, int **b, const int n, const int i, const int j) { x[j][n-i]  =b[i][j]; };
void rotate_180(int **x, int **b, const int n, const int i, const int j) { x[n-i][n-j]=b[i][j]; };
void rotate_270(int **x, int **b, const int n, const int i, const int j) { x[n-j][i]  =b[i][j]; };
void rotate_Y  (int **x, int **b, const int n, const int i, const int j) { x[i][n-j]  =b[i][j]; };
void rotate_XY (int **x, int **b, const int n, const int i, const int j) { x[n-j][n-i]=b[i][j]; };
void rotate_X  (int **x, int **b, const int n, const int i, const int j) { x[n-i][j]  =b[i][j]; };
void rotate_YX (int **x, int **b, const int n, const int i, const int j) { x[j][i]    =b[i][j]; };
static t_Turn turnCell[]={ no_Turn,  rotate_90, rotate_180, rotate_270,
                           rotate_Y, rotate_XY, rotate_X,   rotate_YX };
const int numRotations=8;
void Turn(int **x, int **b, const int o, const int n) {
//   ----
  const int nmo=n-o, npo=n+o, k=random_(numRotations);

  if ((n-o==0)|(n-o==3)) { // turn all 1x1, 4x4
    for (int i=o; i<=n; i++) for (int j=o; j<=n; j++)
      turnCell[k](x, b, npo, i, j);
  } else { // turn only border rows and columns  
    for (int i=o; i<=n; i+=nmo) for (int j=o; j<=n; j++)
      turnCell[k](x, b, npo, i, j);
    for (int j=o; j<=n; j+=nmo) for (int i=o+1; i<n; i++)
      turnCell[k](x, b, npo, i, j);
  }
} // Turn

void putBorder(int **x, int **b, const int o, const int n) { // random choices from top and left
//   ---------
  int length=n-o-1; // remaining choices in top, left 
  for (int i=o+1; i<(n-1); ++i) {
    int k=random_(length); b[o][i]=top[k]; b[n][i]=-top[k];
    for (int j=k; j<length; ++j) top[j]=top[j+1];
    k=random_(length); b[i][o]=left[k]; b[i][n]=-left[k];
    for (int j=k; j<length; ++j) left[j]=left[j+1]; --length;
  }
  b[o][n-1]=top[0]; b[n][n-1]=-top[0]; b[n-1][o]=left[0]; b[n-1][n]=-left[0];
  Turn(x, b, o, n);
} // putBorder

void makeActual(int **x, const int n) {
//   ----------
  const int nn=n*n;
  
  if ((n&1)==0) {
    const int pPlus=nn/2, mPlus=pPlus+1;
    for (int i=0; i<n; i++) for (int j=0; j<n; j++) x[i][j]+=x[i][j]>0 ? pPlus : mPlus;
  } else {
    const int midc=(nn+1)/2;
    for (int i=0; i<n; i++) for (int j=0; j<n; j++) x[i][j]+=midc;
  }
} // makeActual
//=========================================== even ============================================

const int num4x4=880;
const int code4x4[]={
0x01ebd2c9,0x01ecd2b9,0x01fcd3b8,0x02d9c3ea,0x02dbc3e8,0x02dec39a,0x02dec3b8,0x02f7e1ca,
0x02fbe1c6,0x02fce17a,0x02fce1b6,0x03c7d2eb,0x03c7e1db,0x03cbd2e7,0x03cbe1d7,0x03cde17b,
0x03cde1b7,0x03ced27b,0x03ced2b7,0x03d8b5fa,0x03dcf17a,0x03dcf1b6,0x03dfa48b,0x03dfc26b,
0x03dfc2a7,0x03e8b6f9,0x03ecf279,0x03ecf2b5,0x03ef948b,0x03efc15b,0x03efc197,0x03fde269,
0x03fde2a5,0x03fed15a,0x03fed196,0x04b9a5ec,0x04bda5e8,0x04bea59c,0x04bea5d8,0x04f7d29c,
0x04f9d27c,0x04f9d2e5,0x04fed295,0x05a6e1dc,0x05a7b4ed,0x05a7e1bd,0x05ab96cd,0x05abe17d,
0x05abe1d7,0x05ac96bd,0x05adb4e7,0x05ade16c,0x05ade1b7,0x05aeb47d,0x05aeb4d7,0x05baf17c,
0x05baf1d6,0x05bc97f8,0x05bf86c9,0x05bfa46d,0x05bfa4c7,0x05eaf479,0x05eaf4d3,0x05efa13d,
0x05efa197,0x05fbe469,0x05fbe4c3,0x05feb13c,0x05feb196,0x0697b4de,0x0697d2be,0x069b87ec,
0x069bd27e,0x069bd2e7,0x069d87ea,0x069db47e,0x069db4e7,0x069e87bc,0x069e87da,0x069eb4d7,
0x069ed2b7,0x06b9f27c,0x06b9f2e5,0x06bf945e,0x06bf94c7,0x06d7c18e,0x06d8e37c,0x06d8e3f4,
0x06d9f47a,0x06d9f4e3,0x06dac15e,0x06df923e,0x06df92a7,0x06fac3d4,0x06fbd45a,0x06fbd4c3,
0x06fdb23c,0x06fdb2a5,0x06fdc3a4,0x078dc36e,0x079ad3f6,0x079bc26f,0x079cb5f6,0x079da46f,
0x079fc24d,0x07a9e3f5,0x07abc15f,0x07acb6f5,0x07ae945f,0x07b9e26d,0x07bad15e,0x07bda6e5,
0x07be95d6,0x07c9e5f3,0x07cad6f3,0x07cda13f,0x07ce923f,0x07cfa12e,0x07d9e46b,0x07dbc6e3,
0x07dcb13e,0x07de93b6,0x07ead45b,0x07ebc5d3,0x07ecb23d,0x07eda3b5,0x087de16c,0x08fdb43a,
0x08feb439,0x096b78ed,0x096bc3e8,0x096be17d,0x096d78eb,0x096da5e8,0x096de17b,0x096e78bd,
0x096e78db,0x096ea5d8,0x096ec3b8,0x097f68ad,0x097f68cb,0x097fc24d,0x09ebc54a,0x09eda32c,
0x09ef524d,0x09ef613d,0x09ef615b,0x09fe713c,0x09fe715a,0x0a5b78de,0x0a5bd27e,0x0a5bd2c9,
0x0a5cd2b9,0x0a5d78be,0x0a5d78eb,0x0a5dc36e,0x0a5e78db,0x0a5ed27b,0x0a7f589e,0x0a7f58cb,
0x0adf436c,0x0adf523e,0x0adf526b,0x0afd723c,0x0afd7269,0x0b4d87ea,0x0b4e87da,0x0b4ec39a,
0x0b5c79fa,0x0b5c97f8,0x0b5d68af,0x0b5f86c9,0x0b6c7af9,0x0b6e589f,0x0b7d6ae9,0x0b7e59da,
0x0bcd613f,0x0bce523f,0x0bce921d,0x0bcf612e,0x0bcf831d,0x0bdc713e,0x0bde537a,0x0bec723d,
0x0bed6379,0x0bed832c,0x0c3d78be,0x0c3db47e,0x0c3e78bd,0x0c3eb47d,0x0c7f389e,0x0c7f38ad,
0x0c7fa12e,0x0cbe921d,0x0cbf345e,0x0cbf346d,0x0cbf612e,0x0d2e87bc,0x0d2ea59c,0x0d3fa48b,
0x0d6e389f,0x0d6f498e,0x0d7e39bc,0x0dae345f,0x0daf436c,0x0dbe357c,0x0e3f948b,0x0e9f524d,
0x10edc2a9,0x10fac3d8,0x10fdc3a8,0x12c9a4eb,0x12cde06b,0x12cde0a7,0x12ceb59a,0x12ced37a,
0x12ced3b6,0x12d6c3fa,0x12d6f0ca,0x12d7f0ab,0x12dac3f6,0x12daf07b,0x12daf0c6,0x12dcf06a,
0x12dcf0a6,0x12dfc36a,0x12dfc3a6,0x12ecf378,0x12ecf3b4,0x12efc04b,0x12efc087,0x12f9a7e8,
0x12fde368,0x12fde3a4,0x12fe859a,0x12fed04a,0x12fed086,0x13cdf269,0x13cdf2a5,0x13cfd04b,
0x13cfd087,0x13e4d2f9,0x13e8d2f5,0x13efd249,0x13efd285,0x14abe06d,0x14abe0c7,0x14ad86e9,
0x14ae97d8,0x14aeb57c,0x14aeb5d6,0x14b6a5fc,0x14b6f0ac,0x14ba87dc,0x14baf06c,0x14baf0c6,
0x14bca5f6,0x14bcf0a6,0x14bd87ac,0x14bdf2a5,0x14bfa56c,0x14bfa5c6,0x14bfd087,0x14eaf578,
0x14eaf5d2,0x14efa02d,0x14efa087,0x14f7b08d,0x14fbe568,0x14fbe5c2,0x14fcb03d,0x14fe923d,
0x14feb02c,0x14feb086,0x15e6c38d,0x15e8c36d,0x15e8c3f4,0x15efc384,0x168ad37e,0x168bc2e7,
0x168cb57e,0x168da4e7,0x168ed35c,0x1697b4af,0x169ab47f,0x16a7c08f,0x16a8f37c,0x16abc04f,
0x16acb7f4,0x16af84c7,0x16b8f2e4,0x16bad04e,0x16bda7e4,0x16bf854e,0x16c7a08f,0x16c8f57a,
0x16cad7f2,0x16cda02f,0x16cf82a7,0x16d7928f,0x16d8f4e2,0x16dbc7e2,0x16dc923f,0x16dcb02e,
0x16df832e,0x16fad4c2,0x16fbc54a,0x16fcb2a4,0x16fda32c,0x178ac36f,0x178ac3f6,0x178ca56f,
0x178ca5f6,0x178fa5c6,0x178fc3a6,0x17a8e36d,0x17a8e3f4,0x17a9f46b,0x17a9f4e3,0x17adb02f,
0x17ae854f,0x17ae85d6,0x17c8e56b,0x17c8e5f2,0x17ce832f,0x17ce83b6,0x17eab4d3,0x17eac54b,
0x17eac5d2,0x17eca32d,0x17eca3b4,0x17edb4a3,0x186e79bc,0x186e79da,0x186ed35c,0x187a69fc,
0x187af06c,0x187c69fa,0x187cf06a,0x187df269,0x187f69ac,0x187f69ca,0x187fd04b,0x18ef602d,
0x18ef604b,0x18fb704d,0x18fc703d,0x18fe435c,0x18fe523d,0x18fe702c,0x18fe704a,0x196af07b,
0x19eca52b,0x19efa528,0x1a4c79be,0x1a4d68eb,0x1a4d86e9,0x1a4e97d8,0x1a6bc04f,0x1a6c7bf8,
0x1a6f48cb,0x1a7d6be8,0x1a7db02f,0x1a7e389f,0x1a7f498e,0x1acb604f,0x1acd602f,0x1acf426b,
0x1adb524f,0x1adbc748,0x1adc523f,0x1adc702e,0x1ade347b,0x1ade920c,0x1adf432e,0x1adf830c,
0x1afc7268,0x1afd632c,0x1b4c69af,0x1b4c69fa,0x1b4dc3a8,0x1b4f69ca,0x1b4fc36a,0x1b6e498f,
0x1b6e49da,0x1bce432f,0x1bce437a,0x1bec632d,0x1bec6378,0x1c2eb59a,0x1c6da02f,0x1c6f28ad,
0x1c7f298e,0x1cad602f,0x1caf246d,0x1cbf254e,0x1d2f69ac,0x1d2fa56c,0x1d6e298f,0x1d6e29bc,
0x1dae254f,0x1dae257c,0x1dae347b,0x1daf830c,0x1e3f5a8d,0x1e3f964d,0x1e5f4b8c,0x1e9f872a,
0x20d7e1ca,0x20dbe1c6,0x20dce17a,0x20dce1b6,0x20fce378,0x20fce3b4,0x20fec15a,0x20fec196,
0x21ca94db,0x21cdb6a9,0x21cde379,0x21cde3b5,0x21ced05b,0x21ced097,0x21dcf378,0x21dcf3b4,
0x21dfc04b,0x21dfc087,0x21e5c3f9,0x21e5f0c9,0x21e9c3f5,0x21e9f0c5,0x21ebf4c3,0x21ecf059,
0x21ecf095,0x21efb087,0x21efc359,0x21efc395,0x21f6b5da,0x21f7e08b,0x21f9e06b,0x21fa97d8,
0x21fd86a9,0x21fda46b,0x21fde049,0x21fde085,0x21fed358,0x21fed394,0x23c5f0e7,0x23cef057,
0x23def156,0x249bd0c7,0x249db67c,0x24b596fc,0x24b5a7ec,0x24b5f0e7,0x24b785ce,0x24b9f0c5,
0x24bcf095,0x24bef057,0x24bf965c,0x24d9f678,0x24d9f6e1,0x24df901e,0x24df9087,0x24fbd658,
0x24fbd6c1,0x24fdb01c,0x24fdb085,0x258bc1d7,0x258cb67d,0x25b7a48f,0x25b8f1d4,0x25b9a46f,
0x25bf864d,0x25c7908f,0x25c8f679,0x25c9e7f1,0x25ce901f,0x25cf8197,0x25e8f4d1,0x25eb704f,
0x25ebc7d1,0x25ec703f,0x25ecb01d,0x25ed613f,0x25ef831d,0x25efa10c,0x25f9e4c1,0x25fbc649,
0x25fcb194,0x25fe931c,0x269bf45a,0x269bf4c3,0x269fb01e,0x269fb087,0x26d8b4f3,0x26dfb41a,
0x26dfb483,0x2789c3f5,0x278c965f,0x278ce3b4,0x278ec196,0x278fc395,0x2798d3f4,0x279d864f,
0x27c8d65b,0x27c8d6f1,0x27cd831f,0x27cd83b5,0x27cda10e,0x27cf830e,0x27d9c64b,0x27d9c6e1,
0x27dc931e,0x27dc93b4,0x285d7abc,0x28795afc,0x28796bec,0x287b49ce,0x287bf45a,0x287cf059,
0x287f5a9c,0x287fb01e,0x28df501e,0x28df504b,0x28f9706b,0x28fd346b,0x28fd701c,0x28fd7049,
0x28fe701b,0x294c7abd,0x296c38bf,0x297f4a8d,0x29cb504f,0x29ce501f,0x29cf415b,0x29ec701d,
0x29ef431d,0x29ef610c,0x29fc7158,0x29fe531c,0x2adc961b,0x2adf9618,0x2b4c5a9f,0x2b4ce378,
0x2b4e785f,0x2b4ec15a,0x2b4fc359,0x2b5d4a8f,0x2bcd431f,0x2bcd4379,0x2bcd610e,0x2bcf430e,
0x2bdc531e,0x2bdc5378,0x2c1db6a9,0x2c3e785f,0x2c5e901f,0x2c5f189e,0x2c7da10e,0x2c7f1a8d,
0x2c9e501f,0x2c9f145e,0x2cbd610e,0x2cbe341f,0x2cbf164d,0x2d4e189f,0x2d6f3c8b,0x2d6fa51b,
0x2d7e1b9c,0x2d8e145f,0x2daf8719,0x2dbe175c,0x2e1f5a9c,0x2e1f965c,0x30cde269,0x30cde2a5,
0x30ced15a,0x30ced196,0x30db85ca,0x30dca7b8,0x30dcf268,0x30dcf2a4,0x30dfc14a,0x30dfc186,
0x30e7a4cb,0x30eb86c9,0x30ec97b8,0x30ecb57a,0x30ecf158,0x30ecf194,0x30efc249,0x30efc285,
0x30f4d2e8,0x30f4e1d8,0x30f5b4e9,0x30f8d2e4,0x30f8e1d4,0x30fae5d2,0x30fde148,0x30fde184,
0x30fea196,0x30feb459,0x30fed248,0x30fed284,0x31c4d2f9,0x31c8d2f5,0x31cfd249,0x31cfd285,
0x31e4f0d7,0x31e6f0d5,0x31edf047,0x31edf065,0x32cfe047,0x32d4e1f6,0x32d596eb,0x32d9f6e1,
0x32de965b,0x32df9087,0x32dfe146,0x349ad0c6,0x349da76c,0x34a9e0c5,0x34ae975c,0x34b6f0d5,
0x34bdf065,0x34d6819e,0x34d6f897,0x34d8f6e0,0x34d9706f,0x34d9e768,0x34de701f,0x34de9086,
0x34df810e,0x34e582ad,0x34e8f5d0,0x34ead758,0x34eda085,0x34ef820d,0x34f5e9a6,0x34f9e5c0,
0x34fa615e,0x34fad6c0,0x34fc702e,0x34fc921d,0x34fd612e,0x34fda10c,0x34fe920c,0x358ac1d6,
0x358ca76d,0x358db0a7,0x35a8e1d4,0x35a9f6e1,0x35ade184,0x35ae874d,0x35af9087,0x35afe146,
0x35c8e769,0x35c8e7f0,0x35ce810f,0x35ce8196,0x35eac749,0x35eac7d0,0x35eca10d,0x35eca194,
0x35edb629,0x35edb6a1,0x35ef940b,0x3689c2e5,0x368c975e,0x3698d2e4,0x369d874e,0x369df047,
0x369ed284,0x36c8d75a,0x36c8d7f0,0x36cd820f,0x36cd82a5,0x36d9c74a,0x36d9c7e0,0x36db504f,
0x36dc920e,0x36dc92a4,0x36de501f,0x378ae5d2,0x378ea196,0x37c9a5e2,0x37cea50b,0x37cea592,
0x385a7cdb,0x385d6bac,0x386e5b9c,0x38796dea,0x387d29ae,0x38da415e,0x38de504a,0x38df410e,
0x38e9426d,0x38ed6049,0x38ef420d,0x38fa7059,0x38fc521d,0x38fd610c,0x38fd7029,0x38fe520c,
0x394c6bad,0x396d784f,0x396de148,0x396e4b8d,0x39ce410f,0x39ce415a,0x39ec257a,0x39ec610d,
0x39ec6158,0x39ef610a,0x3a4c5b9e,0x3a5d4b8e,0x3a5e189f,0x3a5ed248,0x3a5f694e,0x3acd420f,
0x3acd4269,0x3adc520e,0x3adc5268,0x3ade165b,0x3b4d5a6f,0x3bcd870a,0x3bce8709,0x3c1f5a8d,
0x3c1f964d,0x3c5f098e,0x3c6f0a8d,0x3c7e2d9a,0x3c7eb40a,0x3c9f054e,0x3caf064d,0x3cbda508,
0x3cbe9608,0x3d2e189f,0x3d2eb459,0x3d2f694e,0x3d4e098f,0x3d4e701f,0x3d4f810e,0x3d6e0b9c,
0x3d6e501f,0x3d8e054f,0x3d8f410e,0x3dae075c,0x3daf250e,0x3e4f820d,0x3e5f940b,0x3e8f420d,
0x40f9d678,0x40fd923c,0x41e2c3f8,0x41e3a5f9,0x41e3c7d9,0x41e7839d,0x41e7f8a5,0x41e9f0a3,
0x41eaf093,0x41ef702d,0x41efa539,0x41efc328,0x41f3e0c7,0x41fbe083,0x41fde027,0x41feb538,
0x42d396fa,0x42d7f896,0x42d9f0a3,0x42daf093,0x42df701e,0x42df963a,0x42f3d0c7,0x42f583ac,
0x42fac758,0x42fbd083,0x42fdb638,0x42fe831c,0x42fed017,0x43c9617f,0x43ca527f,0x43d8f1b2,
0x43df862b,0x43dfc209,0x43e8f2b1,0x43ef851b,0x43f9e2a1,0x43fad192,0x43fda629,0x43fe951a,
0x45af872c,0x479cf136,0x479f860d,0x47acf235,0x48bf301e,0x48bf302d,0x497d682f,0x497ed318,
0x49ad302f,0x49ae301f,0x49af213d,0x4a5fc328,0x4a7e581f,0x4a9d302f,0x4a9e301f,0x4a9f123e,
0x4b8d213f,0x4b8e123f,0x4c3f701e,0x4c3f702d,0x4d2fa539,0x4d3e971c,0x4e1f872c,0x4e1f963a,
0x50eaf192,0x50efa429,0x50f2b4e8,0x50f6e9b4,0x50f8e1b2,0x50fbe182,0x50fe613c,0x50feb428,
0x51e6f0b3,0x51ebf063,0x52c9e0a3,0x52ce973a,0x52d3cbe6,0x52d6f0b3,0x52db436e,0x52dbf063,
0x52e384cb,0x52e8f3b0,0x52ebc083,0x52ecb738,0x52ef840b,0x52f9e3a0,0x52fe940a,0x53c8e1b2,
0x53cbe182,0x53ce872b,0x53eac192,0x53eca729,0x53efc106,0x56bd302f,0x56bde324,0x56be301f,
0x58bc213e,0x58be302c,0x58bf210e,0x59ae210f,0x59ae213c,0x5a9c302e,0x5a9f032e,0x5b6d302f,
0x5b6e301f,0x5b6f490e,0x5b8c213e,0x5b8e032f,0x5b8f210e,0x5c3eb428,0x5d2e613c,0x5e2f840b,
0x60f5dab4,0x60fd523c,0x61e3cbd5,0x61eb435d,0x61f5e0a3,0x61fbe043,0x63d4f1b2,0x63daf152,
0x63dfc205,0x64bf301e,0x65ad213f,0x65bed314,0x6a5f301e,0x6b4d213f,0x6b5f4a0d,0x6d3e5b1c
};

void putCenter4x4(int **x, int **b, const int o, const int n) {
//   ------------
  int code=code4x4[random_(num4x4)]; const int Msum=34; // 4*(4*4+1)/2;

  x[2][2]=(code&0xf)+1; code>>=4; x[2][0]=(code&0xf)+1; code>>=4;
  x[1][2]=(code&0xf)+1; code>>=4; x[1][1]=(code&0xf)+1; code>>=4;
  x[1][0]=(code&0xf)+1; code>>=4; x[0][2]=(code&0xf)+1; code>>=4;
  x[0][1]=(code&0xf)+1; code>>=4; x[0][0]=(code&0xf)+1;

  x[0][3]=Msum-x[0][0]-x[0][1]-x[0][2]; x[1][3]=Msum-x[1][0]-x[1][1]-x[1][2];
  x[3][0]=Msum-x[0][0]-x[1][0]-x[2][0]; x[3][2]=Msum-x[0][2]-x[1][2]-x[2][2];
  x[3][3]=Msum-x[0][0]-x[1][1]-x[2][2]; x[3][1]=Msum-x[3][0]-x[3][2]-x[3][3];
  x[2][1]=Msum-x[0][1]-x[1][1]-x[3][1]; x[2][3]=Msum-x[2][0]-x[2][1]-x[2][2];

  for (int i=0; i<4; i++) for (int j=0; j<4; j++)
    b[i+o][j+o]=x[i][j]-(x[i][j]>8 ? 8 : 9); // (4*4+1)/2; (8.5)
  Turn(x, b, o, n);
} // putCenter4x4

void makeEven(int **x, int **b, const int size) {
//   --------
  int v=9; // (4*4+1)/2; (8.5)

  // fill center 4x4
  int o=(size-4)/2, n=o+3; putCenter4x4(xSquare, b, o, n);  
  for (int i=6; i<=size; i+=2) {
    int c=0, r=0; o=(size-i)/2;  n=o+i-1;  
    if (i % 4!=0) { //------------------------------   // singly even
      const int k=(i-2)/4;
      int j=k; while (j--) { top[c++]=-v++; top[c++]=v++; }
      top[c++]=-v++; left[r++]=-v++;
      j=k-1; while (j--) { left[r++]=v++; left[r++]=-v++; }
      b[n][n]=-v; b[o][o]=v++; /* NW */ b[n][o]=-v; b[o][n]=v++; // NE
      left[r++]=v++;
      j=k-1; while (j--) { left[r++]=-v++; left[r++]=v++; }
      left[r++]=v++; top[c++]=-v++;
      j=k-1; while (j--) { top[c++]=v++; top[c++]=-v++; } left[r++]=-v++;
    } else { //---------------------------------------   // doubly even
      top[c++]=-v++; const int k=(i-4)/4;
      int j=k; while (j--) { top[c++]=v++; top[c++]=-v++; }
      if (i==8) {
        left[r++]=v++;
      } else {
        left[r++]=-v++; left[r++]=v++;
        j=k-2; while (j--) { left[r++]=-v++; left[r++]=v++; } left[r++]=v++;
      }
      left[r++]=-v++; left[r++]=-v++;
      b[n][n]=-v; b[o][o]=v++; /* NW */ b[n][o]=-v; b[o][n]=v++; // NE
      left[r++]=v++; left[r++]=v++;
      j=k-1; while (j--) { left[r++]=-v++; left[r++]=v++; } left[r++]=-v++;
      j=k; while (j--) { top[c++]=-v++; top[c++]=v++; } top[c++]=-v++;
    } // if (i % 4!=0)
    putBorder(x, b, o, n);
  } // for (i=6; ...
  biggestValue=v-1; makeActual(x, size);
}  // makeEven
//=========================================== odd ============================================

void makeOddAbulWafa(int **x, int **b, const int size) {
//   ---------------
  int v=1; const int m=(size-1)/2; b[m][m]=0; Turn(x, b, m, m);
  for (int i=3; i<=size; i+=2) {
    int c=0, r=0, o=(size-i)/2, n=o+i-1, k=(i-1)/2, j=k-1;
    b[n][o]=v; b[o][n]=-v++; /* NE */ left[r++]=v++;
    b[n][n]=v; b[o][o]=-v++; /* NW */
    while (j--) { left[r++]=v++; top[c++]=-v++; } top[c++]=v++; 
    j=k-1; while (j--) { top[c++]=v++; left[r++]=-v++; }
    putBorder(x, b, o, n);
  }
  biggestValue=v-1;
} // makeOddAbulWafa

void makeOddSeki(int **x, int **b, const int size) {
//   -----------
  int v=1; const int m=(size-1)/2; b[m][m]=0; Turn(x, b, m, m);
  for (int i=3; i<=size; i+=2) {
    int c=0, r=0, o=(size-i)/2, n=o+i-1, k=(i-1)/2, j=k-1;
    b[n][o]=-v; b[o][n]=v++; /* NE */ while (j--) top[c++]=v++;
    j=k; while (j--) left[r++]=-v++; if (i>3) left[r++]=v++;
    j=k-1; while (j--) top[c++]=-v++;
    if (i>3) { j=k-2; while (j--) left[r++]=v++; }
    b[n][n]=-v; b[o][o]=v++; /* NW */ top[c++]=-v++;
    putBorder(x, b, o, n);
  }
  biggestValue=v-1;
} // makeOddSeki

void makeOddStifel(int **x, int **b, const int size) {
//   -------------
  int v=1; const int m=(size-1)/2; b[m][m]=0; Turn(x, b, m, m);
  for (int i=3; i<=size; i+=2) {
    int c=0, r=0, o=(size-i)/2, n=o+i-1, k=(i-1)/2, j=k-1;
    b[n][n]=v; b[o][o]=-v++; /* NW */
    while (j--) { top[c++]=-v++; left[r++]=-v++; } left[r++]=-v++;
    j=k-1; while (j--) { left[r++]=v++; top[c++]=v++; } 
    b[n][o]=v; b[o][n]=-v++; /* NE */ top[c++]=v++;
    putBorder(x, b, o, n);
  }
  biggestValue=v-1;
} // makeOddStifel

void makeOddTravers(int **x, int **b, const int size) {
//   --------------
  int v=1; const int m=(size-1)/2; b[m][m]=0; Turn(x, b, m, m);
  for (int i=3; i<=size; i+=2) {
    int c=0, r=0, o=(size-i)/2, n=o+i-1, k=(i-1)/2, j=k-1;
    while (j--) left[r++]=-v++; b[n][o]=-v; b[o][n]=v++;       /* NE */
    j=k-1; while (j--) top[c++]=v++; left[r++]=-v++;
    j=k-1; while (j--) left[r++]=v++; b[n][n]=-v; b[o][o]=v++; /* NW */
    j=k; while (j--) top[c++]=-v++;
    putBorder(x, b, o, n);
  }
  biggestValue=v-1;
} // makeOddTravers

void makeOddWhite(int **x, int **b, const int size) {
//   ------------
  int v=1;

  const int m=(size-1)/2; b[m][m]=0; Turn(x, b, m, m);
  for (int i=3; i<=size; i+=2) {
    int c=0, r=0, o=(size-i)/2, n=o+i-1, k=(i-3)/2, j=k;
    while (j--) { top[c++]=v++; left[r++]=-v++; }
    b[n][o]=-v; b[o][n]=v++; /* NE */ left[r++]=-v++;
    b[n][n]=-v; b[o][o]=v++; /* NW */ top[c++]=-v++;
    j=k; while (j--) { top[c++]=-v++; left[r++]=v++; }
    putBorder(x, b, o, n);
  }
  biggestValue=v-1;
} // makeOddWhite

void makeOdd(int **x, int **b, const int size, const int kind) {
//   -------
  switch (kind) {
    case 1: makeOddAbulWafa(x, b, size); break;
    case 2: makeOddSeki(x, b, size);     break;
    case 3: makeOddStifel(x, b, size);   break;
    case 4: makeOddTravers(x, b, size);  break;
    case 5: makeOddWhite(x, b, size);    break;
    default: printf("\aProgran error: Unknown kind %d\n", kind); return;
  }
  makeActual(x, size);
} // makeOdd
//====================================== make squares =======================================

const char *notMagic=
  "\a\nERROR: Square is NOT magic! Please report by email\n";
const char *notBordered=
  "\a\nERROR: Square is NOT bordered! Please report by email\n";

bool makeSquares(const int n, const int kind) {
//   -----------
  int **x=xSquare, **b=bSquare;
  if ((n&1)==0) makeEven(x, b, n); else makeOdd(x, b, n, kind);
  if (isCorrect(x, n)) { if (!isBordered(x, n)) printf("%s",notBordered); }
  else printf("%s",notMagic);
  return putSquare(x, n);
} // makeSquares
//========================================== input ==========================================

void clearLine(int c) { while (c!='\n') c=getchar(); }
//   ---------

bool getY() {
//   ----
  int c;  do { c=getchar(); } while ((c==' ')|(c=='\t')|(c=='\n'));
  clearLine(c); return (c=='Y')|(c=='y');
}

bool getYorOrder(int *n) {
//   -----------
  bool result=F; int c; *n=0;

  do { c=getchar(); } while ((c==' ')|(c=='\t')|(c=='\n') );
  if ( (c=='Y')|(c=='y') ) result=T;
  else if ( (c!='N')&(c!='n') )
    if ( ('1'<=c)&(c<='9') ) {
      int i=c-'0'; while ( ('0'<=(c=getchar()))&&(c<='9') ) i=i*10+c-'0'; *n=i; result=T;
    }   
  clearLine(c); return result;
} // getYorOrder

int getInt() { int n=0; scanf("%d", &n); clearLine(getchar()); return n; }
//  ------
//========================================== output ==========================================

const int bufSize=1024;
bool openDir() {
//   -------
  char buf[bufSize], msg[bufSize+50]; const char *baseName="./BorderedSquares";
  strcpy(buf, baseName); int sub=0;

  do {
    if (mkdir(buf, 0775)==0) break;
    if (errno!=EEXIST) {
      snprintf(msg, bufSize+50, "Can't make folder %s", buf); perror(msg); return F;
    }
    snprintf(buf, bufSize, "%s_%d", baseName, ++sub);
  } while (T);
  if (chdir(buf)!=0) {
    snprintf(msg, bufSize+50, "Can't open folder %s", buf); perror(msg); return F;
  }
  printf("Output files are in folder %s\n", buf); return T;
} // openDir

FILE *open_File(const int n) {
//    ---------
  char buf[bufSize]; FILE *wfp=NULL; snprintf(buf, bufSize, "./Order%d.txt", n);
  if ((wfp=fopen(buf, "a"))==NULL) {
    char msg[bufSize+50]; snprintf(msg, bufSize+50, "\a\nCan't open for write %s", buf); perror(msg);
  }
  return wfp; 
} // open_File
//========================================== main ========================================

bool validOrder(const int n) {
//   ----------
  switch (n) {
  case 1: case 4:
    printf("There is no bordered magic square of order %i.\n"
           "Making normal magic.\n", n); return T;
  case 2:
    printf("\aERROR: There is no magic square of order 2.\n"); return F;
  default:
    if (n<=0) {
      printf("\aERROR: N must be a positive integer.\n"); return F;
    } else return T;
  }
}// validOrder

int inputKind(const int n) {
//  ---------
  int k=5;
  if ((n>3)&((n&1)!=0)) {
    printf("Method, (1 Abu'l-Wafa al-Buzjani, 2 Seki, 3 Stifel, 4 Travers, 5 White)? ");
    k=getInt(); if (k<1) k=1; else if (k>5) k=5;
  }
  return k;
} // inputKind

int main() {
//  ----
  bool another=T, inputSize=T, writeError=F, ok=F; seed_rand();

  if (openDir()) {
    int n=0;
    do {     
      if (inputSize)
        { printf("\nInput the order of the square: "); n=getInt(); }
      if (validOrder(n)) {
	if (allocateStore(n)) {
	  FILE *wfp=NULL;
          if ( (wfp=open_File(n))!=NULL) {
            int kind=inputKind(n); Sindex=0; sLen=n*n;
            int howMany=1; if (n>3) { printf("\nHow many? "); howMany=getInt(); }
            int loop=max(howMany,1000000); 
            while (loop--) {
              ok=makeSquares(n, kind); if (!ok) break; if (Sindex==howMany) break;
            }
            if (ok) writeError=!outputSquares(n, wfp); fclose(wfp);
	  }
        } else printf("\a\nERROR: Storage allocation failed.\n");
      }
      if (writeError) {
        perror("\a\nError writing file"); another=F;
      } else {
        printf("\nMake another square? "
          "input y (yes) or n (no) or the order of the square: ");
        if (getYorOrder(&n)) inputSize=(n==0); else another=F;
      }
    } while (another);
  }
  freeStore(); printf("\nHit return to close the console.");
  while (T) if (getchar()=='\n') break; return ok ? EXIT_SUCCESS : EXIT_FAILURE;
} // main