/*
 *  File:    Order6CSample.cpp 
 *  Author:  S Harry White
 *  Created: 2009-08-06
 *  Updated: 2022-01-19
 *    Tidy code.
 *  Updated: 2023-01-31
 *    Change to compile with g++ for macOS.
 */

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

const bool F=false, T=true;
const int M=4,
          MM=M*M,          // 16

          N=6,
          NN=N*N,         //  36
          Half=NN/2,      //  18

// numbers 0 .. NN-1
          Sum2=NN-1,      //  35
          Sum4=Sum2+Sum2, //  70
          Sum6=Sum4+Sum2, // 105

//Partitions of 0 .. NN-1 as MM/2 pairs and other (NN-MM)/2 pairs.
          numPartitions=43758; // 18!/(8!10!)
//================================================== output ==============================================

int X[N][N];

FILE *openFile() {
//    --------
  FILE *wfp=NULL; int sub=0; const int bufSize=1024; char buf[bufSize];
  const char *baseName="./Order6ConcentricMagicSquares"; snprintf(buf, bufSize, "%s.txt", baseName);
  do {
    if (access(buf, F_OK)!=0) break; snprintf(buf, bufSize, "%s_%d.txt", baseName, ++sub);
  } while (T);
  if ((wfp=fopen(buf, "w"))==NULL) {
    char msg[bufSize+50]; snprintf(msg, bufSize+50, "\a\nCan't open for write %s", buf); perror(msg);
  } else printf("Output file is %s\n", buf);
  return wfp;
} // openFile

//bool isCorrect() {
////   ---------
//  const int chkSum=Sum6; 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-1-i]; sumYX+=X[i][i];
//  }
//  return ((sumXY==chkSum)&(sumYX==chkSum));
//} // isCorrect

bool outputSquare(FILE *wfp) {
//   ------------
  for (int row=0; row<N; row++) {
    if (fprintf(wfp, "%2d", X[row][0])<0) return F;
    for (int col=1; col<N; col++) if (fprintf(wfp, " %2d", X[row][col])<0) return F;
    if (fputc('\n', wfp)==EOF) return F; 
  }
  /* return isCorrect(); */ return fputc('\n', wfp)!=EOF;
 } // outputSquare
//============================================= make =======================================================

int Centers[numPartitions][MM], numCenters;

const int maxCenterCombos=86, maxCenterPermus=2064; // 86 x 4!
int CenterCombos[maxCenterCombos][M], numCenterCombos, CenterPermus[maxCenterPermus][M], numCenterPermus;

// Only CenterPermus in which third>second.
const int maxCenterGPermus=1032; int *CenterGPermus[maxCenterGPermus], numCenterGPermus;

// CenterGPermus indexed by the second and third numbers.
const int maxCenterGPermus23=14;
int *CenterGPermus23[NN][NN][maxCenterGPermus23], numCenterGPermus23[NN][NN],
// Third number of CenterPermus indexed by the first, second, and fourth.
    CenterPermus124[NN][NN][NN];

const int numSquares=22145;
// Output is 1 square for each of the partitions that make a center square.

int Borders[numPartitions][NN-MM];

// Combinations that do not include complementary pairs.
const int maxBorderCombos=330; int BorderCombos[maxBorderCombos][N], numBorderCombos;

// Groups of BorderCombos in which the sixth is greater than the first.
const int maxBorderGGroups=4950; int BorderGGroups[maxBorderGGroups][N], numBorderGGroups;

// BorderGGroups indexed by the first and sixth numbers.
const int maxBorderGGroups16=43;
int *BorderGGroups16[NN][NN][maxBorderGGroups16], numBorderGGroups16[NN][NN];

void putCenter(const int a, const int b, const int c, const int d, const int e, const int f, const int g, const int h) {
//   ---------
  int *p=Centers[numCenters++]; p[0]=a; p[1]=b; p[2]=c; p[3]=d; p[4]=e; p[5]=f; p[6]=g; p[7]=h;
  p[8] =Sum2-h; p[9] =Sum2-g; p[10]=Sum2-f; p[11]=Sum2-e; p[12]=Sum2-d; p[13]=Sum2-c; p[14]=Sum2-b; p[15]=Sum2-a;
} // putCenter

void getCenters() {
//   ----------
  numCenters=0;
  for (int i1=0; i1<(Half-7); i1++) for (int i2=i1+1; i2<(Half-6); i2++) for (int i3=i2+1; i3<(Half-5); i3++)
	  for (int i4=i3+1; i4<(Half-4); i4++) for (int i5=i4+1; i5<(Half-3); i5++) for (int i6=i5+1; i6<(Half-2); i6++)
	    for (int i7=i6+1; i7<(Half-1); i7++) for (int i8=i7+1; i8<Half; i8++) putCenter(i1, i2, i3, i4, i5, i6, i7, i8);
 // assert(numCenters==numPartitions);
} // getCenters

