Find extra work done by Bob

Question

Alice has challenegd Bob game of N puzzle.N puzzle is played on N*N grid with each cell containing distinct numbered tile from 1 to N*N-1 Except one which is empty cell and represented as 0.

Move Type 1 : Bob can pull out any tile he want and put it into any cell of his choice (not necessarily blank)

Move Type 2 : He can choose any tile and move it to any adjacent cell in 4 direcions regardless of weather cell is empty or not.

Goal to be achieved : Goal is to reach configuration where first row contains tiles 0,1,2..N-1 second row contains N,N + 1,N + 2..2*N-1 and last row contains N*(N-1)...N*N-1

Now we need to help Bob in finding how much extra work he will have to do if he chooses Move Type 2 which means if given position can be solved optimally using Move Type 1 in X moves and using Move Type 2 in Y moves then we need to find (Y-X) extra work.

Example : Let M=N*N=4 and initial configuration be

0 2 
3 1

Here answer will be 1

Explanation : Using Type 1 move Bob can put out tiles 1,2,3 and put them in reuired order this takes him X=3 moves

Using Type 2 move he can move tile 1 UP,tile 2 DOWN and then LEFT and then tile 3 RIGHT to reach final goal.So Y=4

Hence Y-X=4-3=1

Answer 1

Each tile moves independently. For Type 1 moves, Bob has to move each tile that doesn't start out in the right place once. At a maximum he will make $N^2-1$ moves. For Type 2 moves, each tile has to move the Manhattan distance that it starts from its final spot number of times. Each tile moves from $0$ to $2N-2$ times. To get the average, note we can consider the two axes independent. In one axis and the continuous approximation, the average distance is the average distance between points in a unit square $\frac 1{15}(2+\sqrt 2 +5 \sinh^{-1}1 \approx 0.521405433$ times the size of the square $N-1$ so on average Bob will move $2(N-1)(\frac 1{15}(2+\sqrt 2 +5 \sinh^{-1}1)$ moves.