solution to standard puzzle

Question

there is board in which there are m*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 we have 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).But like all other engineers we are very lazy and wants to solve it in minimum number of steps.

So what approach should we follow except for backtracking.

m is of order 500.. ie 500x500 board.

Answer 1

You can find the goal state by simply sorting the array. Let say you goal state is g then a simple but inefficient algorithm to solve the puzzle would be:

void solve()
{
    if(current_state == g)
        return;

    foreach(choice c in shifting_choices)
    {
      // shift neighbour
      apply choice;
      solve();
      undo choice;
    }
}

In above algorithm choices are basically moving the blocks which are surrounded by the zeroth block.

To improve the algorithm you can use A* (best first). In order to find best choice you can use Manhattan Distance. It is basically steps required to reach one block to another within puzzle. Consider below:

6 2 1
5 0 3
4 7 8

In above situation, you could move 2, 5, 3, 7 but to find best move consider the goal state:

8 7 6
5 4 3
2 1 0

When you move a block to zeroth block you are changing position of two blocks. Calculate sum of Manhattan Distance of these two blocks from their position within goal state. The choice within least sum will be most preferable:

Moving 2: 2 + 3 = 5

Moving 3: 1 + 1 = 2

Moving 7: 1 + 1 = 2

Moving 5: 1 + 2 = 3

You can break tie between 3 and 7 by checking their previous positions, 3 was at right place therefore 7 makes the locally most optimal choice.