I Can New Theorems Predict Incomplete 5x5 Magic Square Solutions?

[Vanadium 50]

TL;DR Summary

Are there additional theorems one can show from an incomplete 5x5 magic square that completing it is possible or impossible?

A magic square is a NxN array of numbers from 1 to N² such that the sum of elements of each row, column and diagonal adds up to the same number, 65 in the case of 5x5's. An example would be:

15 19 4 7 20
6 14 24 16 5
9 21 1 22 12
10 3 23 18 11
25 8 13 2 17

There are a number of theorems one can prove about incomplete 5x5 squares. For example,

14 X 4 X 20
X 15 24 16 X
9 21 1 22 12
X 3 23 18 X
25 X 13 X 17

will never complete to form a magic square because it fails what I call the "nine minus four" theorem. All magic squares have the difference between the sum of the inner nine cells minus the four corners equal to 65. For the second square, this is 67.

There is also what I call the parity theorem. The 5 cells that form a + sign centered on the center cell (24,21,1,22,23) must have an odd sum.

Are there other theorems, independent from these two, that can be used to determine if an incomplete 5x5 square can be completed as magic? For example,

14 X X X 20
X 15 X 10 X
X X 1 X X
X 13 X 16 X
21 X X X 19

cannot be completed. (Exhaustive test). Can one tell this from the 9 numbers already placed?

 

[.Scott]

I'll call that selection of 9 cells that includes the middle cell , the 4 corner cells, and the 4 connecting cells, the "X Pattern". Each stroke of the X in the X pattern is a diagonal to the square and therefore the 5 cells in each stroke add up to 65.

I noticed that the 9 cells in the X pattern consist of 1 special cell (the center) and two ordered groups of four (the corners and the connectors). The corners and connectors are interchangeable. So if ((a),(b,c,d,e),(f,g,h,i)) is solvable, then so will be ((a),(f,g,h,i),(b,c,d,e)).

There are several hundred million X patterns. I believe I can complete an exhaustive search for a particular selection criteria in about 12 hours.

I can start with a parity search. Normally, with 9 numbers, there would be 512 parity combinations.
But X patterns are already constrained. If the center cell is odd, then the sum of the other cells in each diagonal must be even - and vice versa. So that should result in only 128 valid parity combinations. Perhaps some of those parity combinations are always solvable or always unsolvable.

If that doesn't bear fruit, I could try comparing the relative magnitudes of the cell values - or combinations of cell values.

 

[Vanadium 50]

The corners and connectors are interchangeable.

Why?

 

[mfb]

It's one of the more complex symmetries. For the diagonals and the central column/row, exchange inside with outside. For cells horizontally/vertically adjacent to the corner cells, exchange them in these pairs. You end up putting all numbers of the first row into the second row and vice versa and the same for all row/column pairs, while the diagonals and the central row/column keep their entries.

Matching symbols are cells that swap their place:

A	N	1	K	B
N	A	1	B	K
4	4	X	2	2
M	D	3	C	L
D	M	3	L	C

That produces another nine minus four theorem, because both configurations need to satisfy it. I'm not sure if this is a useful additional constraint - it might follow directly from row sums.

 

[Vanadium 50]

it might follow directly from row sums.

It does.

Starting with (and code tags were a great idea)..

A    1    N    2    B
1    a    n    b    2
L    l    X    m    M
3    d    k    c    4
D    3    K    4    C

Numbers are swaps irrelevant to Nine Minus Four, and the symmetry in question involves switching upper and lower case.

The original Nine Minus Four is:

a+n+b+l+m+d+k+c+X-A-B-C-D = 65

Under the symmetry it becomes:

A+N+B+L+M+D+K+C+X-a-b-c-d = 65

Adding, simplifying and rearranging gives (m+M+X+l+L) + (N+n+X+k+K) = 65 + 65, which is automatically satisfied by the row sums.

 

[Vanadium 50]

I'm wondering if subtracting instead of adding will help. That gives me (after some algebra):

2A + 2B + 2C + 2D + K + L + M + N + 3X = 195

If you apply the corner-connector symmetry mod 2, you get what I called the parity theorem above. This is, of course, stronger. However, the coefficients arouse suspicion: corners appear in 3 rows, the center in 4, and everything else 2. Here the coefficients are one less than that.

 

[WWGD]

Number of NxNs grows pretty fast :

https://www.trump.de/magic-squares/howmany.html

 

