可视化汉诺塔问题的可能方法

Question

我最近开始在 Python 中学习更多关于递归的知识，很快就陷入了汉诺塔问题。

我在 Python 中已经有一个递归解决方案，它打印出解决问题我应该下的棋步，但我想将其形象化并看到棋子在移动。

可能的方法是什么？

Answer 1

可能是命令行字符串：

{"peg1": [0, 1, 2],
 "peg2": [0, 0, 3],
 "peg3": [0, 0, 0]}

如：

   |          |          |   
  -|-         |          |   
 --|--     ---|---       |   
=============================

这就是将列表翻译成这些挂图。

您可以通过以下方式联系到：

def peg_to_strings(peg_list, dct={0: "   |   ",
                                  1: "  -|-  ",
                                  2: " --|-- ",
                                  3: "---|---"}):
    return [dct[x] for x in peg_list] + ["======="]

def interleave(lists, lst):
    # interleave([1, 2, 3], 'a') => [1, 'a', 2, 'a', 3]
    res = [(l, lst) for l in lists]
    return [y for x in res for y in x][:-1]

def transpose(lists):
    # transpose([[1, 2, 3], ['a', 'b', 'c']]) => [[1, 'a'], [2, 'b'], [3, 'c']]
    return [[l[i] for l in lists] for i in range(len(lists[0]))]

def pegs_to_strings(pegs_dct, inbetween=["    ", "    ", "    ", "===="]):
    lists = [peg_to_strings(pegs_dct[f"peg{x}"]) for x in [1,2,3]]
    return [''.join(strings) for strings in transpose(interleave(lists, inbetween))]

pegs_dct = {"peg1": [0, 1, 2],
            "peg2": [0, 0, 3],
            "peg3": [0, 0, 0]}

print('\n'.join(pegs_to_strings(pegs_dct)))

#    |          |          |   
#   -|-         |          |   
#  --|--     ---|---       |   
# =============================

因此对于可视化步骤，您必须将钉子带入此字典形式。

Answer 2

如果您将钉子建模为列表列表，其中较大的圆盘位于较低的索引处，那么实现打印功能和移动功能（也可以打印）应该相对简单。然后，您可以将您的动作输入该功能。

def printHanoi(pegs):
    height = sum(map(len,pegs))
    for r in reversed(range(height)):
        for peg in pegs:
            disc = "-" * (0 if r>=len(peg) else peg[r])
            print(f"{disc:>{height}}|{disc:{height}}", end=" ")
        print()
    invalid = any(p[::-1]!=sorted(p) for p in pegs)
    print("="*(height*6+5),"INVALID"*invalid)        
    print()


def moveHanoi(pegs,fromPeg,toPeg):
    pegs[toPeg].append(pegs[fromPeg].pop(-1))
    printHanoi(pegs)

输出：

pegs = [[3,2,1],[],[]]
printHanoi(pegs)
moveHanoi(pegs,0,2)
moveHanoi(pegs,0,1)
moveHanoi(pegs,2,1)
moveHanoi(pegs,0,2)

  -|-      |       |   
 --|--     |       |   
---|---    |       |   
=======================

   |       |       |   
 --|--     |       |   
---|---    |      -|-  
=======================

   |       |       |   
   |       |       |   
---|---  --|--    -|-  
=======================

   |       |       |   
   |      -|-      |   
---|---  --|--     |   
=======================

   |       |       |   
   |      -|-      |   
   |     --|--  ---|---
=======================

这适用于任何塔高，如果您的算法进行了非法移动，它也会对其进行说明：

pegs = [[5,4,3,2,1],[],[]]
printHanoi(pegs)
moveHanoi(pegs,0,2)
moveHanoi(pegs,0,1)
moveHanoi(pegs,0,2)
    
    -|-          |           |      
   --|--         |           |      
  ---|---        |           |      
 ----|----       |           |      
-----|-----      |           |      
===================================

     |           |           |      
   --|--         |           |      
  ---|---        |           |      
 ----|----       |           |      
-----|-----      |          -|-     
===================================

     |           |           |      
     |           |           |      
  ---|---        |           |      
 ----|----       |           |      
-----|-----    --|--        -|-     
===================================

     |           |           |      
     |           |           |      
     |           |           |      
 ----|----       |        ---|---   
-----|-----    --|--        -|-     
=================================== INVALID

如果您将 Hanoi 求解器构建为生成器，您将能够在只需调用 moveHanoi() 函数的 for 循环中使用它：

def solveHanoi(count,fromPeg=0,toPeg=2,tempPeg=1):
    if not count: return
    yield from solveHanoi(count-1,fromPeg,tempPeg,toPeg)
    yield fromPeg,toPeg
    yield from solveHanoi(count-1,tempPeg,toPeg,fromPeg)
        
pegs = [[3,2,1],[],[]]
printHanoi(pegs)
for f,t in solveHanoi(3):
    moveHanoi(pegs,f,t)

可视化汉诺塔问题的可能方法

Possible approach to visualize the Tower of Hanoi problem

python

recursion

visualization

towers-of-hanoi

code-visualization