# Solution: Minimum Moves to Spread Stones Over Grid

Let's solve the Minimum Moves to Spread Stones Over Grid problem using the Backtracking pattern.

## We'll cover the following

## Statement

Given a 2D grid of integers of size (

**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.

First, we check if there are exactly

If a cell is empty, we mark down its position.

If a cell has more than one stone, we note its position and the number of extra stones.

Once we know the locations of the empty cells and the cells with extra stones, we start exploring possible moves. We try placing each extra stone into each empty cell, one by one, and calculate the moves needed for each trial. The number of moves to transfer a stone from the extra cell at position

â€ƒâ€ƒâ€ƒâ€ƒâ€ƒâ€ƒâ€ƒâ€ƒâ€ƒâ€ƒâ€ƒâ€ƒâ€ƒâ€ƒ

During the process, we keep track of the minimum number of moves to distribute all the stones, considering different combinations. After each trial, if the number of moves for that specific trial is less than the current minimum, we update the minimum number of moves. Additionally, after trying out one possible way to spread the stones, we backtrack and try other possible combinations. Once we have tried all possible combinations and calculated the number of moves for each possible combination of stone moves, we return the minimum number of moves.

Here are the detailed steps of this approach:

Populate the

`zeros`

array with the coordinates of the empty cells.Populate the

`extras`

array with the coordinates of the cells with more than one stone and the count of the extra stones. Also, initialize the`minMoves`

variable with a high value.Call the solution function to start with the first empty cell in

`zeros`

with the initial number of moves as zero. Iterate over each cell in`extras`

and move a stone from the cell in`extras`

to the cell in`zeros`

.Calculate the number of moves by computing the Manhattan distance between the current cell in

`extras`

and the current empty cell.Recursively call the solution function with the index of the next empty cell in

`zeros`

, and the sum of the number of moves calculated in the previous and current function call to fill the next empty cells in`zeros`

with the remaining cells in`extras`

.After all the empty cells are filled, update the value of the

`minMoves`

variable by calculating the minimum of the current total number of moves and the previous value of`minMoves`

.Then, backtrack to the previous recursive function call, placing back the stone removed from the previous cell in

`extras`

, and iterate to the next stone in`extras`

to fill the current empty cell in`zeros`

.Finally, return the value of

`minMoves`

once all possible choices of moving stones from the`extras`

to the cells in`zeros`

have been explored.

The following illustration shows these steps in detail:

Level up your interview prep. Join Educative to access 80+ hands-on prep courses.