[WWGD]

I remember an analysis of Sudokus taken as matrices. Pretty sure there is one where Magic Squares ( solutions) are or can be viewed as matrices. Former was interesting but I did not see it sheding much light on related questions. Can't see why latter would be any better.

 

[Vanadium 50]

Number of NxNs grows pretty fast

I would say the reverse - the number of magic squares grows much, much more slowly than the number of squares. (n²!).

 

[mfb]

There are 2n independent sums that go roughly from 0 to n². (n²)!/(n²)²ⁿ still grows faster than the number of magic squares, but not that unreasonably faster.

For n=5 it's 3 orders of magnitude too high, for n=6 it's 3.5 orders of magnitude too high, for n=7 it's 4.5 orders of magnitude too high. For n=10 it's 7.5 orders of magnitude too high - but the number of magic squares is 10¹¹⁰.

This is purely curve-fitting, but 100(n²)!/(3n²)²ⁿ gives an almost unreasonably good approximation starting at n=5:

n	magic		approx		ratio
3	1			0.0936		10.68
4	880			74.24		11.85
5	275305224	275443828	0.999497
6	1.78E+19	1.48E+019	1.20
7	3.80E+34	2.76E+034	1.37
8	5.22E+54	3.72E+054	1.40
9	7.85E+79	6.64E+079	1.18
10	2.42E+110	2.69E+110	0.90

I don't see how this would lead to new constraints on n=5, however.

 

[Vanadium 50]

I was right to be suspicious that there was any gain to be had by the Corner-Connector Theorem in message 6. It rejects the same combinations that would be rejected by Nine Minus Four and Parity. However, it does so slightly more quickly - about 10% faster.

 

[Vanadium 50]

gives an almost unreasonably good approximation

I think you've found the equivalent of Koide sum rules.

There are some differences between magic squares of various sizes. For example, a 4x4 must either have row elements 0,1,2,3 mod 4 or a pair like 0,0,1,1. There are no valid rows with remainders 0,0,0,2, like 4,8,10 and 12. Or rather, the rows are valid, but are not incorporated in any magic squares. About 3/4 of the 4x4's have only elements of the first kind, and so are related to Latin squares. The other quarter aren't.

I have not found a similar rule for 5x5's. 6x6's get even more interesting because of the 36 officers problem. So there seems to be a complex relationship between Magic and Latin squares, and we know that the properties of Latin squares vary with n.

 

[.Scott]

I set up my computer to generate all possible X Patterns and to attempt to solve each one.
Since I change the middle cell first, when it reaches 13 and the next cell crosses from 12 to 14, I have reached the halfway point - and there will be symmetry in the stats between the first and second half.
It reach that halfway point in 5 hours.

There are approximately half a billion X Patterns.
Of those about 66.5% can be solved.
Of the 128 possible parity (even/oddness) combinations in a valid X Pattern, none were 0% or 100% solvable.
At the halfway point, the solvability within those 128 combinations ranges from 51.72% solvable (when all 9 are odd) to 72.75% (when only the center is odd).

If anyone has a specific test that want run against those half billion combinations, let me know. I can set it up and run it in the background.

The result is a 3.5 page report - which I have attached.
Those little 5x5 icons show the Odd/Even selections for each column and row. The symbols in those icons are 1's (odd) and 0's (even).

Some time after 10pm EDT (when the program completes), I will post the full stats.

 

[mfb]

There are about 1/4 of a billion solutions excluding rotations and mirror symmetry, if 2/3 of your half a billion X patterns can be solved (despite using the corner-connector symmetry) then you still have some symmetry that is not considered?

If you fix the X, what is the typical distribution of solutions? Are patterns with multiple solutions common?

 

[.Scott]

The way the program is currently written, it only looks for the first solution for each X Pattern.
If you want, when it finished, I will recode it to collect more - then run it overnight.

 

[mfb]

I'm more interested in the rough behavior, a few thousand random patterns would give that already.

 

[Vanadium 50]

Of the 128 possible parity (even/oddness) combinations in a valid X Pattern, none were 0% or 100% solvable.

I would be interested in mod 5 combinations, if that is simple.

 

[Vanadium 50]

As if people haven't guessed, I am doing exhaustive searches, and trying to be smarter about it.

B F D G C
H B D C J
E E A E E
J C D B J
C G D G B

