Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question
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|cite|improve this answer

Your Answer


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.