struct bools { bool used[NN]; }; struct bools allfree;
void getBorders() {
//   ----------
  for (int i=0; i<numPartitions; i++) {
    struct bools v=allfree; int *p=Centers[i]; for (int j=0; j<MM; j++) v.used[p[j]]=T;
    p=Borders[i];  int k=0; for (int j=0; j<NN; j++) if (!v.used[j]) p[k++]=j;
  }
} // getBorders

void getPartitions() { getCenters(); getBorders(); }
//   -------------

void putCenterCombo(const int a, const int b, const int c, const int d) {
//   --------------
  int *p=CenterCombos[numCenterCombos++]; p[0]=a; p[1]=b; p[2]=c; p[3]=d;
} // putCenterCombo

void getCenterCombos(const int i) {
//   ---------------
  numCenterCombos=0; int *p=Centers[i];
  for (int i=0; i<(MM-3); i++) for (int j=i+1; j<(MM-2); j++) for (int k=j+1; k<(MM-1); k++)
	  for (int l=k+1; l<MM; l++) if (p[i]+p[j]+p[k]+p[l]==Sum4) putCenterCombo(p[i], p[j], p[k], p[l]);
} // getCenterCombos

void permute4_3(const int a, const int b, const int c, const int d) {
//   ----------
  int *p;
  p=CenterPermus[numCenterPermus++]; p[0]=a; p[1]=b; p[2]=c; p[3]=d;
  p=CenterPermus[numCenterPermus++]; p[0]=a; p[1]=b; p[2]=d; p[3]=c;
  p=CenterPermus[numCenterPermus++]; p[0]=a; p[1]=c; p[2]=b; p[3]=d;
  p=CenterPermus[numCenterPermus++]; p[0]=a; p[1]=c; p[2]=d; p[3]=b;
  p=CenterPermus[numCenterPermus++]; p[0]=a; p[1]=d; p[2]=b; p[3]=c;
  p=CenterPermus[numCenterPermus++]; p[0]=a; p[1]=d; p[2]=c; p[3]=b;
} // permute4_3

void getCenterPermus() {
//   ---------------
  numCenterPermus=0;
  for (int i=0; i<numCenterCombos; i++) {
    int *p=CenterCombos[i]; permute4_3(p[0], p[1], p[2], p[3]);	 
    permute4_3(p[1], p[0], p[2], p[3]); permute4_3(p[2], p[1], p[0], p[3]); permute4_3(p[3], p[1], p[2], p[0]);
  }
} // getCenterPermus

void getCenterGPermus() {
//   ----------------
  numCenterGPermus=0;
  for (int i=0; i<numCenterPermus; i++) {
    int *p=CenterPermus[i]; if (p[2]>p[1]) CenterGPermus[numCenterGPermus++]=p;
  }
} // getCenterGPermus

void getCenterGPermus23() {
//   ------------------
  for (int i=0; i<NN; i++) for (int j=0; j<NN; j++) numCenterGPermus23[i][j]=0;
  for (int i=0; i<numCenterGPermus; i++) {
    int *p=CenterGPermus[i]; CenterGPermus23[p[1]][p[2]][(numCenterGPermus23[p[1]][p[2]])++]=p;
  }
} // getCenterGPermus23 

void getCenterPermus124() {
//   ------------------
  for (int i=0; i<NN; i++) for (int j=0; j<NN; j++) for (int k=0; k<NN; k++) CenterPermus124[i][j][k]=-1;
  for (int i=0; i<numCenterPermus; i++) { int *p=CenterPermus[i]; CenterPermus124[p[0]][p[1]][p[3]]=p[2]; }
} // getCenterPermus124

void putBorderCombo(const int a, const int b, const int c, const int d, const int e, const int f) {
//   --------------
  int *p=BorderCombos[numBorderCombos++]; p[0]=a; p[1]=b; p[2]=c; p[3]=d; p[4]=e; p[5]=f;
} // putBorderCombo

void getBorderCombos(const int i) {
//   ---------------
  int *p=Borders[i]; struct bools v=allfree; numBorderCombos=0;
  for (int i=0; i<(NN-MM-5); i++) { v.used[Sum2-p[i]]=T;
    for (int j=i+1; j<(NN-MM-4); j++) if (!v.used[p[j]]) { v.used[Sum2-p[j]]=T;
      for (int k=j+1; k<(NN-MM-3); k++) if (!v.used[p[k]]) { v.used[Sum2-p[k]]=T;
	      for (int l=k+1; l<(NN-MM-2); l++) if (!v.used[p[l]]) { v.used[Sum2-p[l]]=T;
	        for (int m=l+1; m<(NN-MM-1); m++) if (!v.used[p[m]]) { v.used[Sum2-p[m]]=T;
            for (int n=m+1; n<(NN-MM); n++) if (!v.used[p[n]])
              if ( ((p[i]+p[j]+p[k]+p[l]+p[m]+ p[n])==Sum6) )
                putBorderCombo(p[i], p[j], p[k], p[l], p[m], p[n]); v.used[Sum2-p[m]]=F;
          } v.used[Sum2-p[l]]=F;
        } v.used[Sum2-p[k]]=F;
      } v.used[Sum2-p[j]]=F;
    } v.used[Sum2-p[i]]=F;
  }
} // getBorderCombos

