Search code examples
algorithmmathtowers-of-hanoi

Alternate plain English algorithm for Towers of Hanoi

There are four plain English algorithms for the Towers of Hanoi Puzzle available on Wikipedia, but when I was first solving the puzzle, I came up with an algorithm that is different from any of the solutions I have seen.

Wikipedia algorithms:

  1. Iterative solution
  2. Simpler statement of iterative solution
  3. Equivalent iterative solution
  4. Recursive solution

Of course the results of the algorithms are the same, and they are really just different ways of thinking about the same thing, but I am talking about plain English ways of describing the process.

My process goes like this:

  1. Never move same tile twice in a row(obviously)
  2. Prioritize moving right
  3. When moving right, move to the closest pole that can be legally moved to.
  4. When moving left, move to the farthest pole that can be legally moved to.

..

Towers of hanoi

These rules differ from other descriptions of the algorithm in that:

  • The initial stack can be placed on any of the 3 pillars and still work without any adjustment to the rules needed.(Unlike solutions 2 and 3 and 4)

  • You don't have to number the disks(Unlike solutions 1 and 3 and 4)

I have tested this programmatically, and it always solved the puzzle in (2^n)-1 moves where n is the number of rings.

It seems to me that my description really is different from the other plain English descriptions I have found. Has any one seen this description before? If so, please show reference.

Solution

  • This solution is a unidirectional version of the first iterative solution.

    The difference between the unidirectional solution and the mono-directional version is the unidirectional solution doesn't specify an end position.

    A simple solution for the toy puzzle: Alternate moves between the smallest piece and a non-smallest piece. When moving the smallest piece, always move it to the next position in the same direction (to the right if the starting number of pieces is even, to the left if the starting number of pieces is odd). If there is no tower position in the chosen direction, move the piece to the opposite end, but then continue to move in the correct direction. For example, if you started with three pieces, you would move the smallest piece to the opposite end, then continue in the left direction after that. When the turn is to move the non-smallest piece, there is only one legal move. Doing this will complete the puzzle in the fewest number of moves.

    This description of the mono-directional version can be changed to be unidirectional if direction choices of direction are replaced with the rules from the unidirectional solution revolving around prioritizing moving right.