<p>Filling a partially-filled Latin square is NP-Complete. "The complexity of completing partial Latin squares" Charles J. Colbourn. Discrete Applied Mathematics, Volume 8, Issue 1, April 1984, Pages 25-30 <a href="http://dx.doi.org/10.1016/0166-218X(84)90075-1">http://dx.doi.org/10.1016/0166-218X(84)90075-1</a></p>

<p>Can a Latin square problem be turned into a magic square problem via modular arithmetic? My intuition says yes, but the rest of my brain says "Get back to grading!"</p>

CC BY-SA 2.5
2011-03-19T22:31:10.503Z
It would be nice to turn this into a rigorous argument.  It is not at all clear to me how modular arithmetic would really help in reducing LATIN SQUARE COMPLETION to MAGIC SQUARE COMPLETION, or vice versa.  It would be rather pretty if it could be made to work.
András Salamon
CC BY-SA 2.5
2010-12-21T16:13:38.207Z
2010-12-21T16:13:38.207Z
Peter Boothe
<p>This question has two parts: first, is the problem in NP, and second, is it NP-hard?</p>

<p>For the first part, I have a positive answer with a non-obvious proof.  (Thanks to Suresh for pointing out an earlier error.)</p>

<hr>

<p>Consider the following way to formalize the question as a decision problem:</p>

<blockquote>
  <p><strong>UNRESTRICTED MAGIC SQUARE COMPLETION</strong><br>
  <em>Input:</em> positive integer $n$ given in unary, list of integers with their positions in an $n$ by $n$ grid<br>
  <em>Question:</em> do there exist integers for the remaining positions in the grid, so that the arrangement forms a <a href="http://en.wikipedia.org/wiki/Magic_square" rel="nofollow">magic square</a>?</p>
</blockquote>

<p>If we add the restriction that each of the integers $1,2,\dots,n^2$ must occur precisely once in the magic square, then the resulting MAGIC SQUARE COMPLETION decision problem is obviously in NP.  The <a href="http://en.wikisource.org/wiki/1911_Encyclop%C3%A6dia_Britannica/Magic_Square" rel="nofollow">definition of a magic square in the 1911 Encyclopædia Britannica</a>, following <a href="http://arxiv.org/pdf/math/0408230" rel="nofollow">Euler</a>, has this restriction; in contrast, the Wikipedia article currently uses the terminology "normal magic square" and reserves "magic square" for the unrestricted version.</p>

<p>With an $n$ by $n$ grid, at least $n$ numbers must be given, otherwise the answer is trivially "YES" for the unrestricted version.  The size of the input can therefore be assumed to require more than $n$ bits in this case.  For the normal version, it is possible that there are inputs that require few bits but which have no solution; to avoid such complications I have specified that $n$ is given in unary.</p>

<p>The argument uses a bound on the possible size of integers that appear in solutions.  In the normal case this bound is obviously $n^2$, but in the general case it is not <em>a priori</em> obvious that such a bound exists.  It turns out that an exponential bound exists.</p>

<blockquote>
  <p><em>Theorem (<a href="http://arxiv.org/abs/math/0702558" rel="nofollow">Tyszka, Theorem 12</a>):</em> Any system of Diophantine equations involving equations of the form $x_i = 1$ and $x_i = x_j + x_k$, for $i,j,k \in \{1,2,\dots,n\}$, either has no integer solution, or has a solution in which every $x_i$ is an integer and at most $\sqrt{5}^{n-1}$ in absolute value.</p>
</blockquote>

<p>This also appeared as Theorem 4.7 in:</p>

<ul>
<li>Apoloniusz Tyszka, <a href="http://onlinelibrary.wiley.com/doi/10.1002/malq.200910004/abstract" rel="nofollow"><em>Two conjectures on the arithmetic in R and C</em></a>, Math. Log. Quart. <strong>56</strong> 175–184, 2010.</li>
</ul>

<p>Cipu recently announced an asymptotically better bound of $2^n$.  (Note that the smallest possible bound is $2^{n-1}$.)  The argument builds on a bound on the determinant of a matrix, due to Waldi.</p>

