5
$\begingroup$

I want to know what is algorithm and time complexity of Hanoi tower with forbidden direct move from source to destination (it means you cannot move disk from source to destination directly and you instead of that should first move disk from source to middle and then from middle to destination) and other rules as normal problem?

I didn't find any article about it.

$\endgroup$
  • 1
    $\begingroup$ What means "forbidden direct move from source to destination"? $\endgroup$ – frafl May 19 '13 at 7:01
  • $\begingroup$ @frafl it means you cannot move disk from source to destination directly and you instead of that should first move disk from source to middle and then from middle to destination. did you know my mean? $\endgroup$ – Majid May 19 '13 at 7:08
  • $\begingroup$ It seems to me that it is almost the same problem, you just need to do twice much the work. First move all disks to middle rod then to destination. It would take 2*T moves, where T is moves reqired solve original problem. $T = 2^n - 1$, n - number of discs. $\endgroup$ – Bartosz Przybylski May 19 '13 at 11:58
  • $\begingroup$ @Bartek thank you but what means "you just need to do twice much the work"? $\endgroup$ – Majid May 20 '13 at 7:33
  • $\begingroup$ It means that you need to perform twice much moves as in original problem. Since you cannot move directy to destination rod you first need to move all discs to middle rod using T moves, and then to destination rod using another T moves. Overall you need to make 2*T moves, which means you need to do twice as much work as in original problem. $\endgroup$ – Bartosz Przybylski May 25 '13 at 8:00
2
+50
$\begingroup$

Notation
Let's denote least number of moves needed to move $n$ disks from column $i$ to column $j$ with $T_{ij}$. Let $A$ be the source and $C$ be the destination column.

Recurrence relations
We can say the followings about each $T$: \begin{equation} T_{AC}(n)=T_{AC}(n-1)+1+T_{CA}(n)+1+T_{AC}(n-1) \end{equation} To move $n$ disks from source to destination, we first have to move the top $n-1$ disks to column $C$ and then move the last one to Column $B$, Then return the $n-1$ disks to $A$ so as to free up destination column, then move the biggest disk to $C$ and once again move the $n-1$ disks to $C$. It's easy to see that this is the optimal set of operations. This equation can be written as: \begin{equation} T_{AC}(n)=2T_{AC}(n-1)+2+T_{CA}(n-1) \end{equation}

For other $T$s we have a different situation: \begin{equation} T_{CA}(n)=T_{CB}(n-1)+1+T_{BA}(n-1)\\ T_{CB}(n)=T_{CA}(n-1)+1+T_{AB}(n-1)\\ T_{BA}(n)=T_{BC}(n-1)+1+T_{CA}(n-1)\\ T_{AB}(n)=T_{AC}(n-1)+1+T_{CB}(n-1)\\ T_{BC}(n)=T_{BA}(n-1)+1+T_{AC}(n-1) \end{equation}

Solving the system of recurrence relations
Let's start with $T_{AB}$ or $T_{BC}$ . We already know: \begin{equation} T_{AB}(n)=T_{AC}(n-1)+1+T_{CB}(n-1) \end{equation} We try to rewrite $T_{CB}$'s equation by replacing $T_{AB}$ from the above equation. \begin{align} T_{CB}(n)&=T_{CA}(n-1)+1+(T_{AC}(n-2)+1+T_{CB}(n-2))\\ &=T_{CA}(n-1)+T_{AC}(n-2)+T_{CB}(n-2)+2 \end{align} \begin{equation} T_{CB}(n)-T_{CB}(n-2)=T_{CA}(n-1)+T_{AC}(n-2)+2 \end{equation}

By the same method we get: \begin{equation} T_{BA}(n)=T_{CA}(n-1)+T_{AC}(n-2)+T_{BA}(n-2)+2 \end{equation}

It can immediately be seen that $T_{BA}(n)=T_{CB}(n)$. Then we rewrite $T_{CA}$ as: \begin{equation} T_{CA}(n)=2T_{CB}(n-1)+1 \Rightarrow \end{equation} \begin{align} T_{CA}(n)-T_{CA}(n-2)&=2(T_{CB}(n-1)-T_{CB}(n-3))\\ &=2(T_{CA}(n-2)+T_{AC}(n-3)+2)\\ &=2T_{CA}(n-2)+2T_{AC}(n-3)+4 \end{align}

Now let's go back to the main relation, to $T_{AC}$: \begin{equation} T_{AC}(n)=2T_{AC}(n-1)+2+T_{AC}(n-1) \Rightarrow\\ \end{equation} \begin{align} &T_{AC}(n)-3T_{AC}(n-2)\\ =&2(T_{AC}(n-1)-3T_{AC}(n-3))+(T_{CA}(n-1)-3T_{CA}(n-3))=\\ =&2(T_{AC}(n-1)-3T_{AC}(n-3))+(2T_{AC}(n-4)+4)\\ =&2T_{AC}(n-1)-6T_{AC}(n-3)+2T_{AC}(n-4)+4 \Rightarrow \end{align} \begin{equation} T_{AC}(n)=2T_{AC}(n-1)+3T_{AC}(n-2)-6T_{AC}(n-3)+2T_{AC}(n-4)+4 \end{equation}

There! We have reduced the system of recurrence relations to a single relation, involving only the target series. Ok, the rest is easy from here on. I leave it as an exercise to the reader! $\ddot\smile$

$\endgroup$
  • $\begingroup$ What does it mean to mingle to two recursions? Why not write $T_{AC}(n)=3 T_{AC}(n-1)+2$ for the first one? $\endgroup$ – Anonymous Coward Nov 21 '13 at 3:12
  • $\begingroup$ I think you are referring to the equation in the end of the first paragraph in "Recurrence relations". It was just a typo. I fixed it. (thanks for noticing though). $\endgroup$ – Untitled Nov 21 '13 at 5:17

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.