Algorithms: Rearrange 2D Matrix (through element 'flipping')

Answer 1

nice puzzle! anyway, you can try modified versions of sorting algorithms. i'm not too good on the implementations but i could try to give you one later. another way to solve this is through the A* algorithm. it's a path searching algorithm used in artificial intelligence, but i've seen it apply to a problem similar to this.

Answer 2

The part about not being able to flip diagonally is a red herring. (Just flip an element with the one next to it, then the one below it.) So any element can be exchanged with any other element in the matrix by repeated flips. Continue this line of reasoning, and you'll see that your desired final state is a matrix containing the elements in ascending order, increasing from left to right and from top to bottom (as in your final state).

To produce this final result quickly, just reshape the initial matrix from a 2-D array to a flat list. Sort. Then reshape back to a 2-D array.

If you need to know a sequence of legal moves that can generate the final result (note that such a sequence is not unique!), the following simple algorithm will do it:

1. Start by positioning the element that belongs in the upper left corner; this is the current position.
2. Find the minimum element in the rest of the matrix.
3. Flip this element left until it reaches the column of the current position, then up until it reaches the row of the current position.
4. Mark the current position as properly placed.
5. Move to the next position by shifting the current position one index to the right, or to the beginning of the next line if an entire row has been positioned.
6. Repeat until the entire matrix has been positioned.

Optimally efficient? Unlikely. Simple and effective? Absolutely.