Can New Theorems Predict Incomplete 5x5 Magic Square Solutions?

[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?

 

[Vanadium 50]

How?

Bug.

 

[Vanadium 50]

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

Thanks your your help!

The bug was that one test was performed twice and another zero times. It's looking like it takes ~20 hours to find all the squares, which is much better than the 458h it took at the beginning of this.

What's impressive is that once the diagonals and the center row and column are placed, 5% of the time we find a magic square. Technically, 0.6% of the time we find 8. But if you just place those 17 numbers at random the probability of finding a magic square is about 4 x 10^-7. So we're doing a million times better.

I find @.Scott 's numbers very intriguing. About half of the X-patterns have no solution. That's potentially a factor of 2 right there, and the rule may be applicable elsewhere.

I had considered parallelizing this, but it's not trivial. Part of the reason is that the code was not designed that way; there's a single Square object, and part of the problem is that parallelizing by center element leaves you with a maximum of 13 workers and a very unbalanced system.

 

[Vanadium 50]

It takes 75774 seconds to do an exhaustive search.

I looked at the main diagonals mod 5. There are three patterns, which I call a straight (e.g. 20134), two pair (e.g. 33144), and three of a kind (e.g. 31114). All three are present, so if there is a way to identify non-solutions mod 5, it will involve both diagonals.

I plan to parallelize with pThreads. Load balancing will come later, but I will probably do it at the main diagonal level. Each thread will look at every Nth element in that list of rows. The machine this will run on has 12 cores and 24 threads. so I suspect N will be 25. Fully load balanced, I imagine it will take between 1 and 2 hours to run.

 

[mfb]

No five of a kind is a little bit of information.

 

[Vanadium 50]

Not so much, since the only 5 of a kind that works is all 3's. That's a single row for a few cases.

 

[mfb]

Wait, so it exists?
And why does it need to be all 3s, unless that's a non-trivial result?

 

[Vanadium 50]

3+8+13+18+23 = 65 The other fives of a kind don't add up to the right number. Further, there's only one such row (and its permutations) for every center square.

 

[mfb]

Oh right, the limit to 1-25 restricts that.

 

[Vanadium 50]

So, I managed to rework the parallelization and got it down to under an hour. Barely. I can find all 275M squares in 59 minutes and 23 seconds. This uses 32 threads on a 12C/24T processor. It's 22.9x faster than one processor.

About ten minutes towards the end, threads start terminating. So there is some room to improve the load balancing: perhaps 5%. This is mitigated somewhat by the fact that as threads terminate, the chip speeds up.

Another potential source for a 5% gain is squares with 13 as their center. If I find a square with 12 as its center, I have also found one with a 14 as its center, under the {26-x} transformation. If I do with with a square with center 13, I find a different square with center 13. So effectively I find each pair twice. If I could find a way to quickly reject the "second" member of the pair, it would double the speed of the 13's, saving maybe 5% overall in time.

That same symmetry has interesting implications for early detection of patterns with no solution. There's been speculation that looking at subsets of cells (one or two diagonals) mod 5 one can conclude there are no solutions. Because of the {26-x} symmetry, should such a pattern be found, a second pattern could be found swapping 0 and 1, and 2 and 4. I think that's very interesting as it is not the "normal" 1 and 4/2 and 3.

I'm not sure if this is a breakthrough or proves it impossible.

 

[Vanadium 50]

Here are the scaling plots (for center = 1 and 25):

 

[mfb]

It's getting difficult to disentangle the different cuts. What do we have so far:
* The upper left corner is the largest element on the diagonals (excluding the center, but if the center is 13 it's trivially true for that as well). This covers rotation and the corner-connector symmetry
* The upper right corner is larger than the lower left corner. This covers mirrored cases.
* The upper left connector is larger than the lower right connector. This covers the 2/4 exchange symmetry.

If we apply the 1<->25 swap to a solution then we have to rearrange everything to fit that pattern again. We would need an inequality that's guaranteed to swap.

Here is an approach that separates the symmetries better:
* The sum of the corners needs to be larger than the sum of the connectors (can they be equal? That would need to be treated separately). This covers only the corner-connector symmetry.
* The upper left corner is the largest corner
* The upper right corner is larger than the lower left corner.
* The upper left connector is larger than the lower right connector.

If we apply the 1-25 swap then the first condition gets reversed, so clearly we need to do the corner/connector swap. In general we might have to rotate and mirror the magic square, and it's possible that we need to use the 2/4 exchange.

I didn't find a nice way to throw away 1/2 of the magic squares, but I found a classification: Consider the center row/column. If the sum of the outer numbers is larger than the sum of the inner numbers, then this is still true after the 1-25 swap and applying the corner/connector symmetry. This splits our sample of magic squares (with 13 in the center) into two groups. Maybe one of the groups is empty, or has some nice patterns?

 

[Vanadium 50]

Here is what I do:

A B C D E
F G H I J
K L M N O
P Q R S T
U V W X Y

First place M.

Second, place main diagonal, requiring:

• A is smallest of {A,G.S,Y}
• S > G

Third, place opposite diagonal, requiring:

• A is smaller than {E,I,U,Q}
• U > E

Fourth, place center vertical column.
Fifth, place center horizontal row requiring

• 3M+2(A+E+U+Y)+(C+W)+(K+O)=195 (Parity + NineMinusFour rolled into one)
• A range check on the 8 remaining numbers, which gives me a 1% speedup. For example, if 65-A-C-D = 4 and the smallest of the eight remaining numbers is 4, I know there's no solution.

Finally, with the 8 remaining numbers, pick 2 for B and F and complete. Test for validity and uniqueness. Print base square and the 7 (3 if M=13) that derive from it.

You are right that I could divide my M=13 set into two based on C,K,O and W (or H, L, N and R). The problem is that this information arrives late in the process. By the time I get to the 6th step, I have only 56 tests remaining.

I'm doing some detailed profiling now, but most time is spent in Steps 4 and 5.

I'd also need to do a bit of work to place a cut in Step 4. I started off using a stl::list of rows, filtering at each step. I discovered half the time was spent in the row constructor. So I replaced the Step 5 stl::list with an stl::vector. This helped (although I am spending a frightful amount of time clearing vector elements) but for some reason cuts at Step 4 cause a double free somewhere. So a test would be slow - I'd need to clean up that mess first.

The way I load-balance is to have thread X look at rows in Step 1 with number mod N (number of threads) equal to X. As you see, it works pretty well, but not perfectly. Some rows take longer to go through than others, and I am counting on them averaging out. Putting more intelligence in would help: e.g. if I know that for M=1 thread 6 takes the least time and 9 the most, and for M=2, 11 takes the least and 4 the most, I would reassign the work so that the thread that handled 6 (9) for M=1 gets 4 (11) for M=2.

 

[Vanadium 50]

Some timing:

Steps 1-3 take < 1% of the time.
Step 4 - 14%
Step 5 - 64%
Step 6 - 22%

I thought Step 6 is smaller than it was because the cost of determining you don't have to do a calculation is comparable to the cost of doing the calculation.

With -Ofast, gprof tells me 92% of the time is spent finding squares and 3% checking that candidate magic squares are in fact magic. Another 5% is spent checking rows to see if they can be placed (steps 2,3 and 5).

Without-Ofast, 28% of the time is spent handling C++ overloading. I can get cells with with x,y coordinates or a single 5*x+y coordinate. 6.5% is spent seeing if numbers are used, and everything else is a few percent her and a few percent there.

 

[Vanadium 50]

So I was motivated by the work of @.Scott . I took all the solutions mod 5 and plotted the patterns looking only at the 3's on the diagonals. There are 511 such patterns. An astonishing 179 have no solutions.

 

[.Scott]

So I was motivated by the work of @.Scott . I took all the solutions mod 5 and plotted the patterns looking only at the 3's on the diagonals. There are 511 such patterns. An astonishing 179 have no solutions.

That's an interesting result - and perhaps it has direct application to the original post.
I've kind of dropped the ball on this. "Real" work has gotten in the way.

 

[Vanadium 50]

It has some application, although in the clear light of day it's less exciting.

The 512th pattern is all 3's. There are nine of them, and there are only eight numbers congruent to 3, so that never makes it into the sample.

Many of the 179 have a diagonal with exactly five 3's. This is helpful, but there are not many rows that are all 3's: there is 3, 8,13, 18 and 23, plus their permutations. Also, many of the 179 have a diagonal with exactly four 3's. This is even less useful, because there are no such rows: if you have four 3's and a sum to 65, what must the fifth one be?

Where it gets more interesting is the remaining set. It appears (checking now) that there needs to be 5 or fewer 3's on the two diagonals. That will take a bigger bite out of the number of possibilities. I would want to prove it before using it. Otherwise it feels like cheating.

For kicks, I am running a similar check on the placement of zeros mod 5. (Which is related to the placement of 1's)

 

[Vanadium 50]

Well, that was a bust.

The X-patterns that lead to no solutions have 6 or more elements with the same remainder mod 5. There are a very very small number (like 2) of patterns with 4 or 5 common remainders, but the bulk is 6+. How many does this eliminate that aren't eliminated some other way? Zero.

 

[mfb]

It appears (checking now) that there needs to be 5 or fewer 3's on the two diagonals.

Kind of obvious with just 5 elements that have the same remainder mod 5?

 

[Vanadium 50]

Kind of obvious with just 5 elements that have the same remainder mod 5?

In retrospect, yes.