<blockquote>
  <p><em>Theorem (Cipu, 2011):</em> Any system of Diophantine equations involving equations of the form $x_i = 1$ and $x_i = x_j + x_k$, for $i,j,k \in \{1,2,\dots,n\}$, either has no integer solution, or has a solution in which every $x_i$ is an integer and at most $2^n$ in absolute value.</p>
</blockquote>

<p>Even more recently, <a href="http://arxiv.org/abs/1108.4078v1" rel="nofollow">Freitas, Friedland and Porta</a> showed that the $2^{n-1}$ bound holds, as a corollary of their more general Theorem 1.1.</p>

<p>This yields the following:</p>

<blockquote>
  <p><em>Corollary:</em> If an instance of UNRESTRICTED MAGIC SQUARE COMPLETION of size $N$ has a solution, then it has a solution using only numbers up to $2^{O(N^2)}$.</p>
</blockquote>

<p>This means that one can use $O(N^4)$ space to guess a solution up to the bound, and then check in $O(N^8)$ time whether it is a solution.  The precise polynomial depends on whether one uses Tyszka's or Cipu's result for the bound, and how one expresses the Diophantine system of equations representing the magic square.  In either case, the number of variables required in a Diophantine system of the form posed by Tyszka is no more than $n^2 + 2(n+1)(n-2)+1 = 3n^2-2n-3$.  This is achieved with $n-2$ variables for partial sums for each row, column, and diagonal and a grand total variable linking these together.  Beyond the magic square itself, a further polynomial number of variables is required for the numbers in the square: a number requiring $m$ bits can be represented by using $O(m^2)$ intermediate variables.</p>

<p>For the second part of the question, as far as I can tell either version of MAGIC SQUARE COMPLETION should be NP-hard, but I do not have reductions.  It is worth noting that there are procedures to construct normal magic squares of arbitrarily large size; moreover, the number of normal magic squares seems to grow superpolynomially with $n$ (see <a href="http://oeis.org/A006052" rel="nofollow">OEIS A006052</a>) so the underlying language does not seem to be sparse.</p>

<hr>

<p>Using Papadimitriou's bound on the solutions of an instance of INTEGER LINEAR PROGRAMMING, one can also show that the version where the numbers must all be non-negative is also in NP.</p>

<blockquote>
  <p><em>Theorem (Papadimitriou):</em> Let $A$ be an $r \times s$ matrix and $b$ an $r$-vector, both with entries from $\{-a, -a+1, \dots, a-1, a\}$.  Then if $Ax = b$ has a solution in non-negative integers, it also has one where every component is in $\{0,1,\dots,s(ra)^{2r+1}\}$.</p>
</blockquote>

<p>The constraints forming the magic square can be expressed as a linear program using $a=1$, with $s=n^2+1$ variables and $r=2n+2$ inequalities.  This yields a somewhat larger bound than the bound above where negative numbers are allowed, but the certificate is still of polynomial size.  (Thanks to Tony Tan for pointing out the result of Papadimitriou.)</p>

<ul>
<li>Christos H. Papadimitriou, <em>On the complexity of integer programming</em>, JACM <strong>28</strong> 765–768, 1981. (<a href="http://dx.doi.org/10.1145/322276.322287" rel="nofollow">link</a>)</li>
</ul>

CC BY-SA 2.5
2011-03-19T18:06:49.650Z
I guess I'm confused. if there's a poly bound on the size of the answers, then we are guaranteed to have a guess that can be read and verified in polynomial time.
Suresh Venkat
CC BY-SA 2.5
2011-03-19T18:12:17.857Z
@Suresh: Apologies for the errors, this answer turned out a bit harder to write down than I expected.
András Salamon
CC BY-SA 3.0
2011-03-19T16:53:03.183Z
2011-09-15T12:40:42.483Z
2011-09-15T12:40:42.483Z
András Salamon
<p>Here is the problem:</p>

<p>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.</p>

<p>Examples:</p>

<pre><code>2 _ 6       2 7 6
_ 5 1  &gt;&gt;&gt;  9 5 1
4 3 _       4 3 8

7 _ _ 
9 _ _  &gt;&gt;&gt;  NO SOLUTION 
8 _ _
</code></pre>

<p>Is this problem NP-complete? If yes, how can I prove it?</p>

<p><em><a href="https://math.stackexchange.com/q/15042/4003">Crosspost on MS</a></em></p>

