I'm looking to implement an algorithm that will calculate the minimum number of moves based on the rules below.
Let's say that we have a grid (NxM), as exampled in the image below.
Each cell will be the sum based on the row and column and I can subtract 1 unit from one cell and add it to a neighbour. For example, on the image above, the minimum number of moves on Initial will be 2 and on Initial - 2 will be 4.
Aha! Here's another angle on solving this:
Your problem is isomorphic to the Minimum Weighted Edge Cover problem on a bipartite graph.
To build some intuition: imagine your grid is initially at its resolved value, then we've scattered onto it a bunch of charged particles, like electrons (-1) and positrons (+1). Each electron or positron needs to make its way to its opposite to annihilate. Once all electron-positron pairs have annihilated, we've returned to the resolved value of the grid and found a solution.
So our problem becomes: how do we pair up the positive and negative charges ("computing a matching" between them), so that the total travel distance (number of swaps) is minimized?
To translate this into a graph: take each cell whose initial value is different from its resolved value. For every +1 value it has above its resolved value, create a "positive" node. For every -1 below, create a "negative" node.
Then form a bipartite graph by joining an edge from each positive node to every negative node. The length of the edge is the Manhattan distance between the two nodes' cells. (The number of moves it would take to bring the excess 1 to the cell with the deficit, or vice versa, or to make them meet somewhere in the middle)
We want to find a subset of these edges such that:
Every node is connected to exactly one chosen edge.
The total weight of all chosen edges is minimized.
The minimum weighted edge cover on a bipartite graph with a single assignment to each node is also called The Assignment Problem (specifically the linear balanced assignment problem).
The Wikipedia link has an overview of algorithms for solving it, including "The Hungarian Algorithm". Now you have several algorithms to choose from to do the heavy lifting. 🙂
An under-appreciated fact about the A* pathfinding algorithm is that it's not restricted to finding shortest paths in the spatial sense. It finds the shortest sequence of moves to solve any problem that can be expressed as walk on a graph.
And your problem is a walk on a graph.
Each node of the graph is one particular assignment of n x m numbers to the cells in the grid.
Each node has an edge leading to every other node that can be formed by subtracting 1 from one of its cells and adding 1 to a neighbouring cell.
So now you have a starting node (your "initial" state), a goal node (your "resolved" state), and a procedure to enumerate the nodes reachable from the current node (for each cell, subtract 1 from its value and try adding it to each of the cell's neighbours in turn).
All we need to add to use A* is a heuristic, to estimate how many swaps remain to be done. A good heuristic lets us focus our search on the most promising parts of the graph, and save time by not exploring "bad" moves.
We could just use a heuristic of 0 - that's admissible (it never over-estimates the remaining work), but it doesn't help us distinguish promising moves from useless / harmful ones. With this, A* effectively falls back to Djikstra's algorithm, exploring equally in all directions until it happens across the solution.
But we can do better. Iterate over all your cells, and for each one take the absolute value of the difference between its current value and its resolved value. Sum up those absolute differences to get the total amount of value we need to shunt around, and divide by 2 (since each step could potentially move 2 cells closer to their correct value).
This is also an admissible estimate (never over-estimates), and while it can under-estimate the distance, it's a lot more accurate - it gives the correct move count for all three of your examples, for instance.
You could probably do even better than this, by factoring in some spatial information. Like if a cell is 1 above its resolved value, and the closest cell below its own resolved value is 5 units away, you know you need to do at least 5 swaps to transport the excess to a suitable sink. But this is more complicated to compute, so there's a trade-off between choosing an accurate heuristic that lets you evaluate a minimal number of nodes, and choosing a cheap heuristic that you can evaluate quickly, so evaluating a few more nodes isn't a problem. Especially for small problem sizes, the options above might be all you need.
Once A* has found found its way to a solution, guided by this heuristic, it will report back the number of steps on the path from the initial state to the goal. This count is guaranteed to be the smallest possible, as long as you use an admissible heuristic.
This can be expressed as a maximum flow problem where the sources are the cells with values higher than desired and the sinks are cells with values lower than desired and each source points to every sink with infinite capacity.
The only difference from a traditional maximum flow problem is we also have to assign each path a length equal to the Manhattan distance and we must pick a solution that minimizes the distance of the pipes.
The most straightforward way to do this is brute force every possible solution to the maximum flow problem. But I suspect this problem can be solved greedily.
To do this pick the source that is farthest from any sink and distribute as much flow as you can from that source to the nearest sink. Then repeat until solved. I'm not 100% sure if this algorithm is correct but it appears to work.
