0
$\begingroup$

So I started practicing some algorithms and programming before university starts and I ran into this problem:

Given a 3x3 matrix containing the numbers from 0 to 8, find the minimum number of steps required to sort the matrix in the following format:

1 2 3
4 5 6
7 8 0

In one move it is only allowed to pick a cell that is adjacent to the cell which contains the 0 and swap those two cells.

Now, I am really stuck with this one and have no idea how to begin. Any tips and ideas to get me started are appreciated.

Improve this question
$\endgroup$
3
  • $\begingroup$ I'm not sure what you mean. The input might be in the correct format already, so the answer to the question you've asked is "zero". $\endgroup$
    – David Richerby
    Commented Sep 7, 2015 at 17:38
  • $\begingroup$ the question is nontrivial if 0-9 designations are taken as the order of the elements & not the elements themselves. if that is the case the question should be revised to make that clear. $\endgroup$
    – vzn
    Commented Sep 7, 2015 at 22:45
  • $\begingroup$ eg there is ongoing research into minimal size sorting networks & that area may contain the answer published somewhere $\endgroup$
    – vzn
    Commented Sep 7, 2015 at 23:02

1 Answer 1

Reset to default
3
$\begingroup$

Since you are looking for minimal number of moves without any tricks, there is old good pattern for small exact problems.

0) treat your starting matrix as root.
1) enumerate possible moves, and perform them (copy matrix, save steps etc.).
2) keep performing step one for every resulting matrix until you find them ordered. This is minimal number of moves.
1+) optimization possible is to ignore the same matrices that you already have, block sliding ply in direction it came from.

Improve this answer
$\endgroup$
1
  • $\begingroup$ There is also post connected to this question, it is not strict duplicate, but you shoud do your research and check already existing questions: heuristic $\endgroup$
    – Evil
    Commented Sep 7, 2015 at 17:13

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.