Square board game with overlapping square sub-parts

Question

Two players, A and B play a game on a board with $NxN$ squares. Player A populates all squares with numbers from 1 to $N^2$ in a completely random way. Here is an example for a 5x5 board:

Player B does not see the board but can ask player A to tell him the content of any square part of the board. Two such square parts (with red and green frame) are shown here:

Player A has to report numbers in the requested square part but he does not have to report them in any particular order. For example, for the red part of the board he could respond with: 23, 21, 12, 4, 14, 10, 5, 22, 25. And for the green part he could reply with: 15, 21, 11, 1.

How many questions player B has to ask before he is able to fully reconstruct the content of the board?

Obviously he can do it by asking for a content of every single 1x1 square of the board. So in the worst case he does not have to ask more than $N^2-1$ questions. But with a better strategy that number can be greatly reduced.

Answer 1

Let $f(N)$ be the number of queries used by an optimal strategy to solve the $N\times N$ board.

Claim. $f(N)\ge 2(N-1).$

Proof. Consider the $4(N-1)$ boundary lines between consecutive fields in the following list: $(1,1)$, $(2,1)$, $(3,1),\ldots, (N,1)$, $(N,2)$, $(N,3),\ldots, (N,N)$, $(N-1,N)$, $(N-2,N),\ldots, (1,N)$, $(1,N-1)\ldots,(1,2)$, $(1,1)$. These are the $4(N-1)$ "ends" of the $N-1$ vertical and $N-1$ horizontal lines in the grid that separates the board into fields. In order to distinguish fields separated by such an "end", there must be a query that separates these fields, i.e., that has this end as part of its boundary. A square shaped query of side-length $\le N-1$ can cover at most two of these ends. Hence we need at least $2(N-1)$ queries. $\square$

Combining this lower bounds with the strategies in bof's answer, which shows that $f(N)\le 2N-2$ for odd $N$ and $f(N)\le 2N-1$ for even $N$, we see that $$f(N)=2N-2\qquad \text{if $N$ is odd.}$$

$$2N-2\le f(N)\le 2N-1\qquad \text{if $N$ is even.}$$

Is suspect that in this case the higher value is correct; after all, my argument for the lower bound makes possibly not enough use of the fact that at least three of the four corner fields must be covered by some query. In other words, I dare to

Conjecture. $f(N)=2N-1-(N\bmod 2)$.

Some observations in support of this conjecture: If $N$ is even, then edge edge of the board has $N-1$ "ends", an odd number. If there is a solution with $2N-2$ queries, each end is covered exactly once. A query that covers a corner field takes one end from the adjacent board edges, whereas a query without a corner field may take two ends from one edge, but does not change parities. We conclude that for each board edge, one of the adjacent corner fields is covered by an odd number of queries and the other by an even number of queries. This makes two oddly and two evenly covered corner fields. If both evenly covered corner fields are not covered at all, we cannot distinguish them. Therefore one corner field must be covered by at least two queries. My intuition says that this is wasteful, thereby supporting the conjecture.

Answer 2

For $N=2k+1$ there is a solution with $4k$ questions.

Let $x_1,\dots,x_{N^2}$ be the set of all $1\times1$ squares, and let $S_1,\dots,S_{4k}$ be all of the $(k+1)\times(k+1)$ squares which touch an edge of the board. It is easy to see that, if $x$ and $y$ are any two different $1\times1$ squares, there is some $S_i$ which contains just one of them. In other words, the map $x\mapsto\{S_i:x\subset S_i\}$ is an injection from $\{x_1,\dots,x_{N^2}\}$ to $\mathcal P(\{S_1,\dots,S_{4k}\}).$ Therefore, asking for the contents of each of the squares $S_1,\dots,S_{4k}$ will enable us to reconstruct the board.

If $N=2k$ there is a solution with $4k-1$ questions, namely, we use all of the $k\times k$ squares which touch an edge of the board, except for one corner square.