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?
Best Answer
The $4 \times 4$ version is famous as the 15 puzzle. The Wikipedia article calls this the $8$ puzzle or $9$ puzzle.