Minimum Moves to Spread Stones Over Grid - Video Solutions

Problem Overview: You are given a 3×3 grid containing exactly 9 stones, but some cells may hold multiple stones while others are empty. In one move, you can move a stone to an adjacent cell (up, down, left, right). The goal is to redistribute the stones so every cell contains exactly one stone while minimizing the number of moves.

Approach 1: Breadth-First Search (State Exploration) (Time: O(S), Space: O(S))

This approach treats the entire grid configuration as a state and performs a Breadth-First Search to find the shortest sequence of moves that leads to the target configuration where every cell contains exactly one stone. Each state is encoded as a 9-element array or string representing the grid. From a given state, generate neighbors by moving a stone from any cell with more than one stone to an adjacent cell. A visited set prevents revisiting configurations. Since BFS expands level by level, the first time you reach the valid configuration guarantees the minimum number of moves.

Approach 2: DFS with Backtracking (Assignment Search) (Time: O(k!), Space: O(k))

Instead of exploring grid states, this method focuses on matching surplus stones with empty cells. First iterate through the matrix and record coordinates of cells with extra stones and coordinates of empty cells. Then use depth‑first search with backtracking to assign each extra stone to an empty position. The cost of assigning a stone at (r1, c1) to (r2, c2) is the Manhattan distance |r1-r2| + |c1-c2|, which equals the minimum number of adjacent moves required. Try all permutations of assignments and track the minimum total cost. Because the grid is small (at most 6 extra stones), the factorial search space remains manageable.

Approach 3: Greedy Distance Matching (Time: O(k log k), Space: O(k))

A simpler strategy collects all extra stone positions and all empty cells, then pairs them based on distance. Compute the Manhattan distance between each surplus stone and candidate empty cells and greedily move stones to the nearest target. The key insight is that moving a stone step‑by‑step across the grid effectively accumulates Manhattan distance. While this heuristic often works due to the small grid size, it does not guarantee optimality in every theoretical arrangement. It is useful for quick reasoning and interview discussions when explaining the movement cost model.

Approach 4: BFS with Distance Modeling (Time: O(k! * k), Space: O(k))

Another variation builds the solution by repeatedly moving surplus stones toward empty cells using BFS distance calculations. For each extra stone, compute the shortest path distance to each empty cell and explore combinations. This approach blends graph traversal with assignment search and highlights how shortest paths on a grid correspond to Manhattan distance in unobstructed cases.

Recommended for interviews: The DFS backtracking assignment is the most commonly expected solution. It clearly models the problem as matching extra stones to empty cells and demonstrates strong reasoning about Manhattan distance and permutation search. BFS over full grid states proves correctness but introduces larger state space overhead. Mentioning both shows solid understanding of array manipulation and graph traversal techniques.