# Algorithm for the path with least differences between adjacent cells

This problem is kind of a mathematical riddle to me. Suppose you have a specific rectangular matrix of empty cells, let's say 3x3 matrix for example, and your goal is to make a path of linearly ascending numbers that would go through the whole matrix, such as in the picture below. You can choose the starting cell freely, but you can move from your current cell only to the adjacent ones (diagonal movement is permitted) and you cannot enter the same cell twice. The catch is that you must choose the path that gives the least sum of absolute differences between each cell's number and the adjacent cells (even diagonally).

In the example picture provided, that would mean this score for cell with number "1" equals (|2-1|+|5-1|+|6-1|)=(1+4+5)=10. For cell "2" it is (|1-2|+|3-2|+|4-2|+|5-2|+|6-2|)=(1+1+2+3+4)=11; and so on. The final score of this path is the sum of these "difference" scores for each cell.

My ultimate goal is to find the path combination(s) with the lowest final score on a 10x10 matrix, but I have no idea how to approach this problem. I do not need the algorithm per se, just the path with the lowest final score on 10x10 matrix.

Any help is appreciated.

• I'm not sure this question belongs here -- what is the statistical component? Might make more sense at math.stackexchange.com as you mentioned it's a "mathematical riddle."
– dlid
Nov 17, 2020 at 0:34