2
$\begingroup$

A popular mobile game, DiscoZoo, is about "rescuing" animals from a 5x5 grid of cells. Each animal represents a unique pattern (some have 3 cells, some have 4). The object is that, given this 5x5 grid, find all (or as many as possible) of the given animals within 10 turns, where the pattern of animals can be at any place within the grid (but cannot be rotated, change size, etc. - only translated such that all the coordinates of each animal are valid, and there is only one animal per square). We can only "get" an animal if we can successfully find each of the squares of that animal within the number of turns left; otherwise, we do not.

Here is an example. The sheep has a pattern of 4 horizontal adjacent squares, so clearly the squares (5, 2) (indexing from 1 and as (row, col)) and (5, 5) will be a sheep (and thus get the sheep). For the rabbit, it has a pattern of 4 vertical adjacent squares, so the squares (2, 1) and (4, 1) will be the rabbit. For the cow, it has a pattern of 3 horizontal adjacent squares, and since square (4, 2) was selected (and no animal placed there), the only square left for the cow is (4, 5). This is assuming that we do have attempts left (but there aren't any for this example).

enter image description here

More formally, we are given a 2D array $a[1..n][1..n]$, and $m$ animals $A_1,...A_m$ such that $A_i$ has value $p_i$. In the grid are the values of the $p_i$'s (in their respective positions) and all the rest are 0. Each cell either has 0 or one non-zero value (i.e., only one animal). However, none of the values are given to us at the start. Once we "select" a cell, that cell's value is revealed to us. Our objective is to find all or the maximum possible number of non-zero cells in the grid within $g$ turns.

What is the complexity of this problem in general?

Edit: after some thinking about the problem, let's restrict ourselves to having $m$ copies of the same animal $A$, and let that animal be a 2x2 square (i.e., occupies coordinates $(x, y), (x+1, y), (x, y+1), (x+1, y+1)$). What is the complexity of this version of the problem?

Even if we restrict further by looking at 1x1 squares, this is equivalent to finding nonzero elements in the matrix - it is trivially solvable in $\Theta(n^2)$ time, but can we do better?

Improve this question
$\endgroup$
7
  • $\begingroup$ Does picking an empty square give any information about the other squares? If not, then the obvious adversary argument should suffice to show that it's $\Omega(n^{2})$. $\endgroup$
    – Luke Mathieson
    Commented Apr 5, 2015 at 7:12
  • $\begingroup$ @LukeMathieson I think I gave a bad example here - but the idea is that the structure of one animal can give some info about another or even where the rest of the current one is. For example, if one animal had a spot in the upper left corner, we know everything about the rest of it. $\endgroup$
    – Ryan Dougherty
    Commented Apr 5, 2015 at 13:10
  • $\begingroup$ 1. I suspect you need to think more about how to model this, and how you'd like to measure the "goodness" of a strategy. Are you looking for a strategy that will perform well in the worst case? Or in the average case? This will make a huge difference. (And if the latter, you'll need to specify a distribution for how the animals are placed.) 2. This looks quite similar to Battleship. Is it different? Is the difference that there is a larger set of shapes possible? $\endgroup$
    – D.W. ♦
    Commented Apr 6, 2015 at 2:04
  • $\begingroup$ @D.W. Thanks for the comments. For (1), I was thinking of worst case, which seems to be $\Theta(n^2)$ but possibly not. For (2), it does seem like Battleship, but the coordinates are not necessarily entirely vertical or horizontal. $\endgroup$
    – Ryan Dougherty
    Commented Apr 6, 2015 at 2:06
  • $\begingroup$ OK. Another query: are you looking for (a) the time complexity of finding the optimal strategy, or (b) the complexity required to execute each step of the optimal strategy, or (c) the number of steps (i.e., number of attempts) needed to solve the puzzle in the worst case? The answer to (a) might well be very low complexity (even if it's intuitively hard to find the strategy), because there might exist a fast algorithm to print out the optimal strategy even though it's hard to find this best algorithm. (cont.) $\endgroup$
    – D.W. ♦
    Commented Apr 6, 2015 at 2:10

1 Answer 1

Reset to default
1
$\begingroup$

For the 2 by 2 block version in the edit, consider the promise problem where there is guaranteed to be just one block in each 3 by 3 region, where the regions have coordinates $(3i+1,3j+1)$ to $(3i+3,3j+3)$ for non-negative integers $i$ and $j$. By an adversary argument, in the worst case one may have to probe one square in each of the first $\lfloor n/3\rfloor^2-m$ regions and then two squares in each of the last $m$ regions, so in the worst case at least $\lfloor n/3\rfloor^2+m \ge ((n-2)/3)^2+m\ge \Omega(n^2)$ probes.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.