I start by placing the center A. Then the diagonals B and C, from a set of rows that sum to 65 - A. Then the horizontal and vertical middles from the same set of rows, applying the variation of the Corner-Connector theorem discussed above. At this point there are 8 numbers left. I pick one for F and complete the cells labeled G, and then pick a different one for H and complete the cells labeled J. Then I test the square for magicness, which at this point is a test that each number is used exactly once.

About 90% of the time is spent testing and placing Row E. So anything that can be applied at step D or sooner will help.

 

[.Scott]

Here are the numbers for the full parity (odd/even combinations) report:
499,121,280 X Pattern Combinations
326,948,224 are solvable (65.5048%).
172,173,056 have no solution

The report is attached.

Here is the code:

/*
File: M55.cpp
   Program for walking through all valid "X Patterns" and checking each
  one for a 5x5 Magic Square solution.

   Scott Bowden
   August 13, 2020
*/#include <stdio.h>
#include <memory.h>

/* X Pattern count, solvable, unsolvable */
int nRLine, nRSLine, nRNLine;

/* The 5x5 work area */
int M5[25];

/* Bit mask for the numbers 1 to 25 (to check for duplicate numbers */
int B25[26] = { 0,
  0x01000000, 0x00800000,  0x00400000,  0x00200000,  0x00100000,
  0x00080000, 0x00040000,  0x00020000,  0x00010000,  0x00008000,
  0x00004000, 0x00002000,  0x00001000,  0x00000800,  0x00000400,
  0x00000200, 0x00000100,  0x00000080,  0x00000040,  0x00000020,
  0x00000010, 0x00000008,  0x00000004,  0x00000002,  0x00000001,
};

/*
Codes for the 5 horizontal sums, 5 vertical sums, and 2 diagonal sums.
Each must sum to 65.
*/
#define H1  0
#define H2  1
#define H3  2
#define H4  3
#define H5  4
#define V1  5
#define V2  6
#define V3  7
#define V4  8
#define V5  9
#define D1 10
#define D2 11

/*
There are 512 parity combinations - but only 128 occur in valid X Patterns.
Here are the tally arrays for the total, solvable, and unsolvable counts.
*/
int naParity[512], naParityS[512], naParityN[512];

/*
Pointers for easy access into the Parity Tally arrays.
*/
const int *pT0 = naParity+0;
const int *pT1 = naParity+64;
const int *pT2 = naParity+128;
const int *pT3 = naParity+192;
const int *pT4 = naParity+256;
const int *pT5 = naParity+320;
const int *pT6 = naParity+384;
const int *pT7 = naParity+448;
const int *pS0 = naParityS+0;
const int *pS1 = naParityS+64;
const int *pS2 = naParityS+128;
const int *pS3 = naParityS+192;
const int *pS4 = naParityS+256;
const int *pS5 = naParityS+320;
const int *pS6 = naParityS+384;
const int *pS7 = naParityS+448;
const int *pN0 = naParityN+0;
const int *pN1 = naParityN+64;
const int *pN2 = naParityN+128;
const int *pN3 = naParityN+192;
const int *pN4 = naParityN+256;
const int *pN5 = naParityN+320;
const int *pN6 = naParityN+384;
const int *pN7 = naParityN+448;

/* Indices of the horizontal, vertical, and diagonal lines */
int T5[12][5] = {
  {  0,  1,  2,  3,  4 },
  {  5,  6,  7,  8,  9 },
  { 10, 11, 12, 13, 14 },
  { 15, 16, 17, 18, 19 },
  { 20, 21, 22, 23, 24 },
  {  0,  5, 10, 15, 20 },
  {  1,  6, 11, 16, 21 },
  {  2,  7, 12, 17, 22 },
  {  3,  8, 13, 18, 23 },
  {  4,  9, 14, 19, 24 },
  {  0,  6, 12, 18, 24 },
  {  4,  8, 12, 16, 20 }
};

/*
Instructions for building a Magic 5x5 square.
  LS,LO = C, -1:  Try all remaining value for cell #C
  LS,LO = C, L:   Compute the value of cell #cell by completing line #L
*/
int LS25[25] = {12,  0,  6, 18, 24,  4,  8, 16, 20,  1, 11, 21,  2,  3, 13, 23, 22, 10, 14,  5, 15,  7,  9, 17, 19};
int LO25[25] = {-1, -1, -1, -1, D1, -1, -1, -1, D2, -1, -1, V2, -1, H1, -1, V4, H5, -1, H3, -1, V1, -1, H2, V3, H4};

