1
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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