Beefy Boxes and Bandwidth Generously Provided by pair Networks
No such thing as a small change
 
PerlMonks  

Re^5: magic squares

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


in reply to Re^4: magic squares
in thread magic squares

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:

#! /usr/bin/perl -wl use strict; use warnings; my @names = qw(JOHN MARTY PAUL SHEILA SMACK SUZY ELSA); for my $name (@names) { my @d = map {ord($_) - ord("A") + 1} split //, $name; my @solution = find_square(@d); if (@solution) { printf "%s:\n %2d %2d %2d\n %2d %2d %2d\n %2d %2d %2d\n", $name, @solution; printf "\n %s %s %s\n %s %s %s\n %s %s %s\n\n", map chr($_+ord("A")-1), @solution; } else { print "$name: no solution\n"; } } # All solutions look like: # # x+y x-z x-y+z # x-2y+z x x+2y-z # x+y-z x+z x-y # # Up to rotation and reflection we may insist that: # # 0 < z < y # z != y-z # # If 2z < y they are, in order: # # x-2y+z, x-y, x-y+z, x-z, x, x+z, x+y-z, x+y, x+2y-z # # Otherwise if y < 2z they are: # # x-2y+z, x-y, x-z, x-y+z, x, x+y-z, x+z x+y, x+2y-z # # This falls in the range 1..26 if 0 < x-2y+z and x+2y-z < 27. # # So 4y-2z < 25 with z < y means y < 13. sub find_square { my @d = sort {$a <=> $b} @_; my $min_range = $d[-1] - $d[0]; # As shown above, y < 13, but the lower limit is more complicated. # So work down from there. my $y = 13; Y: while (1) { $y--; last Y if 4*$y-2 < $min_range; # y < z is trivial, but the lower limit is complicated. # Again we were down from the top. my $z = $y; Z: while (1) { $z--; next Y if 4*$y-2*$z > 25; next Y if $z < 1; my @in_order; if ($z+$z > $y) { @in_order = ( -2*$y + $z, -$y, -$z, -$y + $z, 0, $y - $z, $z, $y, 2*$y - $z, ); } elsif ($z+$z < $y) { @in_order = ( -2*$y + $z, -$y, -$y + $z, -$z, 0, $z, $y - $z, $y, 2*$y - $z, ); } else { next; } # Sanity check for our logic. Can be removed. for (1..$#in_order) { if ($in_order[$_-1] >= $in_order[$_]) { print "y: $y, z:$z\n"; die "Out of order: @in_order"; } } # i is the index $d[0] matches at, which tells us $x. I: for my $i (0..$#in_order) { my $x = $d[0] - $in_order[$i]; # Sanity check our number range. # If we're out of range and increasing $i will not help, # then move to a different ($x, $z), otherwise only # increment $i. next Z if $x + $in_order[0] < 1; next I if $x + $in_order[-1] > 26; next Z if $x + $in_order[-1] < $d[-1]; # We match the lowest number, can we find the rest? # We search with "zipping" logic. my $p_d = my $p_o = 1; while ($p_d < @d) { if ($x + $in_order[$p_o] < $d[$p_d]) { # Perhaps the next number will match our digit? $p_o++; } elsif ($x + $in_order[$p_o] > $d[$p_d]) { # $d[$p_d] is not anywhere in our square. next I; } else { # One more digit matched. $p_o++; $p_d++; } } # If we got here we have a solution! Return it in the # right order for a square. return ( $x + $y, $x - $z, $x - $y + $z, $x - 2*$y + $z, $x, $x + 2*$y - $z, $x + $y - $z, $x + $z, $x - $y, ); } } } return; }

Update: In private conversation and in the response above Limbic~Region expressed some doubt about my assertions, so I'll provide proof.

First of all suppose that we have a magic square with sum S:

