/*
 *  File:    Franklin8.cpp
 *  Author:  S Harry White
 *  Created: 2013-11-05
 *  Updated: 2022-01-02
 *    Tidy code.
 *  Updated: 2023-01-02
 *    Change to compile with g++ on macOS.
 */

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

#define N 8
#define Nd2 N/2
#define Nd2m1 Nd2-1
#define NN N*N
#define NNd2 NN/2
const int
// square numbers 0 to NN-1
          S2=NN-1,       //  63
          S4=S2+S2,      // 126
          S8=S4+S4,      // 252
          squareVariations=4096;
#define maxX2X4X6Combos 225
int numX2X4X6Combos, countMagic, countSemiMagic;
typedef unsigned int Uint; Uint X2X4X6Combos[maxX2X4X6Combos][Nd2m1];
const bool F=false, T=true; struct bools { bool used[NN]; }; struct bools allfree;
//============================================= output ==============================================

#define bufSize 1024
bool openDir(char *dir) {
//   -------
  char baseName[bufSize]="./Order8Franklin"; int sub=0; strcpy(dir, baseName);
  do {
    if (mkdir(dir,0775)!=-1) break;
    if (errno!=EEXIST) {
      char msg[bufSize+50]; snprintf(msg, bufSize+50, "\a\nCan't make folder %s", dir); perror(msg); return F;
    }
    snprintf(dir, bufSize, "%s_%d", baseName, ++sub);
  } while (T);
  printf("Output files are in folder %s\n", dir); return T;
} // openDir

int openWrite(char *dir, const char *prefix) {
//  ---------
  char fName[bufSize]; int wfd=-1; snprintf(fName, bufSize, "%s/%sSquares.txt", dir, prefix);
  wfd=open(fName, O_CREAT|O_WRONLY);
  if (wfd==-1) {
    char msg[bufSize+50]; snprintf(msg, bufSize+50, "\a\nCan't open for write %s", fName); perror(msg);
  } else chmod(fName, 0644);
  return wfd;
} // openWrite


#define bytesPerSquare 193
#define numMagic 368640
#define numSemiMagic numMagic+numMagic              //    737280
#define sizeMagic numMagic*bytesPerSquare           //  71147520
//#define sizeSemiMagic numSemiMagic*bytesPerSquare //  71516160 gcc, g++ compiler bug
#define sizeSemiMagic sizeMagic+sizeMagic           // 142295040
char bufferMagic[sizeMagic], bufferSemiMagic[sizeSemiMagic],
     *sMagic=bufferMagic, *sSemiMagic=bufferSemiMagic, *sActive=NULL;

void writeSquares(const int wfdM, const int wfdSM) {
//   ------------
  if (write(wfdM, bufferMagic, sizeMagic)!=sizeMagic) perror("Error writing magic squares: ");
  if (write(wfdSM, bufferSemiMagic, sizeSemiMagic)!=sizeSemiMagic) perror("Error writing semimagic squares: ");
} // writeSquares

void printSquare(Uint **x) {
//   -----------
  char *s=sActive;
  for (int r=0; r<N; ++r) {
    for (int c=0; c<N; ++c) {
      const Uint v=x[r][c]; if (c!=0) *s++=' ';
      if (v<10) { *s++=' '; *s++=v+'0'; } else { *s++=v/10+'0'; *s++=v%10+'0'; }
    }
    *s++='\n';
  }
  *s++='\n'; sActive=s;
} // printSquare
//=================================================== make =============================================

void getX2X4X6Combos() {
//   ---------------
  struct bools v=allfree; numX2X4X6Combos=0;
  for (int i=1; i<NNd2; i++) {
    v.used[i]=T;
    for (int j=1; j<(NNd2-1); j++) if (!v.used[j]) {
      for (int k=j+1; k<NNd2; k++) if (!v.used[k]) {
        if (i==(j+k)) { Uint *p=X2X4X6Combos[numX2X4X6Combos++]; p[0]=i; p[1]=j; p[2]=k; }
      }
    }
    v.used[i]=F;
  }
} // getX2X4X6Combos

