Minimum Moves to Spread Stones Over Grid

Minimum Moves to Spread Stones Over Grid

1. What is this problem about?

You are given a $3 \times 3$ grid where each cell contains some number of stones. The total number of stones is exactly 9. However, some cells have 0 stones, and some have more than 1.

Your goal is to move the stones such that every cell has exactly 1 stone. In one move, you can move one stone from a cell to an adjacent cell (up, down, left, right). You want to find the minimum total moves required.

2. Why is this asked in interviews?

Microsoft and Google use this to test Permutations and Bipartite Matching (or simply Recursion/Backtracking). Key competencies:

• Source and Sink: Identifying which cells have "extra" stones (sources) and which have "zero" stones (sinks).
• Optimization: Finding the best pairing of stones to empty cells.
• Recursion: Using backtracking to try all possible pairings since the grid is small ($3 \times 3$).

3. Algorithmic pattern used

The pattern is Backtracking (Permutations).

1. Create a list of all "extra" stones. If a cell has 3 stones, add its coordinates to the list twice (since 2 stones need to move).
2. Create a list of all "empty" cells.
3. Use recursion to pair each "extra" stone with an "empty" cell.
4. For each pair, the cost is the Manhattan distance: abs(r1 - r2) + abs(c1 - c2).
5. Return the minimum total cost across all possible permutations of pairings.

4. Example explanation

Grid:

3 0 0
0 1 1
0 2 2

• Extra stones at (0, 0): 2 stones to move. List: [(0,0), (0,0)].
• Extra stones at (2, 1): 1 stone. List: [(0,0), (0,0), (2,1)].
• Extra stones at (2, 2): 1 stone. List: [(0,0), (0,0), (2,1), (2,2)].
• Empty cells: (0, 1), (0, 2), (1, 0), (2, 0). We need to pair the 4 extra stones with the 4 empty cells to minimize total Manhattan distance.

5. Common mistakes candidates make

• Greedy Pairing: Trying to move a stone to the closest empty cell. This might leave another stone with an extremely long journey. You must consider all pairings.
• Complex Pathfinding: Using BFS to find the distance between cells. In a grid without obstacles, the shortest distance is always the Manhattan distance.
• Overlooking Permutations: Not realizing that with only 9 cells, $O(n!)$ where $n \le 9$ is perfectly fine.

6. Interview preparation tip

When the input size is very small (like a $3 \times 3$ grid), always consider "Brute Force with Recursion" or "Bitmask DP." These techniques are often simpler to implement and more robust than trying to find a clever greedy or flow-based solution.