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

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

  • $\begingroup$ Actually its not what is actually required.I need to find extra moves not an average moves and why the initial configuration doesnt matter here $\endgroup$ – user3840069 Jul 25 '14 at 18:22
  • $\begingroup$ 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. $\endgroup$ – Ross Millikan Jul 25 '14 at 19:01

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.