/*
 *  File:    NOrder5.cpp
 *  Author:  S Harry White
 *  Created: 2009-05-15
 *  Updated: 2022-01-13
 *    Tidy code.
 */

/*
      Friday 2022-01-14 16:44:22 Newfoundland Standard Time

      Center  1,25 number of squares   4365792, elapsed time  0:10
      Center  2,24 number of squares   5464716, elapsed time  0:12
      Center  3,23 number of squares   7659936, elapsed time  0:13
      Center  4,22 number of squares   7835348, elapsed time  0:14
      Center  5,21 number of squares   9727224, elapsed time  0:16
      Center  6,20 number of squares  10403516, elapsed time  0:16
      Center  7,19 number of squares  12067524, elapsed time  0:18
      Center  8,18 number of squares  12448644, elapsed time  0:18
      Center  9,17 number of squares  13890160, elapsed time  0:19
      Center 10,16 number of squares  13376136, elapsed time  0:20
      Center 11,15 number of squares  15735272, elapsed time  0:20
      Center 12,14 number of squares  15138472, elapsed time  0:21
      Center 13    number of squares  19079744, elapsed time  0:22

             total number of squares 275305224, elapsed time  3:39
*/

#include "stdafx.h"
#include <conio.h>
#include <stdio.h>
#include <time.h>
#include <Windows.h>

const int N             = 5,
          NN            = N*N,         // 25

// zero based
          Mid           = (NN-1)/2,   // 12
          MagicConstant = Mid*N;      // 60

const bool T=true;

// Combinations of N chosen from 0 .. NN-1 that total to MagicConstant.

// Combinations that contain K where K is one of 0 .. Mid.
const int maxKCombos=302;
int KCombos[maxKCombos][N+1], numKCombos;

// Permutations of KCombos with K omitted.
const int maxCenterKPermus=7248;
int CenterKPermus[maxCenterKPermus][N], numCenterKPermus;

// CenterKPermus in which the third number is greater than the second.
const int maxCenterKUPermus=3624;
int *CenterKUPermus[maxCenterKUPermus], sizeCenterKUPermus;

struct spu { int *p; int u; };

const int maxCenterKPermusIJ=22;
// CenterKPermus indexed by the first and fourth.
spu CenterKPermus14[NN][NN][maxCenterKPermusIJ]; int sizeCenterKPermus14[NN][NN];

// CenterKPermus indexed by the second and third.
spu CenterKPermus23[NN][NN][maxCenterKPermusIJ]; int sizeCenterKPermus23[NN][NN];

// Combinations that do not contain K.
const int maxOKCombos=1150;
int OKCombos[maxOKCombos][N], numOKCombos;

// Permutations of OKCombos.
const int maxOKPermus=138000;  // 1150 x 5!
int OKPermus[maxOKPermus][N], numOKPermus;

const int maxOKPermusIJ=330;
// OKPermus in which the fourth is greater than the second,
// indexed by the second and fourth.
spu OKUPermus24[NN][NN][maxOKPermusIJ]; int sizeOKUPermus24[NN][NN];

// OKPermus indexed by the first, second and fifth.
const int maxOKPermusIJK=20;
spu OKPermus125[NN][NN][NN][maxOKPermusIJK]; int sizeOKPermus125[NN][NN][NN];

// OKPermus in which the fourth is greater than the second,
// indexed by the second, third and fourth.
spu OKUPermus234[NN][NN][NN][maxOKPermusIJK]; int sizeOKUPermus234[NN][NN][NN];

// Fourth of OKPermus indexed by the first, second, third and fifth.
int OKPermus1235[NN][NN][NN][NN],
// Third of OKPermus indexed by the first, second, fourth and fifth.
    OKPermus1245[NN][NN][NN][NN];
//=============================================================================================

