Beefy Boxes and Bandwidth Generously Provided by pair Networks
No such thing as a small change
 
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
in thread 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.


Comment on Re^3: magic squares
Select or Download Code
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

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://756235]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others lurking in the Monastery: (12)
As of 2014-09-19 11:15 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    How do you remember the number of days in each month?











    Results (135 votes), past polls