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.
