Keep It Simple, Stupid PerlMonks

### Re^3: magic squares

by tilly (Archbishop)
 on Apr 08, 2009 at 06:00 UTC ( #756235=note: print w/replies, xml ) Need Help??

in reply to Re^2: magic squares

It may help you quite a bit to realize that some linear algebra shows that all solutions are of the form:
```  x+y    x-z  x-y+z
x-2y+z   x  x+2y-z
x+y-z   x+z  x-y
By rotating and reflecting we can make the largest corner be x+y, and we can insist that x-z > x-2y+z. In this case we have 0 < z < y The condition that all values be in the range 1..26 is satisfied if 1 <= x-2y+z < x+2y-z <= 26. Uniqueness is satisfied if 2z != y.

We can actually make a stronger statement. If 2z < y, then the elements fall in the order x-2y+z, x-y, x-y+z, x-z, x, x+z, x+y-z, x+y, x+2y-z and if y < 2z then the elements fall in the order x-2y+z, x-y, x-z, x-y+z, x, x+y-z, x+z x+y, x+2y-z.

With this many conditions, it should not be hard to enumerate the magic squares up to symmetry. And with some cleverness, I believe you don't even have to enumerate them all.

Replies are listed 'Best First'.
Re^4: magic squares
by Limbic~Region (Chancellor) on Apr 08, 2009 at 15:28 UTC
tilly,
Yes, this is exactly what I was guessing at. There are also constraints as to what x, y and z can be within the confines of this puzzle. I didn't have a chance last night to work on this though because the following entered my mind as I was leaving work
```X+Y      X+Z     X-Y-Z
X-2Y-Z   X       X+2Y+Z
X+Y+Z    X-Z     X-Y

Terms: X, X+Y, X-Y, X+Z, X-Z, X+Y+Z, X-Y-Z, X-2Y-Z, X+2Y+Z

X+Y      X-2Y+Z  X+Y-Z
X-Z      X       X+Z
X-Y+Z    X+2Y-Z  X-Y

Terms: X, X+Y, X-Y, X+Z, X-Z, X+Y-Z, X-Y+Z, X+2Y-Z, X-2Y+Z

Terms in common: X, X+Y, X-Y, X+Z, X-Z

Terms not in common: X+Y+Z  VS X+Y-Z  AND X-Y-Z  VS X-Y+Z
X-2Y-Z VS X-2Y+Z AND X+2Y+Z VS X+2Y-Z

I haven't convinced myself that you don't need to iterate over other series of equations. Still thinking on it though.

Update: In fact, I think I can show that your statement "By rotating and reflecting we can make the largest corner be x+y" is not in fact true - consider the following square:

```X+Y   X-Y-Z  X+Z
X-Y+Z X      X+Y-Z
X-Z   X+Y+Z  X-Y
You have X+Y and X+Z both in a corner so you need to make a relationship between them to determine which is the largest value. Also, I noticed that I showed it is possible to have X+Y+Z in a corner and am now convinced that multiple series of equations must be iterated (though you can re-use the values for X, Y and Z).

Cheers - L~R

It is ugly, but I used the above logic to code up a reasonably efficient solution. On my machine it runs in about 0.01s:
tilly,
Thanks! After having read your code and your proof I see why it wasn't immediately obvious to me. I was stuck looking at it a different way. I stubbornly had to convince myself that my way was in fact correct. After I did, I realized we were saying the same thing. This is the frustrating part - I sometimes can't get out of my own way.

Unfortunately, I now lack all ambition to implement my solution.

I only got interested in the problem because glancing at the commentary of existing posts - a number thought brute forcing was necessary. I had a hunch that this wasn't true.

Cheers - L~R

Create A New User
Node Status?
node history
Node Type: note [id://756235]
help
Chatterbox?
 [Corion]: I hope all is well marto! ;) My godson had a surprise visit to the hospital yesterday because he fell and had cut his skin besides his eye, but everything was glued together again and all is well [marto]: good grief, that's not fun, glad to hear all is as well as could be :) [Corion]: marto: Yeah - their mother picked all three of them up at the kindergarden to then go to the hospital, and all three of them were well behaved, and all also were quite obedient when they came home, so they recognized the situation

How do I use this? | Other CB clients
Other Users?
As of 2016-12-08 09:23 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
On a regular basis, I'm most likely to spy upon:

Results (137 votes). Check out past polls.
{"found_math": false, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0}