1
$\begingroup$

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

$\endgroup$
5
  • $\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, 2014 at 17:57
  • $\begingroup$ @barakmanos subset in what sense ? $\endgroup$
    – user3840069
    Jul 25, 2014 at 17:59
  • $\begingroup$ @BarryCipra Yeah right. $\endgroup$
    – user3840069
    Jul 25, 2014 at 18:03
  • $\begingroup$ @BarryCipra Yeah i done that..thanx for pointing it out $\endgroup$
    – user3840069
    Jul 25, 2014 at 18:10
  • $\begingroup$ @BarryCipra Ohh sorry ..it was typing mistake.Actually it was N*N and not N $\endgroup$
    – user3840069
    Jul 25, 2014 at 18:15

1 Answer 1

Reset to default
0
$\begingroup$

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.

$\endgroup$
2
  • $\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, 2014 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, 2014 at 19:01

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .