in reply to Re: magic squares
in thread magic squares

blokhead,
Actually, I don't think brute forcing to the extent you are describing is necessary. Is there any way you can confirm or deny my hunch that says any 3x3 magic square will have a center value of the magic constant divided by 3? If that assumption holds, I can think of a much smarter way of approaching this.

Update: In the CB, tye has shown that this assumption is true. I believe these squares can be constructed rather than validating random permutations. If I get a chance, I will provide a solution tonight. He also pointed out that you can't have the max nor the min values in one of the corners.

Cheers - L~R

Replies are listed 'Best First'.
Re^3: magic squares
by tilly (Archbishop) on Apr 08, 2009 at 06:00 UTC
    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

    [download]
    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.

[reply]
[d/l]
[select]
      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

      [download]

      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

      [download]
      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

[reply]
[d/l]
[select]
        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:
        Read more... (9 kB)
[reply]
[d/l]
[select]

In Section Seekers of Perl Wisdom