http://www.perlmonks.org?node_id=755560


in reply to magic squares

The Siamese method you linked to seems to be only applicable for n x n squares made up of the numbers 1 through n2. In this problem you are asked about 3 x 3 magic squares made up of numbers 1 through 26. So there is much less structure and the Siamese method (even augmented as you have done) will likely not find all such squares.

Unless you happen to fall upon an ingenious simple mathematical simplification, there may be nothing much simpler than trying all possible arrangements of 9 numbers chosen between 1 and 26.

So I would start the other direction, so that there is less to search. Start with the person's name, say PAUL, and figure out which sets of 5 letters could be added to make a magic square. There are some simple constraints that limit the amount of search, for instance the sum of all the entries should be a multiple of 3. Then see if you can make a magic square out of it. It will be less work than searching the entire space.

blokhead

Replies are listed 'Best First'.
Re^2: magic squares
by sflitman (Hermit) on Apr 05, 2009 at 15:23 UTC
    That's what I thought. I wrote some code with Algorithm::Combinatorics and it took bloody forever so I knew it had to be wrong. I like the idea of constrained search, with all 9 entries summing to multiple of 3, but the problem is the arrangement of the PAUL letters can be anywhere in the grid, so I'm stuck searching permutations anyway.

    Thanks for your input!

    SSF

[reply]
Re^2: magic squares
by Limbic~Region (Chancellor) on Apr 07, 2009 at 19:19 UTC
    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

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

In Section Seekers of Perl Wisdom