5x5 Magic Squares

  • I
  • Thread starter Vanadium 50
  • Start date
  • Featured
  • #1
Vanadium 50
Staff Emeritus
Science Advisor
Education Advisor
2019 Award
25,119
8,232

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 N2 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?
 
  • Like
Likes WWGD, .Scott, dRic2 and 1 other person

Answers and Replies

  • #2
.Scott
Homework Helper
2,615
950
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.
 
  • #3
Vanadium 50
Staff Emeritus
Science Advisor
Education Advisor
2019 Award
25,119
8,232
The corners and connectors are interchangeable.
Why?
 
  • #4
34,655
10,799
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:
Code:
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.
 
  • Like
Likes nuuskur, Vanadium 50 and .Scott
  • #5
Vanadium 50
Staff Emeritus
Science Advisor
Education Advisor
2019 Award
25,119
8,232
it might follow directly from row sums.
It does.

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

Code:
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.
 
  • Informative
Likes mfb
  • #6
Vanadium 50
Staff Emeritus
Science Advisor
Education Advisor
2019 Award
25,119
8,232
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.
 
  • #8
WWGD
Science Advisor
Gold Member
2019 Award
5,341
3,295
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.
 
  • #9
Vanadium 50
Staff Emeritus
Science Advisor
Education Advisor
2019 Award
25,119
8,232
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. (n2!).
 
  • Like
Likes WWGD
  • #10
34,655
10,799
There are 2n independent sums that go roughly from 0 to n2. (n2)!/(n2)2n 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 10110.

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

Code:
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.
 
  • Like
Likes WWGD
  • #11
Vanadium 50
Staff Emeritus
Science Advisor
Education Advisor
2019 Award
25,119
8,232
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.
 
  • #12
Vanadium 50
Staff Emeritus
Science Advisor
Education Advisor
2019 Award
25,119
8,232
gives an almost unreasonably good approximation
I think you've found the equivalent of Koide sum rules. :wink:

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.
 
  • #13
.Scott
Homework Helper
2,615
950
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.
 

Attachments

Last edited:
  • Like
Likes Vanadium 50
  • #14
34,655
10,799
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?
 
  • #15
.Scott
Homework Helper
2,615
950
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.
 
  • #16
34,655
10,799
I'm more interested in the rough behavior, a few thousand random patterns would give that already.
 
  • #17
Vanadium 50
Staff Emeritus
Science Advisor
Education Advisor
2019 Award
25,119
8,232
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.
 
  • #18
Vanadium 50
Staff Emeritus
Science Advisor
Education Advisor
2019 Award
25,119
8,232
As if people haven't guessed, I am doing exhaustive searches, and trying to be smarter about it.

Code:
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.
 
  • #19
.Scott
Homework Helper
2,615
950
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:
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]++;
  }
}
 

Attachments

Last edited:
  • #20
.Scott
Homework Helper
2,615
950
@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.
 
  • #21
34,655
10,799
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
 
  • #22
.Scott
Homework Helper
2,615
950
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.
 
  • #23
.Scott
Homework Helper
2,615
950
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.
 
  • #24
Vanadium 50
Staff Emeritus
Science Advisor
Education Advisor
2019 Award
25,119
8,232
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.
 
  • #25
Vanadium 50
Staff Emeritus
Science Advisor
Education Advisor
2019 Award
25,119
8,232
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.
 

Related Threads on 5x5 Magic Squares

  • Last Post
Replies
8
Views
4K
  • Last Post
Replies
9
Views
4K
  • Last Post
Replies
1
Views
5K
  • Last Post
Replies
3
Views
3K
  • Last Post
Replies
8
Views
845
  • Last Post
Replies
3
Views
2K
  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
10
Views
5K
  • Poll
  • Last Post
Replies
11
Views
4K
  • Last Post
Replies
8
Views
2K
Top