I'm wondering about an algorithm solving the following (efficiently): A 2D matrix of numbers [1..9] which need to align in horizontal lines from top (1) to bottom (9), but only through flipping either vertically or horizontally with another number.
Example Input Matrix:
1 8 2 6 1 6
9 2 5 1 6 2
3 6 9 2 9 8
5 1 7 4 2 8
4 2 7 6 9 5
Desired Output Matrix:
1 1 1 1 2 2
2 2 2 2 3 4
4 5 5 5 6 6
6 6 6 7 7 8
8 8 9 9 9 9
Clarification on 'Flipping': Take the input matrix for example. There is a "1" in the top left corner. That 1 can either flip horizontally with the 8 next to it (first row becomes now 8 1 2 6 1 6
) or vertically with the 9 below it (first column becomes now 9 1 3 5 4
). It can't flip with the 2 diagonally.
Any solutions (any language is fine) to this problem?