void swapRows(Uint **x, const int a, const int b) { Uint *tmp=x[a]; x[a]=x[b]; x[b]=tmp; printSquare(x); }
//   --------

void swapCols(Uint **x, const int a, const int b) {
//   --------
  for (int r=0; r<N; ++r) { const Uint tmp=x[r][a]; x[r][a]=x[r][b]; x[r][b]=tmp; } printSquare(x);
} // swapCols

void swapSideRows(Uint **x, int a, int b, const bool print) {
//   ------------
  int loop=2; while(loop--) { Uint *tmp=x[a]; x[a]=x[b]; x[b]=tmp; a+=2; b+=2; }
  if (print) printSquare(x);
} // swapSideRows

void swapSideCols(Uint **x, int a, int b, const bool print) {
//   ------------
  int loop=2;
  while(loop--) {
    for (int r=0; r<N; ++r) { const Uint tmp=x[r][a]; x[r][a]=x[r][b]; x[r][b]=tmp; } a+=2; b+=2;
  }
  if (print) printSquare(x);
} // swapSideCols

void swapCols46(Uint **x) { swapCols(x, 5, 7); swapCols(x, 4, 6); swapCols(x, 5, 7); }
//   ----------

void swapCols13(Uint **x) { swapCols46(x); swapCols(x, 1, 3); swapCols46(x); }
//   ----------

void swapCols02(Uint **x) { swapCols13(x); swapCols(x, 0, 2); swapCols13(x); }
//   ----------
  
void swapRows57(Uint **x) { swapCols02(x); swapRows(x, 5, 7); swapCols02(x); }
//   ----------

void swapRows46(Uint **x) { swapRows57(x); swapRows(x, 4, 6); swapRows57(x); }
//   ----------

void swapRows13(Uint **x) { swapRows46(x); swapRows(x, 1, 3); swapRows46(x); }
//   ----------

void swapRows02(Uint **x) { swapRows13(x); swapRows(x, 0, 2); swapRows13(x); }
//   ----------

void swapCols1357(Uint **x) { swapSideCols(x, 1, 5, T); swapRows02(x); swapSideCols(x, 1, 5, F); }
//   ------------

void swapCols0246(Uint **x) {
//   ------------
  swapSideCols(x, 0, 4, T); swapRows02(x); swapCols1357(x); swapSideCols(x, 0, 4, F);
} // swapCols0246

void swapRows1357(Uint **x) {
//   ------------
  swapSideRows(x, 1, 5, T); swapRows02(x); swapCols0246(x); swapCols1357(x); swapSideRows(x, 1, 5, F);
} // swapRows1357

void swapRows0246(Uint **x) {
//   ------------
  swapSideRows(x, 0, 4, T); swapRows02(x); swapRows1357(x); swapCols0246(x); swapCols1357(x); swapSideRows(x, 0, 4, F);
} // swapRows0246

void swapSides(Uint **x) { swapRows0246(x); swapRows1357(x); swapCols0246(x); swapCols1357(x); }
//   ---------

void printVariations(Uint **x) { printSquare(x); swapRows02(x); swapSides(x); }
//   ---------------

bool isMagic;
Uint xCopy[N][N],
     *xRows[N]={ xCopy[0], xCopy[1], xCopy[2], xCopy[3], xCopy[4], xCopy[5], xCopy[6], xCopy[7] };
void printSquares(Uint x[NN]) {
//   ------------
  Uint *p=x;
  for (int r=0; r<N; ++r) for (int c=0; c<N; ++c) { const Uint v=*p++; xCopy[r][c]=(r+c)&1 ? S2+1-v : v+1; }
  if (isMagic) { sActive=sMagic; countMagic+=squareVariations; }
  else { sActive=sSemiMagic; countSemiMagic+=squareVariations; }
  printVariations(xRows); if (isMagic) sMagic=sActive; else sSemiMagic=sActive;
} // printSquares