void putCombos(const int K, const int a, const int b, const int c, const int d, const int e) {
//   ---------
  int *p;
  if ((a==K)||(b==K)||(c==K)||(d==K)||(e==K)) {
    p=KCombos[numKCombos++]; p[5]=((1<<a)|(1<<b)|(1<<c)|(1<<d)|(1<<e))&~(1<<K);
  } else p=OKCombos[numOKCombos++];
  p[0]=a; p[1]=b; p[2]=c; p[3]=d; p[4]=e;
} // putCombos

void getCombos(const int K) {
//   ---------
  numKCombos=0; numOKCombos=0;
  for (int i=0; i<(NN-4); i++)
    for (int j=i+1; j<(NN-3); j++)
      for (int k=j+1; k<(NN-2); k++)
        for (int l=k+1; l<(NN-1); l++)
          for (int m=l+1; m<NN; m++) if ((i+j+k+l+m)==MagicConstant) putCombos(K, i, j, k, l, m);
} // getCombos

void permuteCenterK_3(const int K, const int a, const int b, const int c, const int d, const int e, const int u) {
//   ----------------
  if (c==K) {
    int *p=CenterKPermus[numCenterKPermus++]; p[0]=a; p[1]=b; p[2]=d; p[3]=e; spu *q;
    q=&(CenterKPermus14[a][e][(sizeCenterKPermus14[a][e])++]); q->p=p; q->u=(1<<b)|(1<<d);
    q=&(CenterKPermus23[b][d][(sizeCenterKPermus23[b][d])++]); q->p=p; q->u=(1<<a)|(1<<e);
    if (d>b) { CenterKUPermus[sizeCenterKUPermus++]=p; p[4]=u; }

    p=CenterKPermus[numCenterKPermus++]; p[0]=a; p[1]=b; p[2]=e; p[3]=d;
    q=&(CenterKPermus14[a][d][(sizeCenterKPermus14[a][d])++]); q->p=p; q->u=(1<<b)|(1<<e);
    q=&(CenterKPermus23[b][e][(sizeCenterKPermus23[b][e])++]); q->p=p; q->u=(1<<a)|(1<<d);
    if (e>b) { CenterKUPermus[sizeCenterKUPermus++]=p; p[4]=u; }
  } else if (d==K) {
    int *p=CenterKPermus[numCenterKPermus++]; p[0]=a; p[1]=b; p[2]=c; p[3]=e; spu *q;
    q=&(CenterKPermus14[a][e][(sizeCenterKPermus14[a][e])++]); q->p=p; q->u=(1<<b)|(1<<c);
    q=&(CenterKPermus23[b][c][(sizeCenterKPermus23[b][c])++]); q->p=p; q->u=(1<<a)|(1<<e);
    if (c>b) { CenterKUPermus[sizeCenterKUPermus++]=p; p[4]=u; }

    p=CenterKPermus[numCenterKPermus++]; p[0]=a; p[1]=b; p[2]=e; p[3]=c;
    q=&(CenterKPermus14[a][c][(sizeCenterKPermus14[a][c])++]); q->p=p; q->u=(1<<b)|(1<<e);
    q=&(CenterKPermus23[b][e][(sizeCenterKPermus23[b][e])++]); q->p=p; q->u=(1<<a)|(1<<c);
    if (e>b) { CenterKUPermus[sizeCenterKUPermus++]=p; p[4]=u; }
  } else if (e==K) {
    int *p=CenterKPermus[numCenterKPermus++]; p[0]=a; p[1]=b; p[2]=c; p[3]=d; spu *q;
    q=&(CenterKPermus14[a][d][(sizeCenterKPermus14[a][d])++]); q->p=p; q->u=(1<<b)|(1<<c);
    q=&(CenterKPermus23[b][c][(sizeCenterKPermus23[b][c])++]); q->p=p; q->u=(1<<a)|(1<<d);
    if (c>b) { CenterKUPermus[sizeCenterKUPermus++]=p; p[4]=u; }

    p=CenterKPermus[numCenterKPermus++]; p[0]=a; p[1]=b; p[2]=d; p[3]=c;
    q=&(CenterKPermus14[a][c][(sizeCenterKPermus14[a][c])++]); q->p=p; q->u=(1<<b)|(1<<d);
    q=&(CenterKPermus23[b][d][(sizeCenterKPermus23[b][d])++]); q->p=p; q->u=(1<<a)|(1<<c);
    if (d>b) { CenterKUPermus[sizeCenterKUPermus++]=p; p[4]=u; }
  }
} // permuteCenterK_3