bool Solve25(int nLevel, int nB25L);
void Tally(bool bSolved);
void Report(bool bSolved);
void Report512(void);int main(int argv, void*argc[])
{
  nRLine  = 0;
  nRSLine = 0;
  nRNLine = 0;
  memset(naParity,0,sizeof(naParity));
  memset(naParityS,0,sizeof(naParity));
  memset(naParityN,0,sizeof(naParity));
  Solve25(0, 0x01FFFFFF);
  printf("Final Report:\n");
  printf(
    "Final Report: %6.1d = %6.1d(solved) + %6.1d(unsolved)\n",
     nRLine, nRSLine, nRNLine
  );

  Report512();

  printf("Done\n");
  getchar();
}

/*
Solve25 (recursive):
  nLevel: Which level of recursion (and cell count) we are working on.
  nB25L:  Mask indicating which numbers have not been used so far.

  return: Whether a solution was found.

Up to level 8, we are completing the X Pattern.
At level 8, we tally the results and periodically generate a report.
Also, at level 8, we always return false to force a search through all
X Patterns.
*/

bool Solve25(int nLevel, int nB25L)
{
  bool bReport, bResult;
  int  n, nLS, nLO, nNext, nPick, nMask;

  if(nLevel>=25) return true;
  bReport = nLevel == 8;
  nLS = LS25[nLevel];
  nLO = LO25[nLevel];
  nNext = nLevel+1;
  if(nLO>=0) {
    nPick = 0;
    for(n=0;n<5;n++) nPick += M5[T5[nLO][n]];
    nPick = 65 - nPick;
    if((nPick<=0)||(nPick>25)) return false;
    nMask = B25[nPick];
    if((nMask & nB25L)==0) return false;
    M5[nLS] = nPick;
    bResult = Solve25(nNext,nB25L-nMask);
    if(bReport) {
       Report(bResult);
       bResult = false;
    }
  } else {
    nMask = 0x01000000;
    for(nPick=1;nPick<=25;nPick++,nMask = nMask>>1) {
      if((nB25L & B25[nPick])==0) continue;
      M5[nLS] = nPick;
      bResult = Solve25(nNext, nB25L-nMask);
      if(bReport) {
         Report(bResult);
         bResult = false;
      }
      if(bResult) break;
    }
  }
  M5[nLS] = 0;
  if(nNext>=25) bResult = true;
  return bResult;
}

void Report(bool bSolved)
{
  Tally(bSolved);
  if(nRLine % 10000) return;

  printf(
    "%6.1d=%6.1d+%6.1d: %2d xxx %2d; x %2d x %2d x; xx %2d xx; x %2d x %2d x; %2d xxx %2d, %s\n",
     nRLine, nRSLine, nRNLine,
     M5[0], M5[4], M5[6], M5[8], M5[12], M5[16], M5[18], M5[20], M5[24],
     bSolved ? "Solved" : "None"
  );
  Report512();
}

void Report512(void)
{
  int i;

  for(i=0;i<64;i++) {
    printf(
       "%2d: %1s%7d%7d%7d |%1s%7d%7d%7d |%1s%7d%7d%7d |%1s%7d%7d%7d |%1s%7d%7d%7d |%1s%7d%7d%7d |%1s%7d%7d%7d |%1s%7d%7d%7d\n",
       i,
       ((pT0[i]>16)&&((!pS0[i])!=(!pN0[i])))?"*":" ", pT0[i], pS0[i], pN0[i],
       ((pT1[i]>16)&&((!pS1[i])!=(!pN1[i])))?"*":" ", pT1[i], pS1[i], pN1[i],
       ((pT2[i]>16)&&((!pS2[i])!=(!pN2[i])))?"*":" ", pT2[i], pS2[i], pN2[i],
       ((pT3[i]>16)&&((!pS3[i])!=(!pN3[i])))?"*":" ", pT3[i], pS3[i], pN3[i],
       ((pT4[i]>16)&&((!pS4[i])!=(!pN4[i])))?"*":" ", pT4[i], pS4[i], pN4[i],
       ((pT5[i]>16)&&((!pS5[i])!=(!pN5[i])))?"*":" ", pT5[i], pS5[i], pN5[i],
       ((pT6[i]>16)&&((!pS6[i])!=(!pN6[i])))?"*":" ", pT6[i], pS6[i], pN6[i],
       ((pT7[i]>16)&&((!pS7[i])!=(!pN7[i])))?"*":" ", pT7[i], pS7[i], pN7[i]
    );
  }
}

