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?

 A: 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.       
A: 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.
