本文提供了命运二的异端深渊地牢（The Pit of Heresy Dungeon）九宫格谜题的一个状态压缩动态规划解法，并给出了一个最小 Python 实现，能够求解任意局面，避免重置任务导致的时间浪费。

问题描述、性质与形式化

在任务的「旅途第二步」过程中，玩家会遇到如下形式的谜题：

problem

具体而言，给定如左图所示的九宫格，玩家需要通过击打部分格子，将所有格子中的图案都变为目标图案。规则如下：

  • 击打某一格子时，该格子所在行、所在列共 5 个格子的图案都会发生一次变换
  • 变换的规律如右图所示，图案在一个循环群之内转移

不难发现，这个问题的解具备一定性质：解与击打格子的顺序无关，只与每个格子的击打次数有关。每个格子的状态空间为 ，九宫格宫格状态总数有 种。对于每个格子，记图案的下标为 ，那么需要击打该格子所在行、所在列的 5 个格子的总次数为：

动态规划解法

注意到，一个格子的 4 种状态可以用 2 位 01 串编码，故可以使用 18 位 01 串表示当前九宫格状态。用 dp[state] 表示达成 state 状态的最小击打次数。用 anc[state] 表示达成 state 状态的最小击打次数方案中，最后击打的格子。

规划过程中，重复如下步骤直到目标达成：首先将上一次规划中的 last_dp 拷贝至 dp，然后枚举所有 state，对于一个 state，分别讨论击打 9 个格子形成的新 state，并维护 dp, anc。下面是上述算法的一个 Python 实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
while last_dp[target_state] == INF:
    dp = last_dp.copy()
    for state in range(max_state):
        if last_dp[state] == INF:
            continue
        for i in range(9):
            new_state = state
            for to in link_map[i]:
                if state & there_map[to] == there_map[to]:
                    new_state ^= there_map[to]
                else:
                    new_state += one_map[to]
            if last_dp[state] + 1 < dp[new_state]:
                dp[new_state] = last_dp[state] + 1
                anc[new_state] = (i, state)
    last_dp = dp.copy()

值得一提的是，本问题中并不是所有九宫格状态都能达成指定状态，即所有状态转移的闭包不包含目标状态。因此为了实现更一般的解，需要判定无解状态，一种简单的判定方式如下：如果一次规划，没有导致访问状态集合的增长，那么意味着已经达成了闭包，若此时仍未见目标状态，那么意味着不存在可行解。

Python 算法实现示例

dp(start_map: list, target: int)即为算法实现。不失一般性的，约定 9 个格子的顺序为行主序：

1
2
3
0 1 2
3 4 5
6 7 8

约定 4 种图案的编号如下：

fAsgYJaw67GtVRh

那么，只需输入 9个图案下标构成的列表，以及目标图案的下标，就能够进行求解，返回值包括最小击打次数（-1代表无解），以及击打方案（有解情况下，为 9个格子所需的击打次数）。完整代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
def dp(start_map: list, target: int):
    max_state = 1 << 18
    INF = 114514

    there_map = [3 << (i * 2) for i in range(9)]
    one_map = [1 << (i * 2) for i in range(9)]
    link_map = [[] for _ in range(9)]
    for i in range(9):
        for j in range(9):
            ix, iy = i // 3, i % 3
            jx, jy = j // 3, j % 3
            if ix == jx:
                link_map[i].append(j)
            elif iy == jy:
                link_map[i].append(j)

    start_state = 0
    target_state = 0
    for i, item in enumerate(start_map):
        start_state |= item << (i * 2)
        target_state |= target << (i * 2)

    anc = [None] * max_state
    last_dp = [INF] * max_state
    last_dp[start_state] = 0
    last_vis = 1

    while last_dp[target_state] == INF:
        dp = last_dp.copy()
        for state in range(max_state):
            if last_dp[state] == INF:
                continue
            for i in range(9):
                new_state = state
                for to in link_map[i]:
                    if state & there_map[to] == there_map[to]:
                        new_state ^= there_map[to]
                    else:
                        new_state += one_map[to]
                if last_dp[state] + 1 < dp[new_state]:
                    dp[new_state] = last_dp[state] + 1
                    anc[new_state] = (i, state)
        last_dp = dp.copy()

        new_vis = 0
        for state in range(max_state):
            if last_dp[state] != INF:
                new_vis += 1

        if new_vis == last_vis:
            return -1, None
        else:
            last_vis = new_vis

    ans = [0 for _ in range(9)]
    state = target_state
    while state != start_state:
        op, state = anc[state]
        ans[op] += 1
    return last_dp[target_state], ans


if __name__ == "__main__":
    start_map = [0, 0, 0, 0, 0, 0, 0, 0, 0]
    target = 1
    print(dp(start_map, target))

进一步分析

  1. 给出任意状态与任意目标，有解的概率是怎样的？

    进行 500 次独立实验，随机采样状态与目标，发现其中 461 个实验无解。

  2. 给出任意有解的状态与目标，最优方案的击打次数期望是多少？

    有解的实验中，最少击打次数的期望为 。

许可协议

本文采用 署名-非商业性使用-相同方式共享 4.0 国际 许可协议，转载请注明出处。