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

Tag: algorithm Author: petroleum001 Date: 2009-08-11

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?
Also, please clarify: When you say efficiently, do you mean the runtime of the algorithm, or the length (in moves) of the solution?
@Walt: Greater efficiency would be assumed with less number of moves.
@Alex: Then that A* suggestion's really good. A*'s guaranteed optimal if your heuristic is smaller than the actual distance remaining.
@WaltW although OP says less number of moves, i still think he means the runtime of the algorithm. Otherwise one wouldn't say efficient but optimal

Best Answer

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.

Other Answer1

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.

comments:

A*'s a good suggestion here . . . The manhattan distance would be a good heuristic, and would be fairly straightforward to calculate here (just iterate through your matrix, summing |xdesired - xactual| + |ydesired - yactual| which can be approximated easily by keeping track of which rows you've filled in the tally).

Relate

© Copyright ask.programmershare.com.

Design by ask.programmershare.com