# In Towers of Hanoi (with 3 sticks and n disks without backtracking), do all legal sequences of moves reach the solution?

Updated Question : How to show that in TH we never reach a state where there are no paths to the solution? ( without reversing moves, as if reversing is allowed this becomes trivial )

Edit : Thanks to Stéphane Gimenez for pointing out the distinction between “A deadlock would never occur” and “The problem always has a solution”, made it possible for me to state the question in a form that was the original intention.

Stéphane Gimenez:

Defining deadlock as a reachable position where no more moves are available (or alternatively as a position from which the goal cannot be reached anymore), it's obvious that deadlocks cannot occur in the TH game: every step along the reverse path (of a path containing valid moves) is a valid move.

Original Question :

In Towers of Hanoi problem there is an implicit assumption that one can keep moving disks, this is trivially true for 1 or 2 disks but as obvious as it looks one can keep going with as many disks? In other words TH with 3 sticks and n disks always has a solution?

The N queens problem is easyly shown will not have a solution for n>m , where m is size of board (using Pigeon Hole ), but also it does not have a soltion for n=m=2. But how does one show that if for some k , n=m=k has a solution then it will also imply for k+1 there is a solution?

-
Assuming that you start from the usual configuration, there is an algorithm that yields a solution. – Alexei Averchenko Oct 2 '11 at 23:25
Not only is there an algorithm for the Towers of Hanoi, but it is described very nicely in an answer to this question. The N-Queens problem also does not have a solution for $n=m=3$, so the first step of your induciton must begin at 4 queens on a four by four board... – user12998 Oct 2 '11 at 23:27
I was confused by the title because “A deadlock would never occur” and “The problem always has a solution” are different statements to me… However, defining deadlock as a reachable position where no more moves are available (or alternatively as a position from which the goal cannot be reached anymore), it's obvious that deadlocks cannot occur in the TH game: every step along the reverse path (of a path containing valid moves) is a valid move. – Stéphane Gimenez Oct 2 '11 at 23:56
@Stéphane Gimenez : Updated the question, thanks – Arjang Oct 3 '11 at 2:09

## 2 Answers

There cannot be deadlock in the Towers of Hanoi, as you almost always have three moves: you can move the smallest disk to one of the other two pegs, and unless all the disks are on the same peg you can always move another disk.

There are many ways of proving that any Towers of Hanoi position is solvable. One I like is to show the correspondence between the positions and the points of a Sierpinski triangle such as 1, 2 or 3. Since a Sierpinski triangle is connected, it is possible to move from any given legal position to any other, and so any Towers of Hanoi position is solvable.

-
Sierpinski triangle Connection was totally unexpected. +1 – Arjang Oct 3 '11 at 4:16

Well, one can give an exact algorithm to solve it. But I would recommend thinking of it as a recursive problem. Say we look at the 3 disk case. Well, that's really a 2 disk case on top of a third disk. So suppose we move those top 2 disks to another rod. Then we move the forgotted third to the desired end rod, and treat the 2 disks as another TH puzzle to move them on top of the third.

In this recursive fashion, we can see that we can always guarantee a procedure inductively. If you pay close attention, you can even give the number of moves necessary.

-