Minimum Moves to Spread Stones Over Grid — Hard Problem & Solution

A 3 × 3 grid holds nine stones in total, but some cells may hold several and some none.

Difficulty: Hard
Topics: Arrays, Dynamic Programming, Matrix, Breadth-First Search
Asked at: Amazon, Google, Zomato
Time limit: 2 s
Memory limit: 256 MB
Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

A 3 × 3 grid holds nine stones in total, but some cells may hold several and some none. In one move you may take one stone from a cell and move it to an adjacent cell — up, down, left or right.

Return the minimum number of moves needed to leave exactly one stone in every cell.

Example 1

Input: grid = [[1,1,0],[1,1,1],[1,2,1]]
Output: 3
Explanation: Walk a stone from `(2,1)` up and left to the empty `(0,2)`.

Example 2

Input: grid = [[1,3,0],[1,0,0],[1,0,3]]
Output: 4

Example 3

Input: grid = [[1,1,1],[1,1,1],[1,1,1]]
Output: 0

Constraints

grid.length == grid[i].length == 3
0 <= grid[i][j] <= 9
The sum of grid is 9.

How to solve Minimum Moves to Spread Stones Over Grid

Reduce to an assignment problem. Each surplus stone must end in some empty cell, the cost of a pairing is the Manhattan distance, and the answer is the minimum-cost perfect matching between the two equal-sized lists.

Approach

Build from, one entry per spare stone (a cell with c stones contributes c - 1).
Build to, one entry per empty cell. The two lists have the same length because the grid sums to 9.
Try every way to assign spares to holes, summing Manhattan distances, and keep the cheapest.
Prune a branch as soon as its partial cost reaches the best found.

Why it works

A stone can always travel along a shortest Manhattan route — the other stones never block it, since a cell may hold any number on the way — so the cost of a pairing really is the sum of distances, and no cleverer routing exists. Both lists have at most 8 entries, so 8! = 40 320 assignments is trivially searchable; bitmask DP over the holes is the O(2^k · k) refinement.

Complexity

Time — O(k!) with pruning, k <= 8 — or O(2^k · k) with bitmask DP
Space — O(k)

Pitfalls

A cell with c stones has c - 1 spares, not c.
Stones do not obstruct each other, so the cost is plain Manhattan distance — no BFS needed.
An already-correct grid answers 0; the search must handle both lists being empty.

Reference solution

Python

from typing import List

def minimumMoves(grid: List[List[int]]) -> int:
    src, dst = [], []
    for i in range(3):
        for j in range(3):
            if grid[i][j] > 1:
                src.extend([(i, j)] * (grid[i][j] - 1))
            elif grid[i][j] == 0:
                dst.append((i, j))
    k = len(src)
    used = [False] * k
    best = [float('inf')]

    def walk(idx: int, cost: int) -> None:
        if cost >= best[0]:
            return
        if idx == k:
            best[0] = cost
            return
        for t in range(k):
            if used[t]:
                continue
            used[t] = True
            walk(idx + 1, cost + abs(src[t][0] - dst[idx][0]) + abs(src[t][1] - dst[idx][1]))
            used[t] = False

    walk(0, 0)
    return 0 if best[0] == float('inf') else best[0]

JavaScript

var minimumMoves = function(grid) {
    var from = [], to = [], i, j, kk;
    for (i = 0; i < 3; i++) {
        for (j = 0; j < 3; j++) {
            if (grid[i][j] > 1) {
                for (kk = 1; kk < grid[i][j]; kk++) from.push([i, j]);
            } else if (grid[i][j] === 0) {
                to.push([i, j]);
            }
        }
    }
    var k = from.length;
    var used = [];
    for (i = 0; i < k; i++) used.push(false);
    var best = Infinity;
    var walk = function(idx, cost) {
        if (cost >= best) return;
        if (idx === k) { best = cost; return; }
        for (var t = 0; t < k; t++) {
            if (used[t]) continue;
            used[t] = true;
            walk(idx + 1, cost + Math.abs(from[t][0] - to[idx][0]) + Math.abs(from[t][1] - to[idx][1]));
            used[t] = false;
        }
    };
    walk(0, 0);
    return best === Infinity ? 0 : best;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue