使用栈解决简单迷宫

用二维列表模拟迷宫，1代表墙，0代表当前路是可以通过的
回溯法的核心是状态的转换，当当前状态不能进入下一状态，我们就回溯到之前能进入下一状态的某状态结点，我们用栈的append和pop去模拟这一过程

# 起始位置为(1, 1)  终点位置为(8, 8)
maze = [
    [1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
    [1, 0, 0, 1, 0, 0, 0, 1, 0, 1],
    [1, 0, 0, 1, 0, 0, 0, 1, 0, 1],
    [1, 0, 0, 0, 0, 1, 1, 0, 0, 1],
    [1, 0, 1, 1, 1, 0, 0, 0, 0, 1],
    [1, 0, 0, 0, 1, 0, 0, 0, 0, 1],
    [1, 0, 1, 0, 0, 0, 1, 0, 0, 1],
    [1, 0, 1, 1, 1, 0, 1, 1, 0, 1],
    [1, 1, 0, 0, 0, 0, 0, 0, 0, 1],
    [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
]

首先我们定义一个函数，函数的参数分别为起始位置和终点位置

def path(x1, y1, x2, y2):
    pass
path(1, 1, 8, 8)

我们定义当前状态位置向四个方向转移的函数, 用python的λ函数来实习

directions = [
    lambda x, y: (x - 1, y),  # 上
    lambda x, y: (x + 1, y),  # 下
    lambda x, y: (x, y - 1),  # 左
    lambda x, y: (x, y + 1),  # 右
]

我们写一个最简易的框架, 定义一个栈 把初始位置的元组放入栈，当栈不为空时候，不停寻找下一状态,当栈为空时，说明当前迷宫是死路，我们设置终止状态

def path(x1, y1, x2, y2):
    stack = []
    stack.append((x1, y1))
    while len(stack) > 0:
        # 当前状态
        cur_node = stack[-1]
        # 终止状态
        if cur_node[0] == x2 and cur_node[1] == y2:
            return True
            pass
    # 当栈为空时 说明为死路 走不到终点
    else:
        return False

接下来我们定义下一状态next_node通过四个方向的函数不断的判断是否能通过 如果四个方向皆不能满足条件则利用stack的pop操作回溯到之前的某一能使条件满足的状态， 为防止环路的出现，每次访问过的路径都设置为已访问状态。

 for direction in directions:
            # 下一状态
            next_node = direction(cur_node[0], cur_node[1])
            if maze[next_node[0]][next_node[1]] == 0:
                stack.append(next_node)
                maze[next_node[0]][next_node[1]] = 2  # 把访问过的路径置为已访问
                break     # 每成功一次就立刻进入下一次状态的寻找
        # 如果四个方向皆不成立 回溯到之前的状态 直到有条件满足当前状态
        else:
            # 利用栈的pop操作进行回溯
            stack.pop()
            maze[next_node[0]][next_node[1]] = 2

最终的代码实现如下, 当满足终止条件时，我们遍历这个栈获得详细的路径。

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

directions = [
    lambda x, y: (x - 1, y),  # 上
    lambda x, y: (x + 1, y),  # 下
    lambda x, y: (x, y - 1),  # 左
    lambda x, y: (x, y + 1),  # 右
]


def path(x1, y1, x2, y2):
    stack = []
    stack.append((x1, y1))
    while len(stack) > 0:
        # 当前状态
        cur_node = stack[-1]
        if cur_node[0] == x2 and cur_node[1] == y2:
            for pat in stack:
                print(pat)
            return True
        print(stack)
        for direction in directions:
            # 下一状态
            next_node = direction(cur_node[0], cur_node[1])
            if maze[next_node[0]][next_node[1]] == 0:
                stack.append(next_node)
                maze[next_node[0]][next_node[1]] = 2  # 把访问过的路径置为已访问
                break     # 每成功一次就立刻进入下一次状态的寻找
        # 如果四个方向皆不成立 回溯到之前的状态 直到有条件满足当前状态
        else:
            # 利用栈的pop操作进行回溯
            stack.pop()
            maze[next_node[0]][next_node[1]] = 2
    # 当栈为空时 说明为死路 走不到终点
    else:
        return False
print(path(1, 1, 8, 8))

某一可达到终点的路径

(1, 1)
(2, 1)
(1, 1)
(1, 2)
(2, 2)
(3, 2)
(3, 1)
(4, 1)
(5, 1)
(5, 2)
(5, 3)
(6, 3)
(6, 4)
(6, 5)
(5, 5)
(4, 5)
(4, 6)
(5, 6)
(5, 7)
(4, 7)
(3, 7)
(3, 8)
(4, 8)
(5, 8)
(6, 8)
(7, 8)
(8, 8)

可以通过打印栈的增长和减小过程来感受不停寻找下一状态和回溯的过程

print(stack)
[(1, 1)]
[(1, 1), (2, 1)]
[(1, 1), (2, 1), (1, 1)]
[(1, 1), (2, 1), (1, 1), (1, 2)]
[(1, 1), (2, 1), (1, 1), (1, 2), (2, 2)]
[(1, 1), (2, 1), (1, 1), (1, 2), (2, 2), (3, 2)]
[(1, 1), (2, 1), (1, 1), (1, 2), (2, 2), (3, 2), (3, 1)]
[(1, 1), (2, 1), (1, 1), (1, 2), (2, 2), (3, 2), (3, 1), (4, 1)]
[(1, 1), (2, 1), (1, 1), (1, 2), (2, 2), (3, 2), (3, 1), (4, 1), (5, 1)]
[(1, 1), (2, 1), (1, 1), (1, 2), (2, 2), (3, 2), (3, 1), (4, 1), (5, 1), (6, 1)]
[(1, 1), (2, 1), (1, 1), (1, 2), (2, 2), (3, 2), (3, 1), (4, 1), (5, 1), (6, 1), (7, 1)]
[(1, 1), (2, 1), (1, 1), (1, 2), (2, 2), (3, 2), (3, 1), (4, 1), (5, 1), (6, 1)]
[(1, 1), (2, 1), (1, 1), (1, 2), (2, 2), (3, 2), (3, 1), (4, 1), (5, 1)]
[(1, 1), (2, 1), (1, 1), (1, 2), (2, 2), (3, 2), (3, 1), (4, 1), (5, 1), (5, 2)]
[(1, 1), (2, 1), (1, 1), (1, 2), (2, 2), (3, 2), (3, 1), (4, 1), (5, 1), (5, 2), (5, 3)]
[(1, 1), (2, 1), (1, 1), (1, 2), (2, 2), (3, 2), (3, 1), (4, 1), (5, 1), (5, 2), (5, 3), (6, 3)]
[(1, 1), (2, 1), (1, 1), (1, 2), (2, 2), (3, 2), (3, 1), (4, 1), (5, 1), (5, 2), (5, 3), (6, 3), (6, 4)]
[(1, 1), (2, 1), (1, 1), (1, 2), (2, 2), (3, 2), (3, 1), (4, 1), (5, 1), (5, 2), (5, 3), (6, 3), (6, 4), (6, 5)]
[(1, 1), (2, 1), (1, 1), (1, 2), (2, 2), (3, 2), (3, 1), (4, 1), (5, 1), (5, 2), (5, 3), (6, 3), (6, 4), (6, 5), (5, 5)]
[(1, 1), (2, 1), (1, 1), (1, 2), (2, 2), (3, 2), (3, 1), (4, 1), (5, 1), (5, 2), (5, 3), (6, 3), (6, 4), (6, 5), (5, 5), (4, 5)]
[(1, 1), (2, 1), (1, 1), (1, 2), (2, 2), (3, 2), (3, 1), (4, 1), (5, 1), (5, 2), (5, 3), (6, 3), (6, 4), (6, 5), (5, 5), (4, 5), (4, 6)]
[(1, 1), (2, 1), (1, 1), (1, 2), (2, 2), (3, 2), (3, 1), (4, 1), (5, 1), (5, 2), (5, 3), (6, 3), (6, 4), (6, 5), (5, 5), (4, 5), (4, 6), (5, 6)]
[(1, 1), (2, 1), (1, 1), (1, 2), (2, 2), (3, 2), (3, 1), (4, 1), (5, 1), (5, 2), (5, 3), (6, 3), (6, 4), (6, 5), (5, 5), (4, 5), (4, 6), (5, 6), (5, 7)]
[(1, 1), (2, 1), (1, 1), (1, 2), (2, 2), (3, 2), (3, 1), (4, 1), (5, 1), (5, 2), (5, 3), (6, 3), (6, 4), (6, 5), (5, 5), (4, 5), (4, 6), (5, 6), (5, 7), (4, 7)]
[(1, 1), (2, 1), (1, 1), (1, 2), (2, 2), (3, 2), (3, 1), (4, 1), (5, 1), (5, 2), (5, 3), (6, 3), (6, 4), (6, 5), (5, 5), (4, 5), (4, 6), (5, 6), (5, 7), (4, 7), (3, 7)]
[(1, 1), (2, 1), (1, 1), (1, 2), (2, 2), (3, 2), (3, 1), (4, 1), (5, 1), (5, 2), (5, 3), (6, 3), (6, 4), (6, 5), (5, 5), (4, 5), (4, 6), (5, 6), (5, 7), (4, 7), (3, 7), (3, 8)]
[(1, 1), (2, 1), (1, 1), (1, 2), (2, 2), (3, 2), (3, 1), (4, 1), (5, 1), (5, 2), (5, 3), (6, 3), (6, 4), (6, 5), (5, 5), (4, 5), (4, 6), (5, 6), (5, 7), (4, 7), (3, 7), (3, 8), (2, 8)]
[(1, 1), (2, 1), (1, 1), (1, 2), (2, 2), (3, 2), (3, 1), (4, 1), (5, 1), (5, 2), (5, 3), (6, 3), (6, 4), (6, 5), (5, 5), (4, 5), (4, 6), (5, 6), (5, 7), (4, 7), (3, 7), (3, 8), (2, 8), (1, 8)]
[(1, 1), (2, 1), (1, 1), (1, 2), (2, 2), (3, 2), (3, 1), (4, 1), (5, 1), (5, 2), (5, 3), (6, 3), (6, 4), (6, 5), (5, 5), (4, 5), (4, 6), (5, 6), (5, 7), (4, 7), (3, 7), (3, 8), (2, 8)]
[(1, 1), (2, 1), (1, 1), (1, 2), (2, 2), (3, 2), (3, 1), (4, 1), (5, 1), (5, 2), (5, 3), (6, 3), (6, 4), (6, 5), (5, 5), (4, 5), (4, 6), (5, 6), (5, 7), (4, 7), (3, 7), (3, 8)]
[(1, 1), (2, 1), (1, 1), (1, 2), (2, 2), (3, 2), (3, 1), (4, 1), (5, 1), (5, 2), (5, 3), (6, 3), (6, 4), (6, 5), (5, 5), (4, 5), (4, 6), (5, 6), (5, 7), (4, 7), (3, 7), (3, 8), (4, 8)]
[(1, 1), (2, 1), (1, 1), (1, 2), (2, 2), (3, 2), (3, 1), (4, 1), (5, 1), (5, 2), (5, 3), (6, 3), (6, 4), (6, 5), (5, 5), (4, 5), (4, 6), (5, 6), (5, 7), (4, 7), (3, 7), (3, 8), (4, 8), (5, 8)]
[(1, 1), (2, 1), (1, 1), (1, 2), (2, 2), (3, 2), (3, 1), (4, 1), (5, 1), (5, 2), (5, 3), (6, 3), (6, 4), (6, 5), (5, 5), (4, 5), (4, 6), (5, 6), (5, 7), (4, 7), (3, 7), (3, 8), (4, 8), (5, 8), (6, 8)]
[(1, 1), (2, 1), (1, 1), (1, 2), (2, 2), (3, 2), (3, 1), (4, 1), (5, 1), (5, 2), (5, 3), (6, 3), (6, 4), (6, 5), (5, 5), (4, 5), (4, 6), (5, 6), (5, 7), (4, 7), (3, 7), (3, 8), (4, 8), (5, 8), (6, 8), (7, 8)]
[(1, 1), (2, 1), (1, 1), (1, 2), (2, 2), (3, 2), (3, 1), (4, 1), (5, 1), (5, 2), (5, 3), (6, 3), (6, 4), (6, 5), (5, 5), (4, 5), (4, 6), (5, 6), (5, 7), (4, 7), (3, 7), (3, 8), (4, 8), (5, 8), (6, 8), (7, 8), (8, 8)]