# Minimum Moves to Spread Stones Over Grid
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/minimum-moves-to-spread-stones-over-grid)
Canonical: https://scaleengineer.com/dsa/problems/minimum-moves-to-spread-stones-over-grid
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Algorithms:** [Breadth-First Search](https://scaleengineer.com/algorithms/breadth-first-search)
**Data structures:** Array, Matrix
**Companies:** [Geico](https://scaleengineer.com/companies/geico), [Guidewire](https://scaleengineer.com/companies/guidewire)
---
## Problem
You are given a **0-indexed** 2D integer matrix `grid` of size `3 * 3`, representing the number of stones in each cell. The grid contains exactly `9` stones, and there can be **multiple** stones in a single cell.

In one move, you can move a single stone from its current cell to any other cell if the two cells share a side.

Return _the **minimum number of moves** required to place one stone in each cell_.

**Example 1:**

![](https://assets.glich.co/dsa/minimum-moves-to-spread-stones-over-grid/image0.svg) 

**Input:** grid = [[1,1,0],[1,1,1],[1,2,1]]
**Output:** 3
**Explanation:** One possible sequence of moves to place one stone in each cell is: 
1- Move one stone from cell (2,1) to cell (2,2).
2- Move one stone from cell (2,2) to cell (1,2).
3- Move one stone from cell (1,2) to cell (0,2).
In total, it takes 3 moves to place one stone in each cell of the grid.
It can be shown that 3 is the minimum number of moves required to place one stone in each cell.

**Example 2:**

![](https://assets.glich.co/dsa/minimum-moves-to-spread-stones-over-grid/image1.svg) 

**Input:** grid = [[1,3,0],[1,0,0],[1,0,3]]
**Output:** 4
**Explanation:** One possible sequence of moves to place one stone in each cell is:
1- Move one stone from cell (0,1) to cell (0,2).
2- Move one stone from cell (0,1) to cell (1,1).
3- Move one stone from cell (2,2) to cell (1,2).
4- Move one stone from cell (2,2) to cell (2,1).
In total, it takes 4 moves to place one stone in each cell of the grid.
It can be shown that 4 is the minimum number of moves required to place one stone in each cell.

**Constraints:**

* `grid.length == grid[i].length == 3`
* `0 <= grid[i][j] <= 9`
* Sum of `grid` is equal to `9`.

# Approaches
## Brute-Force with Permutations
This approach formulates the problem as a classic assignment problem. We need to move extra stones from 'source' cells (more than one stone) to 'destination' cells (zero stones). The goal is to find a one-to-one mapping between the extra stones and empty cells that minimizes the total number of moves. Since the number of stones to move is small (at most 8), we can explore every possible assignment. This is equivalent to generating all permutations of the destination cells and calculating the total cost for each.
**Time:** O(k! * k), where k is the number of empty cells. The algorithm generates k! permutations of the `emptyCells` list. For each permutation, it takes O(k) time to calculate the total Manhattan distance. Given that k is at most 8, this is computationally feasible. · **Space:** O(k), where k is the number of empty cells. This space is used to store the `excessStones` and `emptyCells` lists, as well as for the recursion stack during permutation generation.
**Pros:** Conceptually straightforward and relatively easy to implement.; Guaranteed to find the optimal solution because it exhaustively checks every possibility.
**Cons:** The factorial time complexity `O(k!)` makes this approach impractical for slightly larger grids or more items to match.; It is less efficient than dynamic programming, even for the small constraints of this problem.
### Explanation
The core idea is to perform a brute-force search over all possible pairings of surplus stones with empty cells.

1.  **Identify Sources and Destinations:** First, we iterate through the 3x3 grid to find two types of cells:
    *   Cells with `grid[i][j] > 1`: These are sources of extra stones. For each such cell, we add its coordinates `(i, j)` to a list called `excessStones` exactly `grid[i][j] - 1` times.
    *   Cells with `grid[i][j] == 0`: These are empty cells that need a stone. We add their coordinates `(i, j)` to a list called `emptyCells`.

2.  **Generate Permutations:** The problem is now to match each stone in `excessStones` to a unique cell in `emptyCells`. We can solve this by trying every possible permutation of the `emptyCells` list. For each permutation, we pair the first excess stone with the first cell in the permuted list, the second stone with the second cell, and so on.

3.  **Calculate Cost:** For each complete pairing (permutation), we calculate the total moves required. The number of moves to transfer one stone from `(r1, c1)` to `(r2, c2)` is the Manhattan distance: `|r1 - r2| + |c1 - c2|`. We sum these distances for all pairs in the current assignment.

4.  **Find Minimum:** We keep track of the minimum total moves found across all permutations. After checking all permutations, this minimum value is the solution.

```java
import java.util.ArrayList; 
import java.util.Collections;
import java.util.List;

class Solution {
    private List<int[]> excessStones = new ArrayList<>();
    private List<int[]> emptyCells = new ArrayList<>();
    private int minMoves = Integer.MAX_VALUE;

    public int minimumMoves(int[][] grid) {
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                if (grid[i][j] > 1) {
                    for (int k = 0; k < grid[i][j] - 1; k++) {
                        excessStones.add(new int[]{i, j});
                    }
                } else if (grid[i][j] == 0) {
                    emptyCells.add(new int[]{i, j});
                }
            }
        }

        if (excessStones.isEmpty()) {
            return 0;
        }

        permute(0);
        return minMoves;
    }

    private void permute(int start) {
        if (start == emptyCells.size()) {
            int currentMoves = 0;
            for (int i = 0; i < excessStones.size(); i++) {
                currentMoves += Math.abs(excessStones.get(i)[0] - emptyCells.get(i)[0]) +
                                Math.abs(excessStones.get(i)[1] - emptyCells.get(i)[1]);
            }
            minMoves = Math.min(minMoves, currentMoves);
            return;
        }

        for (int i = start; i < emptyCells.size(); i++) {
            Collections.swap(emptyCells, start, i);
            permute(start + 1);
            Collections.swap(emptyCells, start, i); // backtrack
        }
    }
}
```
### Algorithm
- Identify cells with more than one stone (sources) and cells with zero stones (destinations).
- Create a list `excessStones` containing the coordinates of each extra stone. If a cell has `g` stones, its coordinate is added `g-1` times.
- Create a list `emptyCells` containing the coordinates of each empty cell.
- Generate all possible permutations of the `emptyCells` list.
- For each permutation, calculate the total cost by summing the Manhattan distances between the `i`-th stone in `excessStones` and the `i`-th cell in the permuted `emptyCells` list.
- The minimum cost found among all permutations is the answer.

## Dynamic Programming with Bitmasking
This approach significantly optimizes the brute-force method by using dynamic programming with bitmasking. Instead of re-calculating the cost for the same subproblems, we store the results in a memoization table. A subproblem is defined by `(stoneIndex, mask)`, representing the minimum moves to place the remaining stones (from `stoneIndex` onwards) into a specific set of available empty cells (represented by `mask`). This avoids the redundant computations inherent in the permutation approach and reduces the complexity from factorial to exponential, which is a substantial improvement.
**Time:** O(k^2 * 2^k), where k is the number of empty cells. There are `k * 2^k` possible states for `(stoneIndex, mask)`. For each state, we iterate through `k` possible empty cells to find a match. This is very fast for `k <= 8`. · **Space:** O(k * 2^k), where k is the number of empty cells. This space is dominated by the memoization table. The recursion stack depth adds an additional O(k).
**Pros:** Much more efficient than the brute-force permutation approach, with a significant reduction in time complexity.; Guaranteed to find the optimal solution.; It is a standard and powerful technique (DP on subsets) for solving assignment and matching problems with small numbers of items.
**Cons:** The time complexity is still exponential, making it unsuitable for problems where `k` is large (e.g., > 20).; Requires significantly more memory (`O(k * 2^k)`) for the memoization table compared to the permutation approach.; The logic involving bitmasking can be more complex to understand and implement correctly.
### Explanation
This method solves the assignment problem more efficiently by using recursion with memoization, a technique also known as top-down dynamic programming.

1.  **Identify Sources and Destinations:** This step is the same as the brute-force approach. We populate the `excessStones` and `emptyCells` lists.

2.  **Define State for DP:** We define a recursive function that represents a state of the problem. A good state representation is `(stoneIndex, mask)`, where `stoneIndex` is the index of the stone from the `excessStones` list we are currently trying to place, and `mask` is a bitmask representing the set of *used* `emptyCells`. If the `j`-th bit of `mask` is 1, it means the `j`-th cell in `emptyCells` has been filled.

3.  **Recursive Relation with Memoization:**
    *   The function `solve(stoneIndex, mask)` will compute the minimum moves to place stones from `stoneIndex` to the end of the list, given that the cells in `mask` are already taken.
    *   **Base Case:** If `stoneIndex` reaches the size of `excessStones`, it means all stones have been placed, so we return 0.
    *   **Memoization:** Before computing, we check if `memo[stoneIndex][mask]` has already been calculated. If so, we return the stored value.
    *   **Recursion:** We iterate through all empty cells `j`. If the `j`-th cell is available (`(mask & (1 << j)) == 0`), we calculate the cost of moving `excessStones[stoneIndex]` to `emptyCells[j]`. We then recursively call `solve(stoneIndex + 1, mask | (1 << j))` to get the minimum cost for the rest of the stones. We take the minimum over all possible choices for the current stone.
    *   The result is stored in `memo[stoneIndex][mask]` before being returned.

4.  **Initial Call:** The process starts by calling `solve(0, 0)`, which means we begin by placing the 0-th stone with no empty cells initially occupied.

```java
import java.util.ArrayList;
import java.util.List;

class Solution {
    private List<int[]> excessStones = new ArrayList<>();
    private List<int[]> emptyCells = new ArrayList<>();
    private Integer[][] memo;

    public int minimumMoves(int[][] grid) {
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                if (grid[i][j] > 1) {
                    for (int k = 0; k < grid[i][j] - 1; k++) {
                        excessStones.add(new int[]{i, j});
                    }
                } else if (grid[i][j] == 0) {
                    emptyCells.add(new int[]{i, j});
                }
            }
        }

        if (excessStones.isEmpty()) {
            return 0;
        }

        int k = excessStones.size();
        memo = new Integer[k][1 << k];
        return solve(0, 0);
    }

    private int solve(int stoneIndex, int mask) {
        if (stoneIndex == excessStones.size()) {
            return 0;
        }

        if (memo[stoneIndex][mask] != null) {
            return memo[stoneIndex][mask];
        }

        int minCost = Integer.MAX_VALUE;
        int[] source = excessStones.get(stoneIndex);

        for (int i = 0; i < emptyCells.size(); i++) {
            // Check if the i-th empty cell is NOT used
            if ((mask & (1 << i)) == 0) {
                int[] dest = emptyCells.get(i);
                int cost = Math.abs(source[0] - dest[0]) + Math.abs(source[1] - dest[1]);
                
                // Recurse for the next stone, marking the i-th cell as used
                int remainingCost = solve(stoneIndex + 1, mask | (1 << i));
                
                if (remainingCost != Integer.MAX_VALUE) {
                    minCost = Math.min(minCost, cost + remainingCost);
                }
            }
        }

        return memo[stoneIndex][mask] = minCost;
    }
}
```
### Algorithm
- First, identify and create lists of `excessStones` and `emptyCells` as in the previous approach. Let their size be `k`.
- Define a recursive function, `solve(stoneIndex, mask)`, which calculates the minimum cost to place stones from `stoneIndex` to `k-1` into the available empty cells.
- The `mask` is a bitmask where the `i`-th bit being set indicates that the `i`-th empty cell is already occupied.
- Use a 2D array, `memo[stoneIndex][mask]`, to store the results of subproblems to avoid redundant computations.
- The base case for the recursion is when all stones are placed (`stoneIndex == k`), which costs 0.
- In the recursive step, iterate through all empty cells. If a cell is not yet occupied (checked via the mask), calculate the cost to move the current stone there and add it to the result of the recursive call for the next stone with an updated mask.
- The final answer is the result of the initial call `solve(0, 0)`.

# Solutions
### Java

```java
class Solution {
public
  int minimumMoves(int[][] grid) {
    Deque<String> q = new ArrayDeque<>();
    q.add(f(grid));
    Set<String> vis = new HashSet<>();
    vis.add(f(grid));
    int[] dirs = {-1, 0, 1, 0, -1};
    for (int ans = 0;; ++ans) {
      for (int k = q.size(); k > 0; --k) {
        String p = q.poll();
        if ("111111111".equals(p)) {
          return ans;
        }
        int[][] cur = g(p);
        for (int i = 0; i < 3; ++i) {
          for (int j = 0; j < 3; ++j) {
            if (cur[i][j] > 1) {
              for (int d = 0; d < 4; ++d) {
                int x = i + dirs[d];
                int y = j + dirs[d + 1];
                if (x >= 0 && x < 3 && y >= 0 && y < 3 && cur[x][y] < 2) {
                  int[][] nxt = new int[3][3];
                  for (int r = 0; r < 3; ++r) {
                    for (int c = 0; c < 3; ++c) {
                      nxt[r][c] = cur[r][c];
                    }
                  }
                  nxt[i][j]--;
                  nxt[x][y]++;
                  String s = f(nxt);
                  if (!vis.contains(s)) {
                    vis.add(s);
                    q.add(s);
                  }
                }
              }
            }
          }
        }
      }
    }
  }
private
  String f(int[][] grid) {
    StringBuilder sb = new StringBuilder();
    for (int[] row : grid) {
      for (int x : row) {
        sb.append(x);
      }
    }
    return sb.toString();
  }
private
  int[][] g(String s) {
    int[][] grid = new int[3][3];
    for (int i = 0; i < 3; ++i) {
      for (int j = 0; j < 3; ++j) {
        grid[i][j] = s.charAt(i * 3 + j) - '0';
      }
    }
    return grid;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int minimumMoves(vector<vector<int>> &grid) {
    using pii = pair<int, int>;
    vector<pii> left, right;
    for (int i = 0; i < 3; ++i) {
      for (int j = 0; j < 3; ++j) {
        if (grid[i][j] == 0) {
          left.emplace_back(i, j);
        } else {
          for (int k = 1; k < grid[i][j]; ++k) {
            right.emplace_back(i, j);
          }
        }
      }
    }
    auto cal = [](pii a, pii b) {
      return abs(a.first - b.first) + abs(a.second - b.second);
    };
    int n = left.size();
    int f[1 << n];
    memset(f, 0x3f, sizeof(f));
    f[0] = 0;
    for (int i = 1; i < 1 << n; ++i) {
      int k = __builtin_popcount(i);
      for (int j = 0; j < n; ++j) {
        if (i >> j & 1) {
          f[i] = min(f[i], f[i ^ (1 << j)] + cal(left[k - 1], right[j]));
        }
      }
    }
    return f[(1 << n) - 1];
  }
};

```

### Python

```python
class Solution:
    def minimumMoves(self, grid: List[List[int]]) -> int: q = deque([tuple(tuple(row) for row in grid)]) vis = set(q) ans = 0 dirs = (- 1, 0, 1, 0, - 1) while 1: for _ in range(len(q)): cur = q . popleft() if all(x for row in cur for x in row): return ans for i in range(3): for j in range(3): if cur[i][j] > 1: for a, b in pairwise(dirs): x, y = i + a, j + b if 0 <= x < 3 and 0 <= y < 3 and cur[x][y] < 2: nxt = [list(row) for row in cur] nxt[i][j] -= 1 nxt[x][y] += 1 nxt = tuple(tuple(row) for row in nxt) if nxt not in vis: vis . add(nxt) q . append(nxt) ans += 1

```