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.
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?