I am trying to find the name of an algorithm for a game I am making. I am pretty sure it exists, but I have no idea what name it has.

Say I have a matrix like:

$$ \begin{array}{|r|r|r|} \hline \hphantom{-}1 & -1 & 0 \\\hline 0 & 0 & 1 \\\hline 0 & 1 & -2 \\\hline \end{array} $$

I know that the sum of each element of the matrix is zero.

And an operation $f$ which sums two elements of the matrix together and replaces both of them with this sum. In our example $f( a_{1,1} a_{1,2} )$ (where $a_{r,c}$ is the element of the matrix at row $r$ and column $c$) would lead to

$$ \begin{array}{|r|r|r|} \hline \hphantom{-}0 & \hphantom{-}0 & 0 \\\hline 0 & 0 & 1 \\\hline 0 & 1 & -2 \\\hline \end{array} $$

The cost of this operation is the Manhattan distance between the two points, in this case $1$.

Now, I want to find the moves that:

  • make each element of the matrix go to $0$
  • minimize the total cost

Is there an algorithm (or a combination of them) that does that? Sorry for the laymen lingo, I am not a programmer myself!

  • 1
    $\begingroup$ What do you mean by "sums two elements"? Do you mean replacing the two elements with their sum? $\endgroup$ Sep 27, 2018 at 16:44
  • $\begingroup$ What does (a1,1) mean? Do you mean the matrix element at (1,1)? What is a1? $\endgroup$
    – D.W.
    Sep 27, 2018 at 20:34
  • $\begingroup$ @D.W. yes, with (a1,1) I meant the matrix element at (1,1). Sorry, I only write those on paper! $\endgroup$
    – Frabetto
    Sep 28, 2018 at 9:01
  • $\begingroup$ @YuvalFilmus yes, replacing the two elements with their sum! $\endgroup$
    – Frabetto
    Sep 28, 2018 at 9:02
  • 1
    $\begingroup$ I don't think replacing elements with their sum. Then [[0 1] [1 -2]] would not work. First move: [[0 2] [2 -2]]. Maybe just move one into another. Which satisfies your description. $\endgroup$
    – rus9384
    Sep 28, 2018 at 22:58

1 Answer 1


You could always try the A* algorithm. It might not be optimal but it is something you could try, and depending on how big the matrix is it might be good enough. You'll need to design an appropriate heuristic (e.g., maybe the number of elements that are non-zero, divided by two?).

  • $\begingroup$ I cannot upvote as now, but let me thanks you here. $\endgroup$
    – Frabetto
    Sep 28, 2018 at 9:02
  • 2
    $\begingroup$ @Frabetto You may not be able to upvote but you can accept the answer. $\endgroup$ Jan 28, 2019 at 22:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.