python - 可视化河内塔问题的可能方法

Question

我最近开始学习更多关于 Python 递归的知识，并很快陷入了河内塔问题。

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

有什么可能的方法呢？

Answer 1

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

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)

Answer 2

也许作为命令行字符串：

{"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)))

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

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