void extendX40X56(Uint x[NN], bool used[NN]) {
//   ------------
  Uint maxx56=x[16]-1;
  for (x[56]=(x[16]>>1)+1; x[56]<=maxx56; ++x[56])
    if (!used[S2-x[56]]) { x[57]=x[1]+x[56];
    if (!used[x[57]]) { x[59]=x[3]+x[56];
    if (!used[x[59]]) { x[61]=x[5]+x[56];
    if (!used[x[61]]) { x[63]=x[7]+x[56]; 
    if (!used[x[63]]) {
      used[S2-x[56]]=T; used[x[57]]=T; used[x[59]]=T; used[x[61]]=T; used[x[63]]=T; x[58]=x[2] +x[56];
    if (!used[S2-x[58]]) { x[60]=x[4] +x[56];
    if (!used[S2-x[60]]) { x[62]=x[6] +x[56];
    if (!used[S2-x[62]]) { used[S2-x[58]]=T; used[S2-x[60]]=T; used[S2-x[62]]=T; x[40]=x[16]-x[56];
    if ((x[40]<x[56])&&(x[40]>x[8])&&!used[S2-x[40]]) { x[41]=x[1]+x[40];
    if (!used[x[41]]) { x[43]=x[3]+x[40];
    if (!used[x[43]]) { x[45]=x[5]+x[40];
    if (!used[x[45]]) { x[47]=x[7]+x[40];
    if (!used[x[47]]) { used[S2-x[40]]=T; used[x[41]]=T; used[x[43]]=T; used[x[45]]=T; used[x[47]]=T; x[42]=x[2] +x[40]; 
    if (!used[S2-x[42]]) { x[44]=x[4] +x[40]; 
    if (!used[S2-x[44]]) { x[46]=x[6] +x[40];
    if (!used[S2-x[46]]) printSquares(x); }}
      used[S2-x[40]]=F; used[x[41]]=F; used[x[43]]=F; used[x[45]]=F; used[x[47]]=F; }}}}}    
      used[S2-x[58]]=F; used[S2-x[60]]=F; used[S2-x[62]]=F; }}} used[S2-x[56]]=F;
      used[x[57]]=F; used[x[59]]=F; used[x[61]]=F; used[x[63]]=F; }}}}
  }   
} // extendX40X56

void extendX5X7 (Uint x[NN], bool used[NN]) {
//   ----------
  const Uint maxx7=x[2]-1;
  for (x[7]=(x[2]>>1)+1; x[7]<=maxx7; ++x[7])
    if (!used[S2-x[7]]) { x[15]=x[8]+x[7];
    if (!used[x[15]]) { x[31]=x[24]+x[7];
    if (!used[x[31]]) { used[S2-x[7]]=T; used[x[15]]=T; used[x[31]]=T; x[23]=x[7]+x[16];
    if (!used[S2-x[23]]) { x[39]=x[7]+x[32];
    if (!used[S2-x[39]]) { x[55]=x[7]+x[48];
    if (!used[S2-x[55]]) { used[S2-x[23]]=T; used[S2-x[39]]=T; used[S2-x[55]]=T; x[5]=x[2]-x[7];
    if ((x[5]>x[1])&&(x[5]<x[7])&&!used[S2-x[5]]) { x[13]=x[8]+x[5];
    if (!used[x[13]]) { x[29]=x[24]+x[5];
    if (!used[x[29]]) { used[S2-x[5]]=T; used[x[13]]=T; used[x[29]]=T; x[21]=x[5]+x[16];
    if (!used[S2-x[21]]) { x[37]=x[5]+x[32];
    if (!used[S2-x[37]]) { x[53]=x[5]+x[48];
    if (!used[S2-x[53]]) { used[S2-x[21]]=T; used[S2-x[37]]=T; used[S2-x[53]]=T; extendX40X56(x, used); 
      used[S2-x[21]]=F; used[S2-x[37]]=F; used[S2-x[53]]=F; }}}
      used[S2-x[5]]=F; used[x[13]]=F; used[x[29]]=F; }}} used[S2-x[23]]=F; used[S2-x[39]]=F;
      used[S2-x[55]]=F; }}} used[S2-x[7]]=F; used[x[15]]=F; used[x[31]]=F; }}
  }
} // extendX5X7

