Here is the problem:
We have a square with some numbers from 1..N in some cells. It's needed to determine if it can be completed to a magic square.
Examples:
2 _ 6 2 7 6 _ 5 1 >>> 9 5 1 4 3 _ 4 3 8 7 _ _ 9 _ _ >>> NO SOLUTION 8 _ _
Is this problem NP-complete? If yes, how can I prove it?
P.S.:
I know that I should reduce one of the known NP-complete problems to this one to prove its NP-completeness. The main question is which NP-complete probleme to choose and how to buld polynomial reduction algorithm. Any ideas?