# 理解迭代求解河内塔的机制

The following code implements the Towers of Hanoi iteratively:

``````def towers_of_hanoi(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:
- A disk can be moved if its the uppermost disk on a stack
- No disk may be placed on top of a smaller disk
- One of the towers could be empty, so we can only move to it and not from it
"""
if not len(giver):
giver.appendleft(taker.popleft())
move(taker, giver)

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

elif giver.size > taker.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

# only one disk can be moved at a time
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 - source stack
B - Auxiliary stack
C - destination stack
"""
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)
``````

If `n = 4`, we get the following output:

``````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!
``````

However, I do not quite understand the following sections in the function `hanoi`:

1. 当磁盘数量为偶数时，为什么要翻转辅助/辅助钉和目标钉？
``````if n % 2 == 0:
helper, dest = dest, helper
``````
1. Why do we `mod` 3 and how does that influence the moves between the source, destination and helper pegs?
``````if i % 3 == 1:
valid_moves(src, dest)

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

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