CC BY-SA 2.5
2011-03-22T16:48:47.287Z
@Tsuyoshi: I've set open problems as homework before. In particular, asked for the number of mutually unbiased bases in 2 (easy problem) and 6 (open problem) complex dimensions as part of a linear algebra course.
Joe Fitzsimons
CC BY-SA 2.5
2011-03-22T17:33:42.640Z
@Joe: I see.  I guess that that means that homework problems are not necessarily homework-level.  :)
Tsuyoshi Ito
CC BY-SA 2.5
2010-12-21T09:00:07.757Z
[Crosspost](http://math.stackexchange.com/questions/15042/is-half-filled-magic-square-problem-np-complete) from Math SE.
Hsien-Chih Chang 張顯之
CC BY-SA 2.5
2010-12-21T09:03:42.327Z
@levanovd: This site is for research level problems in theoretical computer science, and your question may not be appropriate here. See the [FAQ](http://meta.cstheory.stackexchange.com/questions/225/official-faq-for-theoretical-computer-science/235#235) for more information. Maybe it is better to wait for answers from Math SE, since you have just post a question there within an hour.
Hsien-Chih Chang 張顯之
CC BY-SA 2.5
2010-12-21T09:03:57.660Z
Yes, I like your observation. This is another community so I thought that somebody here may help. Is it bad?
levanovd
CC BY-SA 2.5
2010-12-21T09:06:19.703Z
No, asking for help is not a bad thing. But your question has to be in the scope of the site you asked. I think Math SE is proper for this question, and TCS SE is not.
Hsien-Chih Chang 張顯之
CC BY-SA 2.5
2010-12-21T09:06:32.980Z
If I tagged this question 'homework' at Math SE it doesn't mean that it is school-level question. It means that I faced it during my study.
levanovd
CC BY-SA 2.5
2010-12-21T09:08:21.233Z
@Hsien-Chih Chang: ok, if anyone will vote for closing this question, I'll delete it asap.
levanovd
CC BY-SA 2.5
2010-12-21T09:10:41.753Z
@lecanovd: Maybe there is no need to delete the question. But anyway, thank you for your help, and I do hope you will solve the problem soon!!
Hsien-Chih Chang 張顯之
CC BY-SA 2.5
2010-12-21T10:12:31.080Z
We do accept questions about proving NP-hardness especially when the problem is hard. For example, consider the three examples listed as answers here: http://meta.cstheory.stackexchange.com/questions/784/original-proofs-generated-on-the-parent-site
Suresh Venkat
CC BY-SA 2.5
2010-12-21T10:47:05.003Z
Yes, and after thinking for a little while, I find this problem non-trivial. I suggest to keep the question open, unless an easy solution to this problem is known.
Hsien-Chih Chang 張顯之
CC BY-SA 2.5
2010-12-21T11:29:54.890Z
Here is a [related discussion](http://meta.cstheory.stackexchange.com/q/849/1800) on meta about the level of NP-hardness proofs.
Hsien-Chih Chang 張顯之
CC BY-SA 2.5
2010-12-21T13:09:24.843Z
(1) I like the problem, but I do not like secret crossposting or simultaneous crossposting.  So when you crosspost next time, please include links, preferably in both directions.  (2) You tagged your question on Math SE as “homework.”  Is it really homework?  If so, I do not think that it is appropriate for TCS SE.  (But I hope that it is not homework, because I cannot see how to solve it.)
Tsuyoshi Ito
CC BY-SA 2.5
2010-12-21T15:34:19.853Z
@Tsuyoshi Ito: Added link to related MS question. In fact this is homework but it is a kind of my professor's joke
levanovd
CC BY-SA 2.5
2010-12-21T15:57:52.657Z
If it is homework, then isn't it unethical for someone to provide a solution here?
Robin Kothari
CC BY-SA 2.5
2010-12-21T20:08:16.987Z
If it's homework, we don't allow it, whether or not it's unethical.
Peter Shor 
CC BY-SA 2.5
2010-12-21T20:25:03.023Z
@Peter Shor: It's quite strange since homework questions are welcome on stackoverflow (http://stackoverflow.com/questions/tagged/homework) Also I don't think that there is any difference if the question is related to homework or not, I always help everybody if only I know the right answer regardless to question tags.
levanovd
CC BY-SA 2.5
2010-12-21T20:26:45.190Z
Also this question is not homework now but question of interest.
levanovd
CC BY-SA 2.5
2010-12-21T20:40:17.860Z
@levanovd: This is not stackoverflow.  This community has an explicit policy forbidding homework questions.  The fact that stackoverflow has a different policy doesn't matter here.
Jeffε
CC BY-SA 2.5
2010-12-22T09:58:16.030Z
so I'm confused now. This is a nice question, but if it's homework it should die a bright flaming death..
Suresh Venkat
CC BY-SA 2.5
2010-12-22T13:04:28.793Z
@Suresh: @levanovd claimed that this is not a homework now. We should trust him, like we trust every users on this site. If later on it is founded that this is indeed a homework, we can close the question right away. But right now I would prefer to view it as a nice brain-twisting question.
Hsien-Chih Chang 張顯之
CC BY-SA 2.5
2010-12-22T13:28:52.200Z
Moreover, in [Math SE](http://math.stackexchange.com/q/15042/2767) the OP seems only asking for directions, and I think the answer by @pboothe works well, this definitely gives a new path of thinking. If the OP is really interested in the question, I think he/she should be able to solve the problem by the hint, or get stuck and revise the problem with new observations and questions.
Hsien-Chih Chang 張顯之
CC BY-SA 2.5
2010-12-22T13:35:06.300Z
In summary, my opinion is that we just leave the question as where it is, and @levanovd if you are still facing some difficulties after reading and trying the suggestions given by @pboothe, you can edit your question and provide your new thoughts about this interesting puzzle. Anyone?
Hsien-Chih Chang 張顯之
CC BY-SA 2.5
2010-12-22T18:08:11.210Z
@Hsien-Chih: The asker once said “In fact this is homework” in a comment, and he changed his claim without explanation after people pointed out that homework questions are not allowed here.  I am totally confused.
Tsuyoshi Ito
CC BY-SA 2.5
2010-12-22T23:22:03.617Z
@Tsuyoshi Ito: If you want to quote please quote the whole sentence: "In fact this is homework but it is a kind of my professor's joke". I've got this problem from my professor but I'm not sure if he even knows the solution. You can argue for a long time about if it is a homework, what is homework, etc. If you want to hear this, I will not be given any mark or get other bonuses for solving this problem. It is scientific interest only.
levanovd
CC BY-SA 2.5
2010-12-22T23:47:09.320Z
So do you mean that you once incorrectly stated that this question was homework while it was not?  Please understand that you contradicted yourself and that contradiction was confusing.
Tsuyoshi Ito
CC BY-SA 2.5
2010-12-23T07:16:36.600Z
@Hsien-Chih Chang: I think there is difference between trusting and over-trusting, e.g. you can trust the students in your class but that does not mean that you should leave them alone during the final exam, we shouldn't mistrust new users but trust is built up by time.
Kaveh
CC BY-SA 2.5
2010-12-23T07:18:51.090Z
We accept NP-hardness questions but if a question is elementary/homework-level, it should be closed (independent of being homework or not), *with the exceptions mentioned in the related meta discussions*, and the way to make the decision about closing is by asking the user for motivation and here the motivation seems to be a problem asked by an instructor. So I think if this question is of elementary level it should be close as it does not fall under the exception for acceptable elementary questions.
Kaveh
CC BY-SA 2.5
2010-12-23T07:22:32.867Z
@Kaveh: I totally agree on your opinion, the hardest part is to decide whether a problem is at homework-level or not. (This has already been discussed on [meta](http://meta.cstheory.stackexchange.com/q/209/1800).) I am only a student who do not have the ability to decide whether this problem is at homework-level (though it seems to me like a non-trivial problem), and I will leave the judgement for this problem to the experts.
Hsien-Chih Chang 張顯之
CC BY-SA 2.5
2010-12-23T10:27:35.337Z
I do not know a solution and I do not think that this is at the level of homework.  However, I might be missing something simple.  Therefore if anyone knows a complete solution and thinks this question is homework-level, please just say so.  In the meanwhile, I will assume that this question is not homework and that the [homework] tag used on Math SE and levanovd’s earlier comment were simply mistakes.
Tsuyoshi Ito
<cc.complexity-theory><np-hardness><np><puzzles>
Is the half-filled magic square problem NP-complete?
levanovd
# Is the half-filled magic square problem NP-complete?

(Asked by: username_0 on 2010-12-21)

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?
Crosspost on MS

**Tags:** cc.complexity-theory, np-hardness, np, puzzles

> **Comments:**
> **username_3**: [Crosspost](http://math.stackexchange.com/questions/15042/is-half-filled-magic-square-problem-np-complete) from Math SE.  
> **username_3**: @username_0: This site is for research level problems in theoretical computer science, and your question may not be appropriate here. See the [FAQ](http://meta.cstheory.stackexchange.com/questions/225/official-faq-for-theoretical-computer-science/235#235) for more information. Maybe it is better to wait for answers from Math SE, since you have just post a question there within an hour.  
> **username_0**: Yes, I like your observation. This is another community so I thought that somebody here may help. Is it bad?  
> **username_3**: No, asking for help is not a bad thing. But your question has to be in the scope of the site you asked. I think Math SE is proper for this question, and TCS SE is not.  
> **username_0**: If I tagged this question 'homework' at Math SE it doesn't mean that it is school-level question. It means that I faced it during my study.  
> **username_0**: @Hsien-Chih Chang: ok, if anyone will vote for closing this question, I'll delete it asap.  
> **username_3**: @lecanovd: Maybe there is no need to delete the question. But anyway, thank you for your help, and I do hope you will solve the problem soon!!  
> **username_4**: We do accept questions about proving NP-hardness especially when the problem is hard. For example, consider the three examples listed as answers here: http://meta.cstheory.stackexchange.com/questions/784/original-proofs-generated-on-the-parent-site  
> **username_3**: Yes, and after thinking for a little while, I find this problem non-trivial. I suggest to keep the question open, unless an easy solution to this problem is known.  
> **username_3**: Here is a [related discussion](http://meta.cstheory.stackexchange.com/q/849/1800) on meta about the level of NP-hardness proofs.  
> **username_2**: (1) I like the problem, but I do not like secret crossposting or simultaneous crossposting.  So when you crosspost next time, please include links, preferably in both directions.  (2) You tagged your question on Math SE as “homework.”  Is it really homework?  If so, I do not think that it is appropriate for TCS SE.  (But I hope that it is not homework, because I cannot see how to solve it.)  
> **username_0**: @username_2: Added link to related MS question. In fact this is homework but it is a kind of my professor's joke  
> **username_5**: If it is homework, then isn't it unethical for someone to provide a solution here?  
> **username_6**: If it's homework, we don't allow it, whether or not it's unethical.  
> **username_0**: @Peter Shor: It's quite strange since homework questions are welcome on stackoverflow (http://stackoverflow.com/questions/tagged/homework) Also I don't think that there is any difference if the question is related to homework or not, I always help everybody if only I know the right answer regardless to question tags.  
> **username_0**: Also this question is not homework now but question of interest.  
> **username_7**: @username_0: This is not stackoverflow.  This community has an explicit policy forbidding homework questions.  The fact that stackoverflow has a different policy doesn't matter here.  
> **username_4**: so I'm confused now. This is a nice question, but if it's homework it should die a bright flaming death..  
> **username_3**: @Suresh: @username_0 claimed that this is not a homework now. We should trust him, like we trust every users on this site. If later on it is founded that this is indeed a homework, we can close the question right away. But right now I would prefer to view it as a nice brain-twisting question.  
> **username_3**: Moreover, in [Math SE](http://math.stackexchange.com/q/15042/2767) the OP seems only asking for directions, and I think the answer by @pboothe works well, this definitely gives a new path of thinking. If the OP is really interested in the question, I think he/she should be able to solve the problem by the hint, or get stuck and revise the problem with new observations and questions.  
> **username_3**: In summary, my opinion is that we just leave the question as where it is, and @username_0 if you are still facing some difficulties after reading and trying the suggestions given by @pboothe, you can edit your question and provide your new thoughts about this interesting puzzle. Anyone?  
> **username_2**: @Hsien-Chih: The asker once said “In fact this is homework” in a comment, and he changed his claim without explanation after people pointed out that homework questions are not allowed here.  I am totally confused.  
> **username_0**: @username_2: If you want to quote please quote the whole sentence: "In fact this is homework but it is a kind of my professor's joke". I've got this problem from my professor but I'm not sure if he even knows the solution. You can argue for a long time about if it is a homework, what is homework, etc. If you want to hear this, I will not be given any mark or get other bonuses for solving this problem. It is scientific interest only.  
> **username_2**: So do you mean that you once incorrectly stated that this question was homework while it was not?  Please understand that you contradicted yourself and that contradiction was confusing.  
> **username_8**: @Hsien-Chih Chang: I think there is difference between trusting and over-trusting, e.g. you can trust the students in your class but that does not mean that you should leave them alone during the final exam, we shouldn't mistrust new users but trust is built up by time.  
> **username_8**: We accept NP-hardness questions but if a question is elementary/homework-level, it should be closed (independent of being homework or not), *with the exceptions mentioned in the related meta discussions*, and the way to make the decision about closing is by asking the user for motivation and here the motivation seems to be a problem asked by an instructor. So I think if this question is of elementary level it should be close as it does not fall under the exception for acceptable elementary questions.  
> **username_3**: @username_8: I totally agree on your opinion, the hardest part is to decide whether a problem is at homework-level or not. (This has already been discussed on [meta](http://meta.cstheory.stackexchange.com/q/209/1800).) I am only a student who do not have the ability to decide whether this problem is at homework-level (though it seems to me like a non-trivial problem), and I will leave the judgement for this problem to the experts.  
> **username_2**: I do not know a solution and I do not think that this is at the level of homework.  However, I might be missing something simple.  Therefore if anyone knows a complete solution and thinks this question is homework-level, please just say so.  In the meanwhile, I will assume that this question is not homework and that the [homework] tag used on Math SE and username_0’s earlier comment were simply mistakes.  
> **username_1**: @Tsuyoshi: I've set open problems as homework before. In particular, asked for the number of mutually unbiased bases in 2 (easy problem) and 6 (open problem) complex dimensions as part of a linear algebra course.  
> **username_2**: @Joe: I see.  I guess that that means that homework problems are not necessarily homework-level.  :)  

---

## 2 answers

### Answer by username_9 on 2010-12-21. Score: 19

Filling a partially-filled Latin square is NP-Complete. "The complexity of completing partial Latin squares" Charles J. Colbourn. Discrete Applied Mathematics, Volume 8, Issue 1, April 1984, Pages 25-30 <http://dx.doi.org/10.1016/0166-218X(84)90075-1>

Can a Latin square problem be turned into a magic square problem via modular arithmetic? My intuition says yes, but the rest of my brain says "Get back to grading!"

> **Comments:**
> **username_10**: It would be nice to turn this into a rigorous argument.  It is not at all clear to me how modular arithmetic would really help in reducing LATIN SQUARE COMPLETION to MAGIC SQUARE COMPLETION, or vice versa.  It would be rather pretty if it could be made to work.  

---

### Answer by username_10 on 2011-03-19. Score: 9

This question has two parts: first, is the problem in NP, and second, is it NP-hard?

For the first part, I have a positive answer with a non-obvious proof. (Thanks to Suresh for pointing out an earlier error.)

---

Consider the following way to formalize the question as a decision problem:

> **UNRESTRICTED MAGIC SQUARE COMPLETION**  
> *Input:* positive integer $n$ given in unary, list of integers with their positions in an $n$ by $n$ grid  
> *Question:* do there exist integers for the remaining positions in the grid, so that the arrangement forms a [magic square](http://en.wikipedia.org/wiki/Magic_square)?

If we add the restriction that each of the integers $1,2,\dots,n^2$ must occur precisely once in the magic square, then the resulting MAGIC SQUARE COMPLETION decision problem is obviously in NP. The [definition of a magic square in the 1911 Encyclopædia Britannica](http://en.wikisource.org/wiki/1911_Encyclop%C3%A6dia_Britannica/Magic_Square), following [Euler](http://arxiv.org/pdf/math/0408230), has this restriction; in contrast, the Wikipedia article currently uses the terminology "normal magic square" and reserves "magic square" for the unrestricted version.

With an $n$ by $n$ grid, at least $n$ numbers must be given, otherwise the answer is trivially "YES" for the unrestricted version. The size of the input can therefore be assumed to require more than $n$ bits in this case. For the normal version, it is possible that there are inputs that require few bits but which have no solution; to avoid such complications I have specified that $n$ is given in unary.

The argument uses a bound on the possible size of integers that appear in solutions. In the normal case this bound is obviously $n^2$, but in the general case it is not *a priori* obvious that such a bound exists. It turns out that an exponential bound exists.

> *Theorem ([Tyszka, Theorem 12](http://arxiv.org/abs/math/0702558)):* Any system of Diophantine equations involving equations of the form $x\_i = 1$ and $x\_i = x\_j + x\_k$, for $i,j,k \in \{1,2,\dots,n\}$, either has no integer solution, or has a solution in which every $x\_i$ is an integer and at most $\sqrt{5}^{n-1}$ in absolute value.

This also appeared as Theorem 4.7 in:

* Apoloniusz Tyszka, [*Two conjectures on the arithmetic in R and C*](http://onlinelibrary.wiley.com/doi/10.1002/malq.200910004/abstract), Math. Log. Quart. **56** 175–184, 2010.

Cipu recently announced an asymptotically better bound of $2^n$. (Note that the smallest possible bound is $2^{n-1}$.) The argument builds on a bound on the determinant of a matrix, due to Waldi.

> *Theorem (Cipu, 2011):* Any system of Diophantine equations involving equations of the form $x\_i = 1$ and $x\_i = x\_j + x\_k$, for $i,j,k \in \{1,2,\dots,n\}$, either has no integer solution, or has a solution in which every $x\_i$ is an integer and at most $2^n$ in absolute value.

Even more recently, [Freitas, Friedland and Porta](http://arxiv.org/abs/1108.4078v1) showed that the $2^{n-1}$ bound holds, as a corollary of their more general Theorem 1.1.

This yields the following:

> *Corollary:* If an instance of UNRESTRICTED MAGIC SQUARE COMPLETION of size $N$ has a solution, then it has a solution using only numbers up to $2^{O(N^2)}$.

This means that one can use $O(N^4)$ space to guess a solution up to the bound, and then check in $O(N^8)$ time whether it is a solution. The precise polynomial depends on whether one uses Tyszka's or Cipu's result for the bound, and how one expresses the Diophantine system of equations representing the magic square. In either case, the number of variables required in a Diophantine system of the form posed by Tyszka is no more than $n^2 + 2(n+1)(n-2)+1 = 3n^2-2n-3$. This is achieved with $n-2$ variables for partial sums for each row, column, and diagonal and a grand total variable linking these together. Beyond the magic square itself, a further polynomial number of variables is required for the numbers in the square: a number requiring $m$ bits can be represented by using $O(m^2)$ intermediate variables.

For the second part of the question, as far as I can tell either version of MAGIC SQUARE COMPLETION should be NP-hard, but I do not have reductions. It is worth noting that there are procedures to construct normal magic squares of arbitrarily large size; moreover, the number of normal magic squares seems to grow superpolynomially with $n$ (see [OEIS A006052](http://oeis.org/A006052)) so the underlying language does not seem to be sparse.

---

Using Papadimitriou's bound on the solutions of an instance of INTEGER LINEAR PROGRAMMING, one can also show that the version where the numbers must all be non-negative is also in NP.

> *Theorem (Papadimitriou):* Let $A$ be an $r \times s$ matrix and $b$ an $r$-vector, both with entries from $\{-a, -a+1, \dots, a-1, a\}$. Then if $Ax = b$ has a solution in non-negative integers, it also has one where every component is in $\{0,1,\dots,s(ra)^{2r+1}\}$.

The constraints forming the magic square can be expressed as a linear program using $a=1$, with $s=n^2+1$ variables and $r=2n+2$ inequalities. This yields a somewhat larger bound than the bound above where negative numbers are allowed, but the certificate is still of polynomial size. (Thanks to Tony Tan for pointing out the result of Papadimitriou.)

* Christos H. Papadimitriou, *On the complexity of integer programming*, JACM **28** 765–768, 1981. ([link](http://dx.doi.org/10.1145/322276.322287))

> **Comments:**
> **username_4**: I guess I'm confused. if there's a poly bound on the size of the answers, then we are guaranteed to have a guess that can be read and verified in polynomial time.  
> **username_10**: @Suresh: Apologies for the errors, this answer turned out a bit harder to write down than I expected.  

---

