# Deciding whether there exists a permutation of the entries of an $n \times n$ matrix that is magic

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.

• Are you looking for a practical answer, or are you asking about the worst-case asymptotic complexity? Are you more interested in the running time as a function of $n$ (treating the size of the integers as a constant), or the running time as a function of the size of the integers (treating $n$ as a constant), or do you really need to know the dependence on both parameters? Related (but doesn't answer your question): cstheory.stackexchange.com/q/3903/5038. – D.W. Jun 27 '17 at 20:24
• A practical answer would be nice, that runs in less than O(n!). – Ethan Ward Jun 28 '17 at 1:25
• Add or subtract a constant so the smallest integer is 0. Obviously the sum of the integers must be divisible by $n^2$, and 2x the largest integer plus the 2n-2 smallest must not be greater than 2x the sum divided by n. Maybe there are other criteria showing quickly there is no solution. – gnasher729 Jun 28 '17 at 22:13

## 1 Answer

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.