4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – D.W. Jun 27 '17 at 20:24
  • $\begingroup$ A practical answer would be nice, that runs in less than O(n!). $\endgroup$ – Ethan Ward Jun 28 '17 at 1:25
  • $\begingroup$ 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. $\endgroup$ – gnasher729 Jun 28 '17 at 22:13
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.