Towers of Hanoi: Model recursive solution to a non-recursive solution

Question

I am having a go at recursive and iterative approaches to problem solving using the Towers of Hanoi puzzle.

f refers to from/source, helper - auxiliary/intermediate position, t - target/destination

Here is the recursive implementation where we just print the moves:

def towers_of_hanoi_v1(n):
    """
    Recursive approach
    """

    def move(f, t):
        print(f"Move disc from {f} to {t}!")

    def hanoi(n, f, helper, t):
        if n:
            hanoi(n - 1, f, t, helper)
            move(f, t)
            hanoi(n - 1, helper, f, t)

    return hanoi(n, "A", "B", "C")

My attempt at converting the above to an iterative solution is as follows:

class Disc:
    def __init__(self, size):
        self.size = size

def towers_of_hanoi_v2(n):
    """
    Iterative approach
    """

    def mapper(queue):
        """
        util to map queue to its respective label
        """
        if queue is A:
            label = "A"
        elif queue is B:
            label = "B"
        elif queue is C:
            label = "C"
        return label

    def move(f, t):
        """
        utility function to print moves
        """
        print(f"Move disc from {mapper(f)} to {mapper(t)}!")

    def valid_moves(giver, taker):
        """
        utility function to figure out next legal move:
        - One of the towers could be empty, so we can only move to it and not from it
        - Tower x can have a larger disk than tower y.
        """
        if not len(giver):
            giver.appendleft(taker.popleft())
            move(taker, giver)

        elif not len(taker):
            taker.appendleft(giver.popleft())
            move(giver, taker)

        elif giver[0].size > taker[0].size:
            giver.appendleft(taker.popleft())
            move(taker, giver)

        else:
            taker.appendleft(giver.popleft())
            move(giver, taker)

    def hanoi(n, src, helper, dest):
        if n % 2 == 0:
            helper, dest = dest, helper

        moves = pow(2, n) - 1

        for i in range(1, moves + 1):
            if i % 3 == 1:
                valid_moves(src, dest)

            elif i % 3 == 2:
                valid_moves(src, helper)

            elif i % 3 == 0:
                valid_moves(helper, dest)

    """
    Initialise towers as stacks. We use stacks so that we can always look at
    the current top disk and compare the sizes between top disks of two towers
    """
    A = collections.deque(maxlen=n)
    B = collections.deque(maxlen=n)
    C = collections.deque(maxlen=n)

    """
    Populate initial tower while assigning sizes
    sizes will be crucial as we can not move a large disk onto a small disk
    """
    for i in reversed(range(n)):
        A.append(Disc(n - i))

    return hanoi(n, A, B, C)

Incorporated this feedback. The iterative approach needed an auxiliary data structure, I used a stack:

n = 4    

Recursive approach:
Move disc from A to B!
Move disc from A to C!
Move disc from B to C!
Move disc from A to B!
Move disc from C to A!
Move disc from C to B!
Move disc from A to B!
Move disc from A to C!
Move disc from B to C!
Move disc from B to A!
Move disc from C to A!
Move disc from B to C!
Move disc from A to B!
Move disc from A to C!
Move disc from B to C!
None

Iterative approach:
Move disc from A to B!
Move disc from A to C!
Move disc from B to C!
Move disc from A to B!
Move disc from C to A!
Move disc from C to B!
Move disc from A to B!
Move disc from A to C!
Move disc from B to C!
Move disc from B to A!
Move disc from C to A!
Move disc from B to C!
Move disc from A to B!
Move disc from A to C!
Move disc from B to C!
None

Do you have a cleaner approach?

did you check the answer? It seems you're asking the same question again and got closed? — Zabir Al Nazi
Yes, your approach helped. However, I do not understand why we swap B and C stacks with even number of disks? and What is the reasoning behind i%3 in the main algorithm? See this, stackoverflow.com/a/48915752/7695722, answer — Brayoni

Zabir Al Nazi Zabir Al Nazi · Accepted Answer · 2020-05-16T07:48:36

If you look into your solution, it's almost correct but it doesn't consider the conditions to validate a legal move.

For example, in n=2, there will be a move between B and C. But you've to decide the correct swap direction.

There can be many scenarios,

One of the towers could be empty, so we can only move to it and not from it.
Tower x can have a larger disk than tower y.

So, you should implement it with a list/stack where you can always look into the current top disk and compare the sizes between top disks of two towers. Then, before each movement, you'll have to decide the correct direction of movement based on the rules of the game.

Towers of Hanoi: Model recursive solution to a non-recursive solution

1 Answers