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$)
Best Answer
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).