#define X0 (*(M5+12))
#define X1 (*(M5+ 6))
#define X2 (*(M5+ 8))
#define X3 (*(M5+18))
#define X4 (*(M5+16))
#define X5 (*(M5+ 0))
#define X6 (*(M5+ 4))
#define X7 (*(M5+24))
#define X8 (*(M5+20))

void Tally(bool bSolved)
{
  int nParity, nParityA, nParityB;

  nParityA = (X1&1) + ((X2&1)<<1) + ((X3&1)<<2) + ((X4&1)<<3);
  nParityB = (X5&1) + ((X6&1)<<1) + ((X7&1)<<2) + ((X8&1)<<3);
  nParity  = (X0&1) + (nParityA<<1) + (nParityB<<5);
  nRLine ++;
  naParity[nParity]++;

  if(bSolved) {
    nRSLine++;
    naParityS[nParity]++;
  } else {
    nRNLine++;
    naParityN[nParity]++;
  }
}

 

[.Scott]

@Vanadium 50 - Hmmm. Mod 5 would be 5^7 = 78,125 bins. Times 2 for the total and success count 156,250. And I plan on doing a solution count - so it would be times 4 or 5 instead of 2. 312,500 bins ... a much longer report.
I will have to make a good summary.

@mfb is correct that a random sampling will do - but I've coded it as a single reentrant search and I'm looking to minimize my coding time, not the execution time.

 

[mfb]

Then I test the square for magicness, which at this point is a test that each number is used exactly once.

I would expect a significant speed-up if you don't place duplicates (i.e. check for duplicates before plugging in numbers). @.Scott's code finds 330 million solutions - I'm not sure how many of them are linked via symmetry, but it seems to be a relevant fraction of all of them. With a bit more optimization it might produce a full list?

- for the central value it's sufficient to test numbers from 1 to 13.
- we can require n(0,0) to be the largest number on all diagonals, that kicks out 7/8 of the search space that would just be filled with symmetric solutions. This is done early so it should save 7/8 of the time.
- we can require n(0,4)>n(4,0) to kick out mirrored solutions
- rearranging the order of the cells to get the central row/column early would allow using the nine minus four theorem early

 

[.Scott]

Restating part of what @mfb said:

The connector cells (1,1), (1,3), (3,1), and (3,3) can be swapped as a group with the corner cells (0,0), (0,4), (4,0), and (4,4).
The 5x5 can be rotated into any 1 or 4 positions.
So, we can check for n(0,0) larger than any diagonal or connector. That's 1 in 8.
Then we can do the mirror check (0,4) > (4,0) to get us to 1 in 16.

Without the checks above, the results of the first half mirror the results from the second half when the middle value is 13 and the first corner value sequences from 12 to 14. But with the optimizations, that would not happen - so cutting off half way would not allow you to regenerate the full stats.

Up until now, I have been using the symmetries as a check for the proper operation of the code. The way the code is written, there is no reason that the code would correctly solve one pattern just because it had done its other 15 "rotations" correctly - so it made for good checks.

 

[.Scott]

There are just over 29 million X Patterns with the middle square either 1 or 2.

I generate a report every 100,000. Here are the two reports that bracket the end of (2,2)==2 and (2,2)==3:
29000000=13712644(0)+2612491(1)+2728455(2)+1874153(3)+1839203(4)+1188232(5)+1130397(6)+3914425(many)
29100000=13772692(0)+2622909(1)+2736960(2)+1879235(3)+1843617(4)+1191014(5)+1132689(6)+3920884(many)

What this report is saying is that:
13.7 million do not have a solution. (higher than usual because (2,2)==1 and (2,2)==2 are harder to solve)
2.6 million have exactly 1 solution.
2.7 million have exactly 2 solutions.
1.9 million have exactly 3 solutions.
1.8 million have exactly 4 solutions.
1.2 million have exactly 5 solutions.
1.1 million have exactly 6 solutions.
3.9 million have seven or more solutions.

This pattern roughly follows in each of the 128 parity bins. In all parity cases, the plurality of X Patterns with solutions is either exactly 1 solution or exactly 2 solutions. In all parity cases, there are many in the 7+ solutions bin.

 

[Vanadium 50]