void extendX8X24(Uint x[NN], bool used[NN]) {
//   -----------
  for (x[24]=(x[16]>>1)+1; x[24]<=x[16]; ++x[24])
    if (!used[S2-x[24]]) { x[25]=x[1]+x[24];
    if (!used[x[25]]) { x[27]=x[3]+x[24];
    if (!used[x[27]]) { used[S2-x[24]]=T; used[x[25]]=T; used[x[27]]=T; x[26]=x[2] +x[24];
    if (!used[S2-x[26]]) { x[28]=x[4] +x[24];
    if (!used[S2-x[28]]) { x[30]=x[6] +x[24];
    if (!used[S2-x[30]]) { used[S2-x[26]]=T; used[S2-x[28]]=T; used[S2-x[30]]=T; x[8]=x[16]-x[24];
    if ((x[8]<x[24])&&!used[S2-x[8]]) { x[9]=x[1]+x[8];
    if (!used[x[9]]) { x[11]=x[3]+x[8];
    if (!used[x[11]]) { used[S2-x[8]]=T; used[x[9]]=T; used[x[11]]=T; x[10]=x[2] +x[8];
    if (!used[S2-x[10]]) { x[12]=x[4] +x[8];
    if (!used[S2-x[12]]) { x[14]=x[6] +x[8];
    if (!used[S2-x[14]]) { used[S2-x[10]]=T; used[S2-x[12]]=T; used[S2-x[14]]=T; extendX5X7(x, used);
      used[S2-x[10]]=F; used[S2-x[12]]=F; used[S2-x[14]]=F; }}} used[S2-x[8]]=F; used[x[9]]=F; used[x[11]]=F; }}}
      used[S2-x[26]]=F; used[S2-x[28]]=F; used[S2-x[30]]=F; }}} used[S2-x[24]]=F; used[x[25]]=F; used[x[27]]=F; }}
  }
} // extendX8X24

void extendX1X3(Uint x[NN], bool used[NN]) {
//   ----------
  for (x[3]=(x[2]>>1)+1; x[3]<=x[2]; ++x[3])
    if (!used[S2-x[3]]) { x[19]=x[3]+x[16];
    if (!used[S2-x[19]]) { x[35]=x[3]+x[32];
    if (!used[S2-x[35]]) { x[51]=x[3]+x[48];
    if (!used[S2-x[51]]) { used[S2-x[3]]=T; used[S2-x[19]]=T; used[S2-x[35]]=T; used[S2-x[51]]=T; x[1]=x[2]-x[3]; 
    if ((x[1]<x[3])&&!used[S2-x[1]]) { x[17]=x[1]+x[16];
    if (!used[S2-x[17]]) { x[33]=x[1]+x[32];
    if (!used[S2-x[33]]) { x[49]=x[1]+x[48];
    if (!used[S2-x[49]]) { used[S2-x[1]]=T; used[S2-x[17]]=T; used[S2-x[33]]=T; used[S2-x[49]]=T;
      extendX8X24(x, used); used[S2-x[1]]=F; used[S2-x[17]]=F; used[S2-x[33]]=F; used[S2-x[49]]=F; }}}}
      used[S2-x[3]]=F; used[S2-x[19]]=F; used[S2-x[35]]=F; used[S2-x[51]]=F; }}}
  }
} // extendX1X3