void permuteK_4(const int K, const int a, const int b, const int c, const int d, const int e, const int u) {
//   ----------
  permuteCenterK_3(K, a, b, c, d, e, u); permuteCenterK_3(K, a, c, b, d, e, u);
  permuteCenterK_3(K, a, d, c, b, e, u); permuteCenterK_3(K, a, e, c, d, b, u);
} // permuteK_4

void getCenterKPermus(const int K) {
//   ----------------
  numCenterKPermus=0; sizeCenterKUPermus=0;
  for (int i=0; i<NN; i++) for (int j=0; j<NN; j++) {
    sizeCenterKPermus14[i][j]=0; sizeCenterKPermus23[i][j]=0;
  }
  for (int i=0; i<numKCombos; i++) {
    int *p=KCombos[i], a=p[0], b=p[1], c=p[2], d=p[3], e=p[4], u=p[5];
    permuteK_4(K, a, b, c, d, e, u); permuteK_4(K, b, a, c, d, e, u); permuteK_4(K, c, b, a, d, e, u);
    permuteK_4(K, d, b, c, a, e, u); permuteK_4(K, e, b, c, d, a, u);
  }
} // getCenterKPermus

void permuteOK_3(const int a, const int b, const int c, const int d, const int e) {
//   -----------
  int *p, t; spu *q; 

  p=OKPermus[numOKPermus++]; p[0]=a; p[1]=b; p[2]=c; p[3]=d; p[4]=e;
  q=&(OKPermus125[a][b][e][(sizeOKPermus125[a][b][e])++]); q->p=p; q->u=(1<<c)|(1<<d);
  OKPermus1235[a][b][c][e]=d; OKPermus1245[a][b][d][e]=c;
  if (d>b) {
    q=&(OKUPermus234[b][c][d][(sizeOKUPermus234[b][c][d])++]); q->p=p; q->u=t=(1<<a)|(1<<e);
    q=&(OKUPermus24[b][d][(sizeOKUPermus24[b][d])++]); q->p=p; q->u=t|(1<<c);
  }

  p=OKPermus[numOKPermus++]; p[0]=a; p[1]=b; p[2]=c; p[3]=e; p[4]=d;
  q=&(OKPermus125[a][b][d][(sizeOKPermus125[a][b][d])++]); q->p=p; q->u=(1<<c)|(1<<e);
  OKPermus1235[a][b][c][d]=e; OKPermus1245[a][b][e][d]=c;
  if (e>b) {
    q=&(OKUPermus234[b][c][e][(sizeOKUPermus234[b][c][e])++]); q->p=p; q->u=t=(1<<a)|(1<<d);
    q=&(OKUPermus24[b][e][(sizeOKUPermus24[b][e])++]); q->p=p; q->u=t|(1<<c);
  }

  p=OKPermus[numOKPermus++]; p[0]=a; p[1]=b; p[2]=d; p[3]=c; p[4]=e;
  q=&(OKPermus125[a][b][e][(sizeOKPermus125[a][b][e])++]); q->p=p; q->u=(1<<c)|(1<<d);
  OKPermus1235[a][b][d][e]=c; OKPermus1245[a][b][c][e]=d;
  if (c>b) {
    q=&(OKUPermus234[b][d][c][(sizeOKUPermus234[b][d][c])++]); q->p=p; q->u=t=(1<<a)|(1<<e);
    q=&(OKUPermus24[b][c][(sizeOKUPermus24[b][c])++]); q->p=p; q->u=t|(1<<d);
  }

  p=OKPermus[numOKPermus++]; p[0]=a; p[1]=b; p[2]=d; p[3]=e; p[4]=c;
  q=&(OKPermus125[a][b][c][(sizeOKPermus125[a][b][c])++]); q->p=p; q->u=(1<<d)|(1<<e);
  OKPermus1235[a][b][d][c]=e; OKPermus1245[a][b][e][c]=d;
  if (e>b) {
    q=&(OKUPermus234[b][d][e][(sizeOKUPermus234[b][d][e])++]); q->p=p; q->u=t=(1<<a)|(1<<c);
    q=&(OKUPermus24[b][e][(sizeOKUPermus24[b][e])++]); q->p=p; q->u=t|(1<<d);
  }

  p=OKPermus[numOKPermus++]; p[0]=a; p[1]=b; p[2]=e; p[3]=c; p[4]=d;
  q=&(OKPermus125[a][b][d][(sizeOKPermus125[a][b][d])++]); q->p=p; q->u=(1<<c)|(1<<e);
  OKPermus1235[a][b][e][d]=c; OKPermus1245[a][b][c][d]=e;
  if (c>b) {
    q=&(OKUPermus234[b][e][c][(sizeOKUPermus234[b][e][c])++]); q->p=p; q->u=t=(1<<a)|(1<<d);
    q=&(OKUPermus24[b][c][(sizeOKUPermus24[b][c])++]); q->p=p; q->u=t|(1<<e);
  }

  p=OKPermus[numOKPermus++]; p[0]=a; p[1]=b; p[2]=e; p[3]=d; p[4]=c;
  q=&(OKPermus125[a][b][c][(sizeOKPermus125[a][b][c])++]); q->p=p; q->u=(1<<d)|(1<<e);
  OKPermus1235[a][b][e][c]=d; OKPermus1245[a][b][d][c]=e;
  if (d>b) {
    q=&(OKUPermus234[b][e][d][(sizeOKUPermus234[b][e][d])++]); q->p=p; q->u=t=(1<<a)|(1<<c);
    q=&(OKUPermus24[b][d][(sizeOKUPermus24[b][d])++]); q->p=p; q->u=t|(1<<e);
  }
} // permuteOK_3