void putBorderGGroup(const int a, const int b, const int c, const int d, const int e, const int f) {
//   ---------------
  int *p; if (a<b) { p=BorderGGroups[numBorderGGroups++]; p[0]=a; p[1]=c; p[2]=d; p[3]=e; p[4]=f; p[5]=b; }
} // putBorderGGroup

void permute6_5(const int a, const int b, const int c, const int d, const int e, const int f) {
//   ----------
  putBorderGGroup(a, b, c, d, e, f); putBorderGGroup(a, c, b, d, e, f);
  putBorderGGroup(a, d, c, b, e, f); putBorderGGroup(a, e, c, d, b, f); putBorderGGroup(a, f, c, d, e, b);
} // permute6_5

void getBorderGGroups() {
//   ----------------
  numBorderGGroups=0;
  for (int i=0; i<numBorderCombos; i++) {
    int *p=BorderCombos[i]; const int p0=p[0], p1=p[1], p2=p[2],  p3=p[3], p4=p[4], p5=p[5];
    permute6_5(p0, p1, p2, p3, p4, p5); permute6_5(p1, p0, p2, p3, p4, p5);
    permute6_5(p2, p1, p0, p3, p4, p5); permute6_5(p3, p1, p2, p0, p4, p5);
    permute6_5(p4, p1, p2, p3, p0, p5); permute6_5(p5, p1, p2, p3, p4, p0);
  }
} // getBorderGGroups 

void getBorderGGroups16() {
//   ------------------
  for (int i=0; i<NN; i++) for (int j=0; j<NN; j++) numBorderGGroups16[i][j]=0;
  for (int i=0; i<numBorderGGroups; i++) {
    int *p=BorderGGroups[i]; BorderGGroups16[p[0]][p[5]][(numBorderGGroups16[p[0]][p[5]])++]=p;
  }
} // getBorderGGroups16 

bool makeCenter4Square() {
//   -----------------
  struct bools v=allfree;
  for (int i0=0; i0<numCenterGPermus; i0++) {
    const int *yx=CenterGPermus[i0], /* back diag */ yx0=yx[0], yx1=yx[1], yx2=yx[2], yx3=yx[3]; 
    v.used[yx0]=T; v.used[yx1]=T; v.used[yx2]=T; v.used[yx3]=T;
    for (int i1=0; i1<numCenterGPermus; i1++) {
      const int *xy=CenterGPermus[i1], /* forward diag */ xy0=xy[0], xy1=xy[1], xy2=xy[2], xy3=xy[3];
      if (!(v.used[xy0]||v.used[xy1]||v.used[xy2]||v.used[xy3])) {
        v.used[xy0]=T; v.used[xy1]=T; v.used[xy2]=T; v.used[xy3]=T; 
	      const int i2Max=numCenterGPermus23[yx1][xy1]; int **p2=CenterGPermus23[yx1][xy1];
	      for (int i2=0; i2<i2Max; i2++) {
	        const int *r2=*(p2+i2); // second row
          if (!(v.used[r2[0]]|v.used[r2[3]])) {
            v.used[r2[0]]=T; v.used[r2[3]]=T; const int c13=CenterPermus124[yx0][r2[0]][xy3];
            if ( (c13>=0)&!v.used[c13]) {
              v.used[c13]=T; const int c43=CenterPermus124[xy0][r2[3]][yx3];
              if ( (c43>=0)&&!v.used[c43]&&(c13+xy2+yx2+c43==Sum4) ) {
                v.used[c43]=T; const int i3Max=numCenterGPermus23[yx1][xy2]; int **p3=CenterGPermus23[yx1][xy2];
                for (int i3=0; i3<i3Max; i3++) {
	                const int *c2=*(p3+i3); // second column
                  if (!(v.used[c2[0]]|v.used[c2[3]])) {
                    v.used[c2[0]]=T; v.used[c2[3]]=T; const int c31=CenterPermus124[yx0][c2[0]][xy0];
		                if ( (c31>=0)&!v.used[c31]) { const int c34=CenterPermus124[xy3][c2[3]][yx3];
		                  if ( (c34>=0)&&!v.used[c34]&&(c31+xy1+yx2+c34==Sum4) ) {
                        int *p=X[1]; p[1]=yx0+1; p[2]=c2[0]+1; p[3]=c31+1; p[4]=xy0+1;
                        p=X[2]; p[1]=r2[0]+1; p[2]=yx1+1; p[3]=xy1+1; p[4]=r2[3]+1;
                        p=X[3]; p[1]=c13+1; p[2]=xy2+1; p[3]=yx2+1; p[4]=c43+1;
                        p=X[4]; p[1]=xy3+1; p[2]=c2[3]+1; p[3]=c34+1; p[4]=yx3+1; return T;
					            } v.used[c31]=F;
		                } v.used[c2[0]]=F; v.used[c2[3]]=F;
		              }
		            } v.used[c43]=F;
              } v.used[c13]=F;
	          } v.used[r2[0]]=F; v.used[r2[3]]=F;
	        }
	      } v.used[xy0]=F; v.used[xy1]=F; v.used[xy2]=F; v.used[xy3]=F;
      }
    } v.used[yx0]=F; v.used[yx1]=F; v.used[yx2]=F; v.used[yx3]=F;
  }
  return F;
} // makeCenter4Square

