Given an array of $n^2$ integers, what is the most efficient way to determine whether any permutation of those integers can form a magic square? Magic square being an arrangement of those integers on a square grid such that all rows, columns and diagonals sum to the same value.Note that this isn't asking how to test if a given arrangement is a magic square, which would be $O(n^2)$, but whether any possible square formed from the array is magic.
Deciding whether there exists a permutation of the entries of an $n \times n$ matrix that is magic
algorithms;algorithm analysis;matrices
One approach is to use integer linear programming, and hope that an ILP solver will be able to find a solution.  This will probably still be exponential in $n$ in the worst case, but it might be faster than enumerating all $n!$ solutions.Here's more detail.  Suppose we are given the integers $a_1,a_2,\dots,a_{n^2}$.  Let $M=(a_1+\dots+a_{n^2})/n$ be the magic constant of the magic square, so that every row, every column, and every diagonal needs to sum to $M$.  Define zero-or-one integer variables $x_{i,j,k}$, with the intended meaning that $x_{i,j,k}=1$ means that the number $a_k$ is placed in row $i$, column $j$.  Then we have the inequalities$$\begin{align*}&\sum_i a_k x_{i,j,k} = M\\&\sum_j a_k x_{i,j,k} = M\\&\sum_i a_k x_{i,i,k} = M\\&\sum_i a_k x_{i,n+1-i,k} = M\\&\sum_k x_{i,j,k} = 1\\&\sum_{i,j} x_{i,j,k} = 1.\end{align*}$$Then any feasible solution to these linear equalities will represent a valid magic square, so you can feed this to an off-the-shelf ILP solver and hope that it finds a solution for you.  Probably it will fail (take forever) once $n$ gets large, but it might be effective if $n$ is small enough.