前情回顾

前面我们已经完成了对棋盘的建模，接下来是暴力求解程序的核心部分，即枚举算法。Python编程资料点击免费获取

算法实现

要想让程序不断地试错每一种走法，需要设计一种枚举算法。第一颗棋子落定后，第二步对应的几种走法又各自对应若干种第三步的走法，因此，固定第一颗棋子，则在这个棋盘上，所有走法构成了一棵树。第一颗棋子的位置有16个选择，考虑对称关系，可以略去重复项，只剩4个特异的起点。因此，整个游戏的所有走法可以用一个含4棵树的森林来表示。而枚举算法的目的则是试图在所有叶子结点中找到完成游戏的那几个结点。

接下来，我们让算法从根结点开始，逐步探索、完善这棵树。

基本操作

首先，我们需要一些基本操作。

为了表示棋盘状态（哪些格子为空，哪些格子有棋子），我们定义一个占用列表，为了方便起见，同时维护一个未占用列表。初试化两个列表如下：

NodesOccupied = []
NodesUnoccupied = list(range(15))
复制代码

获取棋子n在当前棋盘中的所有走法，输入为棋子序号n，该操作会遍历NodesUnoccupied，得到该棋子所有的走法，即下一步占用哪两个格子：

def getRoads(n):
    options_all = list(combinations(NodesUnoccupied, 2))
    options = []
    for option in options_all:
        if isSameRow(n, option[0], option[1]) is True\
                and ((n < option[0] and n < option[1]) or (n > option[0] and n > option[1])):
            options.append(option)
    return options
复制代码

执行某一种走法，输入为(n, n1, n2)，分别为棋子序号n、接下来要占用的两个位置n1和n2。该操作用于更新NodesOccupied和NodesUnoccupied，并记录该走法，用于最后程序输出。当然，这一步有可能是错误的，如果出现这种情况，后面会有别的操作来将其弹出列表。

def action(n, n1, n2):

    NodesOccupied += [n1, n2]
    NodesOccupied.remove(n)
    NodesUnoccupied.append(n)
    NodesUnoccupied.remove(n1)
    NodesUnoccupied.remove(n2)

    temp_unoccupied = NodesUnoccupied[:]
    solution.append([[n, n1, n2], temp_unoccupied])
复制代码

回退。如果程序发现不能再往下走了，即运行到叶子结点，而此时又没有达到完成游戏的条件，则说明这条路不正确，最起码在最后的若干步不正确。这时，需要回退到上一个做选择的位置。回退机制需要我们有一个栈来记录每一个做选择（有路可走）的地方，因此，我定义了一个safe_stack。而回退操作则依赖于这个安全状态栈来完成，回退时需要刷新NodesOccupied和NodesUnoccupied，并弹出action列表的最后一步，因为这不是正确的走法。

def get_back():

    NodesOccupied = safe_stack[-1][0][:]
    NodesUnoccupied = []
    for i in range(15):
        if i not in NodesOccupied:
            NodesUnoccupied.append(i)

    solution.pop()
复制代码

主函数

定义完基本操作后，我们开始实现主函数。

主函数的逻辑很简单，即依赖安全状态栈不断循环，直到棋盘中只剩一个空格时退出循环。

 

代码如下：

def main():

    # 一共有四棵树，简单起见直接分四次执行。
    startPoints = [0, 1, 3, 4]
    # for startPoint in startPoints:
    startPoint = startPoints[0]
    NodesOccupied.append(startPoint)
    NodesUnoccupied.remove(startPoint)

    isAction = 1

    while len(NodesUnoccupied) > 1:

        if isAction:
            temp_Occupied = NodesOccupied[:]
            safe_stack.append([temp_Occupied, []])
            for node in temp_Occupied:
                options = getRoads(node)
                for option in options:
                    safe_stack[-1][1].append([node] + list(option))

        if len(safe_stack[-1][1]):
            action(safe_stack[-1][1][0][0], safe_stack[-1][1][0][1], safe_stack[-1][1][0][2])
            isAction = 1
        else:
            if len(safe_stack) > 1:
                safe_stack.pop()
                safe_stack[-1][1].pop(0)
                get_back()
                isAction = 0
            else:
                print('Fail.\n')
                break

    print('Success.\n')
    for each in solution:
        print(f'remove {each[0][0]}, append {each[0][1:]}, NodesUnoccupied: {each[1]}')
复制代码

至此，暴力求解程序已经完成，它会将自己摸索出来的第一种解法打印出来：

Success.

remove 0, append [1, 3], NodesUnoccupied: [2, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 0]
remove 1, append [4, 8], NodesUnoccupied: [2, 5, 6, 7, 9, 10, 11, 12, 13, 14, 0, 1]
remove 3, append [6, 10], NodesUnoccupied: [2, 5, 7, 9, 11, 12, 13, 14, 0, 1, 3]
remove 4, append [7, 11], NodesUnoccupied: [2, 5, 9, 12, 13, 14, 0, 1, 3, 4]
remove 6, append [1, 3], NodesUnoccupied: [0, 2, 4, 5, 9, 12, 13, 14, 6]
remove 7, append [2, 4], NodesUnoccupied: [0, 5, 9, 12, 13, 14, 6, 7]
remove 8, append [6, 7], NodesUnoccupied: [0, 5, 9, 12, 13, 14, 8]
remove 11, append [12, 13], NodesUnoccupied: [0, 5, 9, 14, 8, 11]
remove 2, append [5, 9], NodesUnoccupied: [0, 14, 8, 11, 2]
remove 5, append [0, 2], NodesUnoccupied: [14, 8, 11, 5]
remove 12, append [8, 5], NodesUnoccupied: [14, 11, 12]
remove 13, append [11, 12], NodesUnoccupied: [14, 13]
remove 12, append [14, 13], NodesUnoccupied: [12]
复制代码

remove 0, append [1, 3]就表示移动0，占用1和3，NodesUnoccupied即当前还有哪些格子没有被占。按照程序给出的攻略，最终只剩一个空格，游戏完成。

 

项目代码：Yuezih-Playground/Hopscotch (github.com)