I would expect a significant speed-up if you don't place duplicates (i.e. check for duplicates before plugging in numbers).

Done. Once I place a row, I remove other rows that share elements.

for the central value it's sufficient to test numbers from 1 to 13.
- we can require n(0,0) to be the largest number on all diagonals, that kicks out 7/8 of the search space that would just be filled with symmetric solutions. This is done early so it should save 7/8 of the time.
- we can require n(0,4)>n(4,0) to kick out mirrored solutions
- rearranging the order of the cells to get the central row/column early would allow using the nine minus four theorem early

All already done.

Originally, I filled by cells, not by rows. Filling by rows is faster, but less than an order of magnitude faster.

 

[Vanadium 50]

13.7 million do not have a solution.

These are the key, I think. If there is some common feature that can be identified, these could be removed early.

 

[Vanadium 50]

Here are the numbers for the full parity (odd/even combinations) report:

@.Scott , I'm trying to make sure I understand the report and am reading it right. (0,0) has the pattern:

0 - - - 0
- 0 - 0 -
- - 0 - -
- 0 - 0 -
0 - - - 0

Correct?

Then the fact that it's blank means that there is no solution of that form. Again, correct? We of course don't expect one, because the sum of five even numbers is even, and 65 is not.

On the other hand, (1,0) has the pattern:

0 - - - 0
- 0 - 0 -
- - 1 - -
- 0 - 0 -
0 - - - 0

and 72.5% of the numbers of that form lead to magic squares.

The conclusion that we see 128 non-zero entries is that there is no test relying solely on the parities of the diagonals formed by valid rows that will be helpful.

For example, we know there are no squares of the form:

14   X   X   X  20
 X  15   X  10   X
 X   X   1   X   X
 X  13   X  16   X
21   X   X   X  19

But this would not be found by a parity test since there are other solutions of the form

0  X   X  X  0
X  1   X  0  X
X  X   1  X  X
X  1   X  0  X
1  X   X  X  1

(which is your category 41-5). Do I understand?

 

[.Scott]

@Vanadium 50
Q1: (0,0) has all zeroes - right.
Q2: It is blank because there are no valid X Patterns with that odd/even pattern - right
Q3: (1,0) has the pattern with 1 in the middle - right
Q4: 72.5% of those can form a magic square - more precisely, 72.75%
Q5: Conclusion is that parity doesn't help - right

Yes, you appear to understand.
If there was any way to use parity, it would have shown up as 0% or 100% somewhere in the table.

 

[mfb]

Without the checks above, the results of the first half mirror the results from the second half when the middle value is 13 and the first corner value sequences from 12 to 14. But with the optimizations, that would not happen - so cutting off half way would not allow you to regenerate the full stats.

Why not? Every magic square with the central number of 14 has an equivalent magic square with a central number of 12, removing symmetries within the squares with a 12 doesn't change that. The number-mirrored pattern will show up with a different orientation, sure.

 

[.Scott]

I did a solution count using the reduction by 16
(x4 for rotation; x2 for mirror, x2 for corner/connector swap)

All numbers below should be multiplied by 2 to undo the corner/connector swap or by 16 to undo all transformations.

31,195,080 (x16) total X Patterns
10,760,816 (x16) with no Magic 5x5 solution.
2,662,578 (x16) with exactly 1 solution
2,937,296 (x16) with exactly 2 solutions
2,176,700 (x16) with exactly 3 solutions
2,240,956 (x16) with exactly 4 solutions
1,578,934 (x16) with exactly 5 solutions
1,558,920 (x16) with exactly 6 solutions
7,278,880 (x16) with seven or more solutions

The total number of solutions found was: 137,652,612
@WWGD provided us with this link: https://www.trump.de/magic-squares/howmany.html
137,652,612 is exactly half the value shown in cell B5 at that web page - they're eliminating mirror and rotate only.

 

[.Scott]

Why not? Every magic square with the central number of 14 has an equivalent magic square with a central number of 12, removing symmetries within the squares with a 12 doesn't change that. The number-mirrored pattern will show up with a different orientation, sure.

The X Patterns with (2,2)=1 to 12 mirror (2,2)=14 to 25 - after reversing the values (1...25) => (25...1).
But when (2,2) = 13, there is no ready way to get that (1...25) => (25...1) effect if you are using the other filters.

If you are only interested in whether there are any 0% or 100% values this wouldn't matter. But if your looking to collect full stats, it doesn't work.

 

