Grid Mouse Detection

Requirements Clarification & Assessment

1. Understanding the Problem:

   • We have a 4x4 grid, making a total of 16 cells.
   • A mouse is hidden in one of these cells.
   • We can perform queries by selecting a subset of cells to determine if the mouse is within that subset.
   • The task is to find the mouse using the minimum number of scans.

2. Constraints and Assumptions:

   • Each scan returns a binary result: whether the mouse is present in the selected subset or not.
   • The exact cell is not revealed, only the presence within the subset.
   • The grid is static, meaning the mouse does not move between scans.
   • We aim to minimize the number of scans, ideally using an efficient algorithmic approach.

3. Goals:

   • Develop an algorithm that efficiently locates the mouse.
   • Ensure the approach is scalable and can be adapted for grids of different sizes if needed.

4. Potential Challenges:

   • Determining the optimal way to divide the grid for scanning.
   • Ensuring that the solution is both efficient and easy to understand.