Is half-filled magic square problem NP-complete?

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?

• If this is homework, you might try listing the NP-complete problems you know and seeing if you can think of a reduction to one of these. Dec 21, 2010 at 8:27
• I thought about converting this problem to Hamiltonian circuit or TSP or Subset sum problems, but not too successfully. Dec 21, 2010 at 8:40
• @Qiaochu A minor addition: what you are saying would prove that the problem is in NP. To prove that it is NP-complete, you need to reduce an NP-complete problem to this one. Dec 21, 2010 at 8:43
• I'm familiar with Clique, Minimal Vertex cover, Knapsack problem, 3SAT and some others. However, conversion to any known NP-complete problem is welcome since if I even don't know such NP-complete problem, I can read about it. Dec 21, 2010 at 8:43
• Yes, that's a different story. For that you need a reduction from a known NP-complete problem to this one - so only one reduction. Dec 21, 2010 at 8:59

To avoid pathological cases, it is common to require that the input specifies the size of the $n \times n$ grid in unary. The input then has at least $n$ bits.
If the grid contains each number $1,2,\dots,n^2$ then a solution can be regarded as a permutation of these numbers, which requires at most $n^2\, \lceil \log\, n \rceil = O(n^3)$ bits to list. This is clearly then polynomial in the input size.