void extendX32X48(Uint x[NN], bool used[NN]) {
//   ------------
  const Uint maxx48=x[16]-1;
  for (x[48]=(x[16]>>1)+1; x[48]<=maxx48; ++x[48])
    if (!used[x[48]]) { x[50]=x[2] +x[48];
    if (!used[x[50]]) { x[52]=x[4] +x[48];
    if (!used[x[52]]) { x[54]=x[6] +x[48];
    if (!used[x[54]]) { used[x[48]]=T; used[x[50]]=T; used[x[52]]=T; used[x[54]]=T; x[32]=x[16]-x[48];
    if ((x[32]<x[48])&&!used[x[32]]) { x[34]=x[2] +x[32];
    if (!used[x[34]]) { x[36]=x[4] +x[32];
    if (!used[x[36]]) { x[38]=x[6] +x[32];
    if (!used[x[38]]) { used[x[32]]=T; used[x[34]]=T; used[x[36]]=T; used[x[38]]=T; extendX1X3(x, used);
      used[x[32]]=F; used[x[34]]=F; used[x[36]]=F; used[x[38]]=F; }}}}
      used[x[48]]=F; used[x[50]]=F; used[x[52]]=F; used[x[54]]=F; }}}
  }
} // extendX32X48

void extendX16(Uint x[NN], bool used[NN]) {
//   ---------
  const Uint maxx16=S2-x[2];
  for (x[16]=x[2]+1; x[16]<=maxx16; ++x[16])
    if (!used[x[16]]) { isMagic=(x[16]==maxx16); x[18]=x[2]+x[16];
    if (!used[x[18]]) { x[20]=x[4]+x[16];
    if (!used[x[20]]) { x[22]=x[6]+x[16];
    if (!used[x[22]]) { used[x[16]]=T; used[x[18]]=T; used[x[20]]=T; used[x[22]]=T; 
      extendX32X48(x, used); used[x[16]]=F; used[x[18]]=F; used[x[20]]=F; used[x[22]]=F; }}}
  }
} // extendX16

void getSquares() {
//   ----------
  getX2X4X6Combos(); struct bools v=allfree; Uint x[NN]; x[0]=0; v.used[0]=T;
  for (int i=0; i<numX2X4X6Combos; ++i) {
    Uint *p=X2X4X6Combos[i]; v.used[x[2]=p[0]]=T; v.used[x[4]=p[1]]=T;
    v.used[x[6]=p[2]]=T; extendX16(x, v.used); v.used[x[2]]=F; v.used[x[4]]=F; v.used[x[6]]=F;
  }
} // getSquares
//================================================= main =============================================

void outputLocalTime(FILE *wfp) {
//   ---------------
  time_t startTime=time(NULL); struct tm *local=localtime(&startTime);
  if (local!=NULL) {
    char dateTime[100]; size_t slen=strftime(dateTime, 100, "%A %Y-%m-%d %X %Z\n\n\0", local);
    fprintf(wfp, "\n%s", dateTime);
  }
} // outputLocalTime

void printElapsedTime(FILE *wfp, time_t startTime) {
//   ----------------
  const int et=(int)difftime(time(NULL), startTime);
  if (et>0) fprintf(wfp, "\nelapsed time %d:%02d:%02d\n", et/3600, et%3600/60, et%60);
} // printElapsedTime
          
int main() {
//  ----
  outputLocalTime(stdout); char dir[bufSize];
  if (openDir(dir)) {
    const int wfdM=openWrite(dir, "Magic"), wfdSM=openWrite(dir, "SemiMagic");
    if ((wfdM!=-1)&(wfdSM!=-1)) {
      time_t startTime=time(NULL); getSquares(); writeSquares(wfdM, wfdSM);
      printf("\nMagic Squares: %u Semi-magic Squares: %u\n", countMagic, countSemiMagic);
      printElapsedTime(stdout, startTime); close(wfdM); close(wfdSM);
    }
  }
  printf("\nHit return to close the console.");
  while (T) { if (getchar()=='\n') break; } return EXIT_SUCCESS;
} // main