# 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