void permuteOK_4(const int a, const int b, const int c, const int d, const int e) {
//   -----------
  permuteOK_3(a, b, c, d, e); permuteOK_3(a, c, b, d, e);
  permuteOK_3(a, d, c, b, e); permuteOK_3(a, e, c, d, b);
} // permuteOK_4

void getOKPermus() {
//   -----------
  numOKPermus=0;
  for (int i=0; i<NN; i++) for (int j=0; j<NN; j++) {
    sizeOKUPermus24[i][j]=0;
    for (int k=0; k<NN; k++) { sizeOKPermus125[i][j][k]=0; sizeOKUPermus234[i][j][k]=0;
      for (int l=0; l<NN; l++) { OKPermus1235[i][j][k][l]=-1; OKPermus1245[i][j][k][l]=-1; }
    }
  }
  for (int i=0; i<numOKCombos; i++) {
    int *p=OKCombos[i], a=p[0], b=p[1], c=p[2], d=p[3], e=p[4];
    permuteOK_4(a, b, c, d, e); permuteOK_4(b, a, c, d, e); permuteOK_4(c, b, a, d, e);
    permuteOK_4(d, b, c, a, e); permuteOK_4(e, b, c, d, a);
  }
} // getOKPermus 

// Used to disable some pairs of diagonal permutations.
struct bools {union { bool off[NN][NN][NN][NN][NN][NN]; int align[(NN*NN*NN*NN*NN*NN+3)/4]; } u; };
bools noOff, diags;

