0
$\begingroup$

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

Example 3x3 matrix solution

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.

$\endgroup$
1
  • $\begingroup$ 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." $\endgroup$
    – dlid
    Nov 17, 2020 at 0:34

1 Answer 1

0
$\begingroup$

This is a variation to the Travelling salesman problem. Finding the shortest path that passes through all nodes (and distance here is defined by the difference between the numbers).

For small cases, you can solve this with a brute force search. An alternative could be to use the nearest neighbour algorithm.

$\endgroup$

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.