基于Python的汉诺塔求解中途算法

Question

能不能把河内塔半路解决？我做了大量的研究来寻找能够解决用户配置问题的代码，但是我还没有找到一个。这是一个任务，我需要代码接管从用户已经停止求解的地方，并继续为用户解决它，而不重置为方块一。在

我知道有递归算法在那里随时可用，但这不是我要寻找的。 我正在寻找算法，它可以接管用户解决问题的地方，然后继续从那里解决问题。 有什么想法吗？在

到目前为止，我已经提出了一种算法，它将优化的算法（通过递归实现）存储到一个数组中，然后检查用户的输入是否等于数组中找到的任何一个，然后从那里继续求解。但是，问题在于优化算法数组中找不到用户的配置。在

以下是我目前为止的代码（我排除了堆栈.py代码）：

def solveHalfway(n, start, end, middle, count):
    gameInstance.stackA = [3,2]
    gameInstance.stackB = []
    gameInstance.stackC = [1]
    loopCounter = 0 # initialise loopCounter as 0
    moveCounter = 0 # initialise the move index the user is stuck at
    indicator = 0 # to indicate whether the user's config equals the solution's config
    while loopCounter < arrayOfStacks.size(): # while loopCounter size has not reached the end of arrayOfStacks
        if loopCounter != 0 and loopCounter % 3 == 0:  # if 3 stacks have been dequeued
            moveCounter += 1
            if gameInstance.getUserConfig() == tempStack.data:  #check whether user's config is equal to the solution's config
                indicator += 1
                print "User is stuck at move: ", moveCounter  #this will be the current move the user is at
                while arrayOfStacks.size() != 0: # while not the end of arrayOfStacks
                    correctMovesStack.push(arrayOfStacks.dequeue())  # add the moves to correctMovesStack
                    if correctMovesStack.size() == 3: # if 3 stacks have been dequeued
                        print "Step:", moveCounter , correctMovesStack.data # display the step number plus the correct move to take
                        moveCounter+=1 # increase move by 1
                        while correctMovesStack.size() != 0: # if correct moves stack isn't empty
                            correctMovesStack.pop() # empty the stack
                return
            else:
                while tempStack.size() != 0: # check if tempStack is empty
                    tempStack.pop()  # empty tempStack so that it can be used for the next loop
            tempStack.push(arrayOfStacks.dequeue()) #dequeue from arrayOfStacks for a total of 3 times and push it to tempStack
        else:
            tempStack.push(arrayOfStacks.dequeue()) #dequeue from arrayOfStacks for a total of 3 times and push it to tempStack
        loopCounter +=1 # increase loop counter by 1
    if indicator == 0:
        moveWith3Towers(noOfDisks, stackA, stackC, stackB, count)
    print indicator

Answer 1

要从任意位置求解河内塔，可以使用类似于从标准起始位置开始工作的标准解的递归过程。在

只是要更一般一点。在

编写一个递归过程moveDisks（maxSize，targetPeg），将所有大小为<；=maxSize的磁盘移动到pegtargetPeg，如下所示：

1. 找到最大的圆盘m使m.size<；=maxSize且m在targetPeg上而不是。如果没有这样的磁盘，则返回，因为所有大小为<；=maxSize的磁盘都已在正确的位置。

2. 设sourcePeg为当前m的peg，其他peg为非sourcePeg或targetPeg的peg。

3. 递归地调用moveDisks（m.size-1，otherPeg）将较小的磁盘放在一边。

4. 将m从sourcePeg移动到targetPeg。

5. 递归调用moveDisks（m.size-1，targetPeg）将较小的磁盘放在属于它们的位置。

在python中，我会这样写。请注意，我对游戏状态使用了一种不同的表示法，这种表示法更适用于此算法，并且不允许任何非法位置：

#
# Solve Towers of Hanoi from arbitrary position
#
# diskPostions   the current peg for each disk (0, 1, or 2) in decreasing
#                 order of size.  This will be modified
# largestToMove   move this one and all smaller disks
# targetPeg   target peg for disks to move
#
def moveDisks(diskPositions, largestToMove, targetPeg):
    for badDisk in range(largestToMove, len(diskPositions)):

        currentPeg = diskPositions[badDisk]         
        if currentPeg != targetPeg:
            #found the largest disk on the wrong peg

            #sum of the peg numbers is 3, so to find the other one...
            otherPeg = 3 - targetPeg - currentPeg

            #before we can move badDisk, we have get the smaller ones out of the way
            moveDisks(diskPositions, badDisk+1, otherPeg)

            print "Move ", badDisk, " from ", currentPeg, " to ", targetPeg
            diskPositions[badDisk]=targetPeg

            #now we can put the smaller ones in the right place
            moveDisks(diskPositions, badDisk+1, targetPeg)

            break;

测试：

^{pr2}$