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 !!
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.