[Vanadium 50]

My thinking on other moduli besides parity goes like this:

If you add up all the rows and columns (10) you get 650. If you include the diagonals (3) you get 780. In the global sum, the middle cell contributes 4x, the rest of the diagonals 3, and every other cell 2.

If you look for a rule mod 3, it removes the diagonals except for the center cell. But they aren't going to tell us anything since their sum is fixed.

I doubt that mod 4 will help, since the only difference is the center cell with respect to the bulk. I think .Scott's study kills that.

Next up is 5. I think mod 5 might be interesting not because of sums, but that it would potentially exclude patterns that use too many 5's, or not enough 2's or something.

 

[mfb]

But when (2,2) = 13, there is no ready way to get that (1...25) => (25...1) effect if you are using the other filters.

You can't stop halfway through 13, yes, but you don't need to check 14-25 in the center.

The total number of solutions found was: 137,652,612

Great! You found code that can find all solutions.

 

[.Scott]

Yesterday I ran the full thing without the x16 optimizations - just so I had a way of further validating the x16 results. That is just fishing up now (about 24 hours). My laptop had 4 cores - so I can run two of these without them slowing each other down. Their effect on other things I have doing on my computer is also mild.

Next up is 5. I think mod 5 might be interesting not because of sums, but that it would potentially exclude patterns that use too many 5's, or not enough 2's or something.

I agree, mod 5 is next - but I might post some other results I generated yest.

 

[mfb]

If you store 16 of the values in each solution the others can be derived trivially. Even without an effective compression that's 16 bytes per solution, or 2.2 GB. Or 3.4 GB when storing all 25. Small enough to store all solutions. Running algorithms over the stored solutions might be much faster than solving magic squares each time.

 

[Vanadium 50]

Here are some of the diagonal rows that do not lead to a solution. They come in pairs, with a reflection of the (edit:) connectors I don't see an obvious pattern mod 5.

For a center value of 1, the upper left corner (defined to be the smallest) runs from 13 to 24.

18 13 1 14 19
18 14 1 13 19
18 12 1 15 19
18 15 1 12 19
18 11 1 16 19
18 16 1 11 19
17 10 1 18 19
17 18 1 10 19
...
13 2 1 24 25
13 24 1 2 25
24 2 1 13 25
24 13 1 2 25
...
18 12 2 14 19
18 14 2 12 19
18 11 2 15 19
18 15 2 11 19
...
24 2 13 1 25
24 1 13 2 25

 

[mfb]

These pairs are coming from another symmetry we didn't consider before. Swap the second and fourth row, swap the second and fourth column. The row and column sums stay the same as each operation doesn't change them, and the diagonals stay the same as we just swap the inner values across the center. That means we can require e.g. n(1,1)>n(3,3) and get the other solutions from symmetry.

Excluding global rotations and reflections there are 275305224 = 2³ * 3 * 109 * 105239 solutions.
* Inverse 1-25 order: 2
* Corner/connector symmetry: 2
* This new symmetry: 2
This means we found all symmetries with a factor 2. There might be one more with three options, even though 3 is an odd number (in both meanings). I don't expect more symmetries.

Edit: Interestingly, this has implications for magic squares where the center is 13, where the 1-25 symmetry could mimic one of the other symmetries in principle. It seems to do this in an even number of times.

 

[Vanadium 50]

275305224 = 23 * 3 * 109 * 105239 solutions

That is a very, very interesting way of looking at it. However, it mixes center = 13 with center <> 13 solutions, with the latter coming in pairs. Also, it's probably not likely there is a symmetry that takes a number in the center and moves it outside. So we should probably look at numbers of squares by center square value.

01: 4365792 = 2⁵ x 3³ x 31 x 163
02: 5464716 = 2² x 3 x 455393
03: 7659936 = 2⁵ x 3² x 26597
04: 7835348 = 2² x 1958837
05: 9727224 = 2³ x 3 x 13 x 31177
06: 10403516 = 2² x 523 x 4973
07: 12067524 = 2² x 3² x 7²x 6841
08: 12448644 = 2² x 3 x 13 x 199 x 401
09: 13890160 = 2⁴ x 5 x 23 x 7549
10: 13376136 = 2³ x 3 x 557339
11: 15735272 = 2³ x 7² x 137 x 293
12: 15138472 = 2³ x 1892309
13: 19079744 = 2⁶ x 47 x 6343