// fill order: \dia, /dia, r 1, c 0, c 4, a[3][2], r 2, c 2, c 1, a[0][3], a[4][3]
//
//  1 21 19 23  5
//  9  2 10  6 11
// 12 17  0 18 14
// 13  7 16  3 15
//  8 22 20 24  4

int countCenterKSquares() {
//  -------------------
  int count=0, i0=sizeCenterKUPermus, **p0=CenterKUPermus; // B2>B1
  while (i0--) { // \ back diagonal B   
    int *B=*p0, B0=B[0], B1=B[1], B2=B[2], B3=B[3], i1=sizeCenterKUPermus, **p1=CenterKUPermus; // F2>F1
    while (i1--) { // / forward diagonal F
      int *F=*p1; if ( (F[1]>B1)&&(!(F[4]&B[4])) ) { const int F0=F[0], F1=F[1], F2=F[2], F3=F[3];
      // F2>F1 and F1>B1, so F2>B1, (see second column below).
      if (diags.u.off[B0][B1][B2][F0][F1][F2]) { ++p1; continue; }
      // Count 4: the square, xform 1, xform 2, and xform 2 of xform 1.
      if (F3<F0) {   // xform 1: Turn off its xform 2 and skip.
        if (B3>B0) { // xform 2
          if (F3>B0) diags.u.off[B1][B0][B3][F2][F3][F0]=T; else diags.u.off[F2][F3][F0][B1][B0][B3]=T;
        } else {    // xform 2, reverse B
          if (F3>B3) diags.u.off[B2][B3][B0][F2][F3][F0]=T; else diags.u.off[F2][F3][F0][B2][B3][B0]=T;
        }
        ++p1; continue;
      } else { // Turn off xform 2.
		    if (B3>B0) {  // xform 2
          if (F0>B0) diags.u.off[B1][B0][B3][F1][F0][F3]=T; else diags.u.off[F1][F0][F3][B1][B0][B3]=T;
		    } else {      // xform 2, reverse B
		      if (F0>B3) diags.u.off[B2][B3][B0][F1][F0][F3]=T; else diags.u.off[F1][F0][F3][B2][B3][B0]=T;
		    }
      }
      const int fUsed=F[4]|B[4]; spu *p2=OKUPermus24[B1][F1]; int i2=sizeOKUPermus24[B1][F1];
      while (i2--) { if (!(p2->u&fUsed)) { // second row
        int *r1=p2->p, r1Used=p2->u|fUsed;
        spu *p3=OKPermus125[B0][r1[0]][F3]; int i3=sizeOKPermus125[B0][r1[0]][F3];
        while (i3--) { if (!(p3->u&r1Used)) { // first column;
          int *c0=p3->p; const int c0Used=p3->u|r1Used;
          spu *p4=OKPermus125[F0][r1[4]][B3]; int i4=sizeOKPermus125[F0][r1[4]][B3];
          while (i4--) { if (!(p4->u&c0Used)) { // fifth column
            int *c4=p4->p, c4Used=p4->u|c0Used; const int a32=OKPermus1245[c0[3]][F2][B2][c4[3]];
            if ( (a32>=0)&&(!(c4Used&(1<<a32))) ) { c4Used|=(1<<a32);
            spu *p5=CenterKPermus14[c0[2]][c4[2]]; int i5=sizeCenterKPermus14[c0[2]][c4[2]];
            while (i5--) { if (!(p5->u&c4Used)) { // third row            
              int *r2=p5->p; const int r2Used=p5->u|c4Used;
              spu *p6=CenterKPermus23[r1[2]][a32]; int i6=sizeCenterKPermus23[r1[2]][a32];
              while (i6--) { if (!(p6->u&r2Used)) { // third column
                int *c2=p6->p; const int c2Used=p6->u|r2Used;
                spu *p7=OKUPermus234[B1][r2[1]][F2]; int i7=sizeOKUPermus234[B1][r2[1]][F2];
                while (i7--) { if (!(p7->u&c2Used)) { // second column
                  const int c1Used=p7->u|c2Used, a03=OKPermus1235[B0][p7->p[0]][c2[0]][F0];
                  if ((a03>=0)&&!(c1Used&(1<<a03))) ++count;
                } ++p7; }
              } ++p6; }
            } ++p5; }
          }} ++p4; }
        } ++p3; }
      } ++p2; }
    } ++p1; }
    ++p0;
  }
  return count;
} // countCenterKSquares 

