$3 \times 3 $ Magic Square of Squares Below is $3 \times 3$ magic square in which seven of the entries are squared integers, found by Andrew Bremner of Arizona State University (and independently by Lee Sallows of the University of Nijmegen):
$$
\boxed{
\begin{array} {ccc}
373^2 & 289^2 & 565^2 \\
360721 & 425^2 & 23^2 \\
205^2 & 527^2& 222121
\end{array}}$$
What would be an efficient algorithm for finding a new example of a three-by-three magic square with seven squared entries that differs from the one already known ?
I know that general formula$^{(1)}$ for $e_{ij}$ entry of an odd magic square of size $n \times n$ is given by :
$$e_{ij}= n\cdot\left(\left(i+j-1+\left \lfloor \frac{n}{2} \right \rfloor \right) \bmod n \right)+\left((i+2j-2\right) \bmod n)+1$$
P.S. : Rotations, symmetries, and multiples of this known square don't count as new solutions.
EDIT
I have found this one with six squared entries :
$$
\boxed{\begin{array} {ccc}
17^2 & 35^2 & 19^2 \\
697 & 25^2 & 553 \\
889 & 5^2 & 31^2 \end{array}}$$

Remarks:
$\;^{(1)}$ this formula gives only one (and special) solution for each size and thus doesn't help for finding various different solutions for a given size (say $3 \times 3$)
 A: You will want to look at A search for $3\times3$ magic squares having more than six
square integers among their nine distinct integers, by Christian Boyer, and at the papers by Bremner and others that Boyer references. You can't hope to find a new one until you understand the methods used to find the one that's already known. 
Boyer also published a paper which I haven't seen: 
Some notes on the magic squares of squares problem, 
Math. Intelligencer 27 (2005), no. 2, 52–64, MR2156534 (2006d:05024). 
A: This isn't a solution. But it's too big to be a comment. I just hope it's useful.
First observation
You can always arrange the numbers in a magic square so that the smallest is top-middle and the next is bottom-right, then there are two possible arrays of ranks of the $9$ numbers.
 TYPE 1        TYPE 0
 8  1  6       8  1  7
 3  5  7  and  4  5  6
 4  9  2       3  9  2

The first is itself a magic square, the second is not. The nicest example of a TYPE $0$ magic square is
 8   0  7
 4   5  6
 3  10  2

Second Observation
For all magic squares, the sum of the squares of the first row (column) equals the sum of the squares of the last row (column). For example
 8² + 0² + 7² = 3² + 10² + 2² = 113

So you are not only looking for numbers such that 
$$a+b+c=A+B+C$$
and 
$$a^2 + b^2 + c^2 = A^2 + B^2 + C^2$$
you must also have  
$$a^4 + b^4 + c^4 = A^4 + B^4 + C^4$$
Even further, $\{a,b,c\}$ and $\{A,B,C\}$ must both be complete residue systems modulo $3$.