x11 x12 x13 x21 x22 x23 x31 x32 x33
Then the following is true:
S = 4*S - 3*S = (x21 + x22 + x23) +(x11 + x22 + x33) +(x12 + x22 + x32) +(x13 + x22 + x31) -(x11 + x12 + x13) -(x21 + x22 + x23) -(x31 + x32 + x33) = 3*x22
Without loss of generality we can pick x, y, and z such that x = x22, x11 = x+y and x12 = x-z. (The - makes things work out more nicely later.) Now let's start solving:
From choice of x, y, and z we have: x11 = x + y x12 = x - z x22 = x We already showed that the sum of every column, row and diagonal is 3x Finish the top row: 3x = S = x11 + x12 + x13 = (x + y) + (x - z) + x13 = 2x + y - z + x13 So x13 = x - y + z Now let's do the bottom row: 3x = S = x13 + x22 + x31 = (x - y + z) + (x) + x31 So x31 = x + y - z 3x = S = x12 + x22 + x32 = (x - z) + (x) + x32 = 2x - z + x32 So x32 = x + z 3x = S = x11 + x22 + x33 = (x + y) + (x) + x33 = 2x + y So x33 = x - y Now do the 2 sides 3x = S = x11 + x21 + x31 = (x + y) + x21 + (x + y - z) = 2x + 2y - z + x21 So x21 = x - 2y + z 3x = S = x13 + x23 + x33 = (x - y + z) + x23 + (x - y) = 2x - 2y + z + x23 So x23 = x + 2y - z
To be sure we made no errors, we need to double-check that all 8 equations for a magic square are satisfied:
x11 + x12 + x13 = (x + y) + (x - z) + (x - y + z) = 3x x21 + x22 + x23 = (x - 2y + z) + (x) + (x + 2y - z) = 3x x31 + x32 + x33 = (x + y - z) + (x + z) + (x - y) = 3x x11 + x21 + x31 = (x + y) + (x - 2y + z) + (x + y - z) = 3x x12 + x22 + x32 = (x - z) + (x) + (x - z) = 3x x13 + x23 + x33 = (x - y + z) + (x + 2y - z) + (x - y) = 3x x11 + x22 + x33 = (x + y) + (x) + (x - y) = 3x x13 + x22 + x31 = (x - y + z) + (x) + (x + y - z) = 3x
OK, good. So we know that we can get all magic squares in this form. (We also get some which are not magic squares because they have duplicates.) Now let's start with an arbitrary magic square whose numbers include the letters of a name. If we take that magic square and rotate or flip it, the magic square is still a magic square. So that magic square exists if and only if there is another magic square with x11 being the largest corner (can make this true by rotating), and with x12 larger than x21 (can make this true by flipping over the diagonal). When we insist on putting squares in this canonical form we no longer represent all magic squares, if there are any, there will be one in this form. (In fact in this form we have exactly 1/8 of the squares.)

Now what does that restriction do to x, y, and z?

It says nothing about x because x is a common term everywhere.

The rule that x11 > x33 says that y > 0.

The rule that x11 > x31 says that x + y > x + y - z. Add (z - x - y) to both sides and you see that z > 0.

The rule that x12 > x21 says that x - z > x - 2y + z. Add 2y - z + z) to both sides and you find that 2y > 2z, so y > z.

Hence the rule that this canonical form of a magic square happens when 0 < z < y.

Now for the bit about the exact order of the terms. You can verify that by hand. I could verify it as well, but I'm getting tired of typing it all in, and I'll just note that my code left in a test to verify that the terms actually appear in the order that I say they do. That test passed in every case, so the logic was, in fact, right. :-)

Since I know the exact order of the terms, I know that there is no duplication, and those choices of parameters really do lead to a real magic square.


Comment on Re^5: magic squares
Select or Download Code
Re^6: magic squares
by Limbic~Region (Chancellor) on Apr 08, 2009 at 23:50 UTC
    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://756379]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others imbibing at the Monastery: (10)
As of 2014-08-21 14:12 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    The best computer themed movie is:











    Results (136 votes), past polls