bool makeOrder6Squares(FILE *wfp) {
//   -----------------
  struct bools v=allfree;
  for (int i0=0; i0<numBorderGGroups; i0++) {
    const int *r1=BorderGGroups[i0]; // first row
    if ( (r1[0]<Half)&(r1[5]<Half) ) {
      v.used[r1[1]]=T; v.used[r1[2]]=T; v.used[r1[3]]=T; v.used[r1[4]]=T;
      v.used[Sum2-r1[1]]=T; v.used[Sum2-r1[2]]=T; v.used[Sum2-r1[3]]=T; v.used[Sum2-r1[4]]=T;
      const int c16=Sum2-r1[5], i1Max=numBorderGGroups16[r1[0]][c16]; int **p1 =BorderGGroups16[r1[0]][c16];
      for (int i1=0; i1<i1Max; i1++) {
        const int *c1=*(p1+i1); // first column
        if (!(v.used[c1[1]]||v.used[c1[2]]||v.used[c1[3]]||v.used[c1[4]])) {
          int *p=X[0]; p[0]=r1[0]+1; p[1]=r1[1]+1; p[2]=r1[2]+1; p[3]=r1[3]+1; p[4]=r1[4]+1; p[5]=r1[5]+1;
          p=X[1]; p[0]=c1[1]+1; p[5]=Sum2-c1[1]+1; p=X[2]; p[0]=c1[2]+1; p[5]=Sum2-c1[2]+1;
          p=X[3]; p[0]=c1[3]+1; p[5]=Sum2-c1[3]+1; p=X[4]; p[0]=c1[4]+1; p[5]=Sum2-c1[4]+1; p=X[5];
          p[0]=c16+1; p[1]=Sum2-r1[1]+1; p[2]=Sum2-r1[2]+1; p[3]=Sum2-r1[3]+1; p[4]=Sum2-r1[4]+1; p[5]=Sum2-r1[0]+1;		  
          if ( outputSquare(wfp) ) return T; else { perror("\a\nError writing file"); return F; }
        }
      }
      v.used[r1[1]]=F; v.used[r1[2]]=F; v.used[r1[3]]=F; v.used[r1[4]]=F;
      v.used[Sum2-r1[1]]=F; v.used[Sum2-r1[2]]=F; v.used[Sum2-r1[3]]=F; v.used[Sum2-r1[4]]=F;
    }
  }
  printf("\a\nNot working. Please report by email.\n"); return F;
} // makeOrder6Squares 

bool makeSquares(FILE *wfp) {
//   -----------
  time_t startTime=time(NULL); getPartitions();
  for (int i=0; i<numPartitions; i++) {
    getCenterCombos(i); getCenterPermus(); getCenterGPermus(); getCenterGPermus23(); getCenterPermus124();
    if ( makeCenter4Square() ) {
      getBorderCombos(i);  getBorderGGroups();  getBorderGGroups16(); if (!makeOrder6Squares(wfp)) return F;
    }
  }
  const int et=(int)difftime(time(NULL), startTime);
  printf("\nsample number of squares: %d, elapsed time: %d:%02d:%02d\n", numSquares, et/3600, et%3600/60, et%60);
  return T;
} // makeSquares
//======================================================= main =================================================

void outputLocalTime() {
//   ---------------
  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\0", local); printf("\n%s", dateTime);
  }
} // outputLocalTime

int main() {
//  ----
  outputLocalTime(); bool  ok=F; FILE *wfp=openFile();
  if (wfp!=NULL) { ok=makeSquares(wfp); fclose(wfp); }
  printf("\nHit return to close the console.");
  while (T) if (getchar()=='\n') break; return ok ? EXIT_SUCCESS : EXIT_FAILURE;
} // main