A magic square of order $n$ is an $n \times n$ grid containing each of the numbers $1,2,\dots,n^2$, so that the numbers in each row, column, and diagonal sum to the same number $n(n^2+1)/2$.
This question follows on from Is half-filled magic square problem NP-complete? about completing a partially filled magic square.
For $n=3$ the middle square must be $5$, so if the middle square is set to another value then there is no way to complete the magic square. On the other hand, if $n=4$ and a single number is specified (anywhere in the grid), then there is always a way to complete the magic square. This can be checked by inspection of the list of order-4 magic squares, from the site of Harvey Heinz.
Let $f(n)$ be the smallest number of values that when placed in an $n\times n$ grid, results in an pattern that cannot be completed to form a magic square. By the previous two examples, $f(3) = 1$ and $f(4) \ge 2$. The value $f(n)$ can also be thought of as the least number of values required in a partial $n \times n$ magic square for the decision problem to be interesting.
This motivates the question:
What is the asymptotic behaviour of $f(n)$ as $n$ tends to infinity?
I would be especially interested in knowing whether $f(n) = O(\log n)$, or if $f(n) = \Omega(n)$ (using big-O notation).
Consider the $k$ smallest numbers specified together with the $n-k$ largest numbers in the same row. This will fail to reach $n^2(n-1)/2$ when $k \gt n/2$. It then follows that $1 \le f(n) \le \lceil (n+1)/2 \rceil$. Are there sharper upper and lower bounds on $f(n)$, perhaps by distinguishing the case of $n$ even from $n$ odd?