Spread Nine Stones Across a Three-by-Three Grid with Minimum Moves

Problem Statement

You are given a 3 x 3 integer matrix grid representing the distribution of stones. There are exactly 9 stones in total placed across the grid. Some cells may contain multiple stones, while others may be empty.

In one move, you can transfer a single stone from its current cell to an orthogonally adjacent cell (up, down, left, or right).

Return the minimum number of moves required to place exactly one stone in every cell of the grid.

Function Signature

def minimum_moves(grid: list[list[int]]) -> int:
    pass

Constraints

• grid has dimensions 3 x 3.
• 0 <= grid[i][j] <= 9 for all 0 <= i, j < 3.
• The sum of all elements in grid is exactly 9.

Examples

Example 1

Input: grid = [
  [1, 1, 0],
  [1, 1, 1],
  [1, 2, 1]
]
Output: 3
Explanation:
One stone from cell (2, 1) must be moved to the empty cell (0, 2).
The Manhattan distance between (2, 1) and (0, 2) is |2 - 0| + |1 - 2| = 2 + 1 = 3.
Therefore, 3 moves are required.

Example 2

Input: grid = [
  [1, 3, 0],
  [1, 0, 0],
  [1, 0, 3]
]
Output: 4
Explanation:
Empty cells: (0, 2), (1, 1), (1, 2), (2, 1).
Surplus stones: two extra at (0, 1) and two extra at (2, 2).
One optimal assignment is:
- Move one stone from (0, 1) to (0, 2) -> distance 1
- Move one stone from (0, 1) to (1, 1) -> distance 1
- Move one stone from (2, 2) to (1, 2) -> distance 1
- Move one stone from (2, 2) to (2, 1) -> distance 1
Total moves = 1 + 1 + 1 + 1 = 4.

Edge Cases

• The grid is already uniform (grid[i][j] == 1 for all cells); the result should be 0.
• All 9 stones start in a single cell (e.g., grid[0][0] = 9); all other 8 cells must receive one stone from that source.