# Find extra work done by Bob

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

• Move-type #$2$ sounds like a subset of move-type #$1$ (in other words, it is redundant). Can you please clarify this? – barak manos Jul 25 '14 at 17:57
• @barakmanos subset in what sense ? – user3840069 Jul 25 '14 at 17:59
• @BarryCipra Yeah right. – user3840069 Jul 25 '14 at 18:03
• @BarryCipra Yeah i done that..thanx for pointing it out – user3840069 Jul 25 '14 at 18:10
• @BarryCipra Ohh sorry ..it was typing mistake.Actually it was N*N and not N – user3840069 Jul 25 '14 at 18:15

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.
• The initial configuration does matter. If you start with everything where it belongs, Bob does no work either way, so no extra work in Type 2. There isn't a simple answer. For Type 1 moves, there is a clear maximum, which I gave. Most arrangements will be close to that as the average number of tiles that start out in the correct location is $1$. There is also a maximum for Type 2, but it isn't as easy to calculate. For a given initial condition it is easy to calculate the number of moves and I sketched the algorithm. – Ross Millikan Jul 25 '14 at 19:01