Solution: Minimum Moves to Spread Stones Over Grid

Explore how backtracking helps solve the problem of distributing stones on a 3x3 grid with minimum moves. Understand the use of recursion, Manhattan distance, and combinatorial exploration to assign stones from cells with extras to empty cells efficiently. Learn how to track and minimize moves while backtracking through possible distributions, gaining problem-solving skills applicable to grid-based challenges.

We'll cover the following...

Statement
Solution
- Time complexity
- Space complexity

Statement

Given a 2D grid of integers of size ( $3 \times 3$ ), where each value represents the number of stones in the given cell, return the minimum number of moves required to place exactly one stone in each grid cell.

Constraints:

Only one stone can be moved in one move.
Stone from a cell can only be moved to another cell if they are adjacent (share a side).
The sum of all stones in the grid must be equal to $9$ .
grid.length, grid[i].length $= 3$
$0 \le$ grid[i][j] $\le 9$

Solution

This solution works by trying different combinations of moving extra stones around the grid until each empty cell has at least one stone. ...