试探算法思想

试探算法也叫回溯法，它选择先暂时放弃关于问题规模大小的限制，并将问题的候选解按某种顺序逐一枚举和检验。当发现当前候选解不可能是正确的解时，就选择下一个候选解。如果当前候选解除不满足规模要求外，能够满足所有其他要求，则继续扩大当前候选解的规模，并继续试探。如果当前候选解满足包括问题规模在内的所有要求，该候选解就是问题的一个解。在试探算法中，放弃当前候选解，并继续寻找下一个候选解的过程称为回溯。扩大当前候选解的规模，并继续试探的过程称为向前试探。

基本步骤

1. 针对所给问题，定义问题的解空间。
2. 确定易于搜索的解空间结构。
3. 以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。

“八皇后”问题

问题描述：在 8x8 的国际象棋上摆放 8 个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一条斜线上，问有多少种摆法。

考虑到 8 个皇后不同行，每一行的皇后可以放置于第 0~7 列，可以认为每一行的皇后有 8 种状态。那么，我们只要套用子集树模板，从第 0 行开始，自上而下，对每一行的皇后，遍历它的 8 个状态即可。

n = 8
x = []  # 遍历过程中的一组解
X = []  # 用来保存所有解

def conflict(k):
    global x

    for i in range(k):
        if x[i] == x[k] or abs(x[i] - x[k]) == abs(i - k):  # 判断不在同一列，且不在同一条斜线上
            return True
    return False

def queens(k):  # 摆放第 k 行
    global n, x, X

    if k >= n:
        X.append(x[:])  # 得到一组解
    else:
        for i in range(n):
            x.append(i)  # 向前试探
            if not conflict(k):  # 剪枝
                queens(k + 1)
            x.pop()  # 回溯

def show(x):
    global n

    for i in range(n):
        print('. '*(x[i]) + 'X ' + '. ' * (n - x[i] - 1))

queens(0)
print(len(X))  # 输出解的数量
print(X[-1], '\n')  # 输出最后一条解
show(X[-1])

# 输出结果
92
[7, 3, 0, 2, 5, 1, 6, 4] 

. . . . . . . X 
. . . X . . . . 
X . . . . . . . 
. . X . . . . . 
. . . . . X . . 
. X . . . . . . 
. . . . . . X . 
. . . . X . . . 

“迷宫问题”

问题描述：给定一个迷宫，入口已知。迷宫内 0 表示可走，1 表示墙。有 8 个方向可以进行移动，即上、下、左、右、上左、上右、下左、下右。要求给出到出口的路径，出口表示为迷宫边界为 0 的格子。

maze = [[1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
        [0, 0, 1, 0, 1, 1, 1, 1, 0, 1],
        [1, 1, 0, 1, 0, 1, 1, 0, 1, 1],
        [1, 0, 1, 1, 1, 0, 0, 1, 1, 1],
        [1, 1, 1, 0, 0, 1, 1, 0, 1, 1],
        [1, 1, 0, 1, 1, 1, 1, 1, 0, 1],
        [1, 0, 1, 0, 0, 1, 1, 1, 1, 0],
        [1, 1, 1, 1, 1, 0, 1, 1, 1, 1]]

m, n = 8, 10  # 8行10列
entry = (1, 0)  # 迷宫入口
path = [entry]  # 一组解
paths = []  # 保存所有解

# 可以移动的方向
directions = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]

def conflict(nx, ny):
    global m, n, maze

    if 0<= nx < m and 0 <= ny < n and maze[nx][ny] == 0:
        return False

    return True

def walk(x, y):
    global entry, m, n, maze, path, paths, directions

    if (x, y) != entry and (x % (m - 1) == 0 or y % (n - 1) == 0):  # 找到出口
        paths.append(path[:])  # 得到一组解
    else:
        for d in directions:
            nx, ny = x + d[0], y + d[1]
            path.append((nx, ny))  # 向前试探
            if not conflict(nx, ny):  # 剪枝
                maze[nx][ny] = 2
                walk(nx, ny)
                maze[nx][ny] = 0
            path.pop()  # 回溯

def show(path):
    global maze

    import pprint, copy

    maze2 = copy.deepcopy(maze)

    for p in path:
        maze2[p[0]][p[1]] = 2

    pprint.pprint(maze)
    print()
    pprint.pprint(maze2)

walk(*entry)
print(paths[-1], '\n')
show(paths[-1])

# 输出结果
[(1, 0), (1, 1), (2, 2), (1, 3), (2, 4), (3, 5), (4, 4), (4, 3), (5, 2), (6, 3), (6, 4), (7, 5)] 

[[1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
 [0, 0, 1, 0, 1, 1, 1, 1, 0, 1],
 [1, 1, 0, 1, 0, 1, 1, 0, 1, 1],
 [1, 0, 1, 1, 1, 0, 0, 1, 1, 1],
 [1, 1, 1, 0, 0, 1, 1, 0, 1, 1],
 [1, 1, 0, 1, 1, 1, 1, 1, 0, 1],
 [1, 0, 1, 0, 0, 1, 1, 1, 1, 0],
 [1, 1, 1, 1, 1, 0, 1, 1, 1, 1]]

[[1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
 [2, 2, 1, 2, 1, 1, 1, 1, 0, 1],
 [1, 1, 2, 1, 2, 1, 1, 0, 1, 1],
 [1, 0, 1, 1, 1, 2, 0, 1, 1, 1],
 [1, 1, 1, 2, 2, 1, 1, 0, 1, 1],
 [1, 1, 2, 1, 1, 1, 1, 1, 0, 1],
 [1, 0, 1, 2, 2, 1, 1, 1, 1, 0],
 [1, 1, 1, 1, 1, 2, 1, 1, 1, 1]]