河内塔 - 用 Python 解决中途算法

河内塔有可能中途解决吗？我已经做了广泛的研究来寻找可以半途解决用户配置的代码，但我还没有找到。这是一项作业，我需要代码从用户停止解决的地方接管并继续为用户解决它，而不将谜题重置为一。

我知道有现成的递归算法，但这不是我正在寻找的。 我正在寻找可以从用户已经解决的地方接管，然后从那里继续解决的算法。 有任何想法吗？

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

以下是到目前为止我的代码（我已排除 stack.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

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

它只是需要更通用一点。

编写一个递归过程moveDisks（最大大小，targetPeg）移动所有大小 maxSize到挂钩目标挂钩， 像这样：

1. 找到最大的磁盘m这样m.size and m is not on 目标挂钩。如果没有这样的磁盘，则返回，因为所有大小maxSize已经在正确的地方了。

2. Let 来源挂钩成为钉子m目前是，并且让otherPeg成为那个不是的钉子来源挂钩 or 目标挂钩.

3. Call moveDisks(m.size-1, otherPeg)递归地将较小的磁盘移开。

4. Move m from 来源挂钩 to 目标挂钩.

5. Call 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;

Test:

> moveDisks([2,1,0,2], 0, 2)
Move  3  from  2  to  0
Move  1  from  1  to  2
Move  3  from  0  to  1
Move  2  from  0  to  2
Move  3  from  1  to  2