Magic Squares with Random Numbers I'm trying to solve a problem related to Magic Squares. The thing is:
Given a list of n numbers, I need to answer if it is possible to create a magic square with them. These numbers are random (no order at all) and may/can be repeated. For example:
-1 -11 -6 19 -21 4 14 29 9 (Which in fact works as a Magic Square 3x3)
I know I can calculate the size of the matrix by sqrt() the lenght of the array, but I cannot find any hint on the way I can solve this efficiently (No, I cannot afford trying every single combination as my matrix can be as big as 29x29)
Any help??
Thanks !!
 A: Preconditions:
$a_i$: the sequence of input numbers, $i \in \{1, 2, \dots, m\}$.
$n$: the number of row/columns. Obviously, $n=\sqrt{m}$. If there is no integer solution for $n$, then there is no magic square.
$s$: the sum of numbers in each row, column and diagonal.
$$s \cdot n=\sum{a_i}$$
$$s=\frac{\sum{a_i}}{n}$$
Like $n$, there has to be an integer solution for $s$, or there is no magic square.
Solution:
Except for the conditions above, I don't see any other way than trying out possible solutions. However, we do not have to try each and every permutation; we can do that a bit more systematically, e.g. by modelling the problem as a contraint satisfaction problem (CSP) with $n^2$ variables and $2n+2$ constraints (one per row/column/diagonal: $\sum=s)$
For $n=29$ it's still quite hard, though.
A: For 29x29 that is a lot of work.  I am here looking for similar info. Where I am at problem solving-wise is you can find all sums of n numbers adding to the magic sum (s above): order the list, test the sum of the smaller numbers until the sum is too large, get a list of possible rows, which is also a list of possible columns.  Search through the rows to find n that are disjoint (have all the numbers in them), then search through the columns (which are also the rows) to find columns that intersect each of your n rows just once.  I think you still have to test (n!)^2 possible row-column permutations then test the diagonal sums.