So it looks like we have all the 2-way symmetries (smallest exponent is 2).

 

[mfb]

Ah, right, we can't guarantee anything for the solutions with 13.

Okay, general 2-way symmetries are done. And I assume from your post that you have a program that can find all solutions now, too.
There is no other common factor, so we are not missing any other universal symmetry. There might be more to find with 13 in the center.

 

[Vanadium 50]

And I assume from your post that you have a program that can find all solutions now, too.

I've had one for a long time. But a) it runs slowly, and b) I am trying to learn things. (Wouldn't it have been interesting if there were a 109-symmetry?)

 

[mfb]

Fast enough to be useful was implied.
There are more powers of 3 than you would expect naively but I would be surprised to see that linked to symmetry.

 

[Vanadium 50]

I'm struggling with my code.

I have code that finds all the combinations. I changed the print routine so that now when it finds one combination, it prints out the other 7 that can be derived from it (3 if the center value is 13). So it counts 8 times as many. So far so good.

Let's simplify things by ignoring the cases where we change the center square. So every time we find a square, we find four. Again, so far so good.

Now I want to avoid the duplicates. This is not so simple. I can define the square's orientation by requiring the smallest corner to be in the top left and for the top right corner to be larger than the bottom left (and I do). But a simple thing like requiring the top left connector be larger than the top left corner does not work. ("work" defined by "getting the right answer" and "runs twice as fast", neither of which is the case)

 

[mfb]

Do you know what breaks if you do that?

 

[Vanadium 50]

Too many squares and not enough reduction in time.

For example.

14  2   8  25  16
 3 17  23   9  13
24 22   1   7  11
 5 20  12  18  10
19  4  21   6  15

appears at least twice. Once as a found square, and once as a 2-4 permutation of the following square.

14  25   8   2  16
 5  18  12  20  10
24   7   1  22  11
 3   9  23  17  13
19   6  21   4  15

 

[mfb]

See post 36 where I first describe this symmetry:

That means we can require e.g. n(1,1)>n(3,3) and get the other solutions from symmetry.

 

[Vanadium 50]

Thanks - that works. (Once I figured out that 1 meant "second row" and 3 meant "fourth".) I get the right number of squares, and a speedup of 1.65. Not the two I hoped for, but still pretty good,

So that's one factor of two. Where is the other one hiding?

Also, when looking at the patterns scroll by, it's impressive how slowly the main diagonal changes. You might think "that makes sense - there are millions of squares but only thousands of ways to add up to 65, so I expect thousands per main diagonal". That's correct. But there are also ones with zero, so it's not so simple.

Further, if printing them out, every so often it pauses for a second or two. That means there are hundreds of thousands of non-squares in a row. I wonder what is happening here.

 

[mfb]

I like to start an index at 0.

So that's one factor of two. Where is the other one hiding?

I lost track, relative to what version?

That means there are hundreds of thousands of non-squares in a row. I wonder what is happening here.

Diagonals with no solution?
I wonder if machine learning could provide some insight here. Feed it half of the diagonals without a solution and half of the diagonals with one, see if it can get predictions for the other half right and then look if there are understandable rules it found.

 

[Vanadium 50]

I like to start an index at 0.

Like French elevators.

I lost track, relative to what version?

I take a square. I apply the two symmetries and get four squares, I apply the n(3,3)-n(1,1) constraint and I have 2 left - that is, I find every square twice. I'd like to find every square once.

Diagonals with no solution?

Yes. I am not sure what ML would tell me that a list of successes and failures does not. Especially something like a NN where the work is being done through a hidden layer. But something like this seems more useful for 6x6 squares and improving the estimate of the number of solutions.

 

[mfb]

Hmm... we might link the rotation symmetry with the corner/connector symmetry in a bad way. After requiring that (0,0) is the largest corner, we might need to require that it's larger than all connectors (instead of just (1,1)). That makes sure we get each case exactly once, the symmetric squares then have the largest element of the diagonals in the connectors. After that n(1,1)>n(3,3) can be checked as before.

Edit: Forgot that part. Yes, extracting patterns from the machine learning output is not necessarily easy. One would start with very simple setups. All parity-like patterns could be found by simple checking all different ways to sum/subtract numbers.

 

[Vanadium 50]

we might need to require that it's larger than all connectors (instead of just (1,1)).

That's not enough. About 15% of the squares are found more than once.

 

[mfb]

How? Do you have examples of what is still being found multiple times?