/*
int MaxKCombos, MaxCenterKPermus, MaxCenterKUPermus, MaxCenterKPermusIJ;
int MaxOKCombos, MaxOKPermus, MaxOKPermusIJ, MaxOKPermusIJK;
void getMaxs() {
//   -------
  if (numKCombos>MaxKCombos) MaxKCombos=numKCombos;
  if (numCenterKPermus>MaxCenterKPermus) MaxCenterKPermus=numCenterKPermus;
  if (sizeCenterKUPermus>MaxCenterKUPermus) MaxCenterKUPermus=sizeCenterKUPermus;
  if (numOKCombos>MaxOKCombos) MaxOKCombos=numOKCombos;
  if (numOKPermus>MaxOKPermus) MaxOKPermus=numOKPermus;

  for (int i=0; i<NN; i++)
    for (int j=0; j<NN; j++) {
      if (sizeCenterKPermus14[i][j]>MaxCenterKPermusIJ) MaxCenterKPermusIJ=sizeCenterKPermus14[i][j];
      if (sizeCenterKPermus23[i][j]>MaxCenterKPermusIJ) MaxCenterKPermusIJ=sizeCenterKPermus23[i][j];
      if (sizeOKUPermus24[i][j]>MaxOKPermusIJ) MaxOKPermusIJ=sizeOKUPermus24[i][j];     
      for (int k=0; k<NN; k++) {
        if (sizeOKPermus125[i][j][k]>MaxOKPermusIJK) MaxOKPermusIJK=sizeOKPermus125[i][j][k];
        if (sizeOKUPermus234[i][j][k]>MaxOKPermusIJK) MaxOKPermusIJK=sizeOKUPermus234[i][j][k];
      }
    }
} // getMaxs

void printMaxs() {
//   ---------
  printf("MaxKCombos %d MaxCenterKPermus %d MaxCenterKUPermus %d MaxCenterKPermusIJ %d\n",
    MaxKCombos, MaxCenterKPermus, ++MaxCenterKUPermus, ++MaxCenterKPermusIJ);
  printf("MaxOKCombos %d MaxOKPermus %d MaxOKPermusIJ %d MaxOKPermusIJK %d\n",
    MaxOKCombos, MaxOKPermus, ++MaxOKPermusIJ, ++MaxOKPermusIJK);
} // printMaxs
*/

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

void printElapsedTime(time_t startTime) {
//   ---------------- 
  int et=(int)difftime(time(NULL), startTime); printf("%2d:%02d\n", et/60, et%60);
} // printElapsedTime

void countSquares() {
//   ------------
  int count=0; time_t startTime=time(NULL);
  for (int K=0; K<=Mid; ++K) {
    time_t startTimeK=time(NULL); getCombos(K); getCenterKPermus(K);getOKPermus(); //getMaxs();
    int Kcount=countCenterKSquares()<<2; count+=Kcount;
    if (K==Mid) printf("Center %2d    number of squares %9d, elapsed time ", K+1, Kcount);
    else { printf("Center %2d,%2d number of squares %9d, elapsed time ", K+1, NN-K, Kcount);
      count+=Kcount; diags=noOff;
    }
    printElapsedTime(startTimeK);
  }
  //printMaxs();
  printf("\n       total number of squares %9d, elapsed time ", count);
  printElapsedTime(startTime);
} // countSquares

int main() {
//  ----
  outputLocalTime(); countSquares(); printf("\n\nPress a key to close the console");
  while (!_kbhit()) Sleep(250); return EXIT_SUCCESS;
} // main