Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

There is board in which there are $m\times m$ boxes each assigned an a non zero integer except one box which is marked as $0$ and is treated as vacant. Only the vertical and horizontal neighbors of vacant box can move towards it leaving their place as vacant. To solve this puzzle bob has to arrange the boxes in increasing order of their value with the vacant box(box marked as zero ) coming at the end(lower right corner of board).

What is the minimum number of moves of solve the puzzle?

For example in a $3\times3$ board with inputs:

9   8  5
2   0  4 
10 12 17

The minimum number of moves required is $12$

Is this a well known/studied puzzle/problem? I am not sure how to approach this one. Any ideas?

share|improve this question
add comment

1 Answer 1

up vote 0 down vote accepted

The $4 \times 4$ version is famous as the 15 puzzle. The Wikipedia article calls this the $8$ puzzle or $9$ puzzle.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.