Hanoi tower with forbidden direct move from source to destination

Question

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.

Answer 1

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$