赛博朋克2077里的代码矩阵解密小游戏我前后点废过不下五十次。最开始我也是凭手感乱戳点在哪儿全看哪格顺眼结果缓冲槽满了、序列连一条都没凑齐只能眼睁睁看着接入点判定失败。后来我把这个局拆成了一道带约束的组合搜索题写了个几十行的脚本从矩阵录入到最优路径输出一杯咖啡的功夫就能跑完。这篇文章会把这个过程完整讲一遍规则里那些容易看漏的硬约束、贪心为什么一定翻车、怎么用KMP自动机把“序列进度”压成一个整数、以及一份可以直接抄走的Python求解器。适合两类人看——一类是想搞懂这个解密最优解到底该怎么算的玩家一类是想拿它练手搜索/剪枝算法的同学。1. 规则复盘代码矩阵里那四条容易被忽略的硬约束很多人觉得这个游戏简单无非就是“凑格子”但实际上它同时压了四条约束任何一条看漏你的最优解就是错的。我先把这四条摆出来后面所有算法设计都建立在这上面。第一条第一步只能落在最上面那一行。也就是说可选的起始格是“第0行的任意一列”。这一条决定了搜索树的根节点不是25个格子而是5个或6个。第二条行列必须交替。选完第0行某个格子后接下来必须在这个格子所在的列里选下一格选完列里的格子后再回到它所在的行里选如此往复。这也是为什么这个局面不能当成普通的网格最短路径来做——你的每一步可动范围是被上一步锁死的。第三条同一个格子不能重复选。这条是我踩过的最大坑。选过的格子会被锁定你再想回头用它是用不了的。这带来一个很隐蔽的结果用掉一个格子存在“机会成本”它可能本来是后面某条路径唯一的桥。第四条缓冲槽数量有限。你的接入仓决定缓冲区长度早期可能是4格越往后越多。选满就结束同时你其实也可以不填满直接停手。序列的判定规则是daemon 序列必须是缓冲序列的连续子串。我用一张表把这四条和常见误解对齐一下约束准确含义常见误解起点固定第一格只能来自第0行以为任意格子都能开局行列交替每步的可选范围由上一格决定以为可以在任意行或列里随便挑不可复用已选格子被锁定无法二次选中以为可以来回蹭同一个格子刷进度连续匹配序列必须是缓冲序列的连续片段当成子序列不连续也算来做重点说说最后一条“连续匹配”。这条几乎是新手和老手的分水岭。假设缓冲序列是1C 55 BD你要的 daemon 是1C BD中间隔了一个55这条 daemon 是不成立的因为你不能跳过中间的码去拼。理解这一点之后你就会意识到这个问题的本质是“在一条受行列交替约束的路径上让缓冲序列尽可能多地包含若干条目标串作为连续子串”而这就是一个标准的组合搜索问题。2. 贪心为什么必然翻车一个能亲手复现的反例绝大多数人第一次玩用的都是某种贪心策略盯住价值最高的那一条 daemon每一步都选让它最靠近完成的格子。这个策略在简单局面上经常能成所以很容易让人误以为“这游戏就是拼眼力”。但只要局面里出现了“两条小 daemon 加起来比一条大 daemon 更值”的情况贪心就必然翻车。我给你一个能亲手验证的4×4棋盘缓冲槽为4格BD FF 1C FF 55 BD 1C FF FF 55 FF FF FF BD FF FF三条 daemon 分别是S1 1C 1C价值记为60S2 BD BD价值60Long BD 55 BD 55价值100。别纠结这几个数字从哪来它们代表你在游戏里给不同 daemon 排的优先级后面我会讲怎么定权重。贪心盯住价值最高的Long100它会这么走起点(0,0)BD→ 列0选(1,0)55→ 行1选(1,1)BD→ 列1选(2,1)55。缓冲序列是BD 55 BD 55Long恰好完整命中得分100。看起来完美。但最优解其实是120。正确路径是起点(0,2)1C→ 列2选(1,2)1C→ 行1选(1,1)BD→ 列1选(3,1)BD。缓冲序列变成1C 1C BD BD前面两格命中S160后面两格命中S260合计120比盯着单条大 daemon 还多20。这个例子的意义不在于20这个差值而在于它证明了“当前最优”不等于“全局最优”。贪心只看眼前这一格能推进什么而在有限缓冲槽下真正决定胜负的是“这4格该怎么分配”——是全部押在一条长序列上还是切成两段去拿两条短序列。这个问题没有任何局部信息能告诉你答案只能靠枚举加剪枝把整棵搜索树过一遍。顺带说一个更隐蔽的贪心翻车方式由于“格子不可复用”有些格子你这一步用了后面某个关键路径就断了。贪心在选这一步的时候根本不会知道这个后果因为它没有前瞻。3. 状态建模用KMP自动机把“序列进度”压成一个整数全量搜索听起来吓人但如果状态设计得好搜索空间会小到可以忽略。关键在于未来能完成什么只取决于两样东西——每条 daemon 当前的匹配进度以及哪些 daemon 已经完成了跟你具体走过哪些格子无关。先说“匹配进度”怎么定义。对于某条 daemon我用一个整数表示当前缓冲序列的最长后缀恰好是这条 daemon 序列的前缀的长度。比如 daemon 是1C 1C BD当前缓冲是1C 1C最长后缀1C 1C正好是它的前缀进度就是2如果再来一个1C缓冲变成1C 1C 1C最长后缀1C 1C仍是前缀进度还是2而不是笨办法里算出来的3或者1。这里就是最容易写错的地方。很多人会图省事写成“如果新码等于序列第 progress 个码就 1否则看新码是不是序列的第一个码是就重置为1”。这个写法在序列存在自我重叠时会算错。举个反例daemon 是1C 1C BD缓冲走到1C 1C进度2再来一个1C正确的进度应该是2但那个偷懒写法会给出1因为新码等于首码被重置了于是后面永远也凑不齐1C 1C BD。正确的做法是构建每条 daemon 的前缀自动机本质就是KMP的失配指针。它保证无论序列怎么自我重叠状态转移都是对的。核心就是这个转移表def build_automaton(seq, alphabet): m len(seq) # 先求KMP的前缀函数 pi [0] * m for i in range(1, m): j pi[i - 1] while j 0 and seq[i] ! seq[j]: j pi[j - 1] if seq[i] seq[j]: j 1 pi[i] j trans {} for k in range(m 1): for c in alphabet: if k m: trans[(k, c)] m # 已完成就保持完成 elif seq[k] c: trans[(k, c)] k 1 elif k 0: trans[(k, c)] 0 else: j pi[k - 1] while j 0 and seq[j] ! c: j pi[j - 1] trans[(k, c)] j 1 if seq[j] c else 0 return trans有了这套转移进度更新就是一次查表O(1) 搞定。再定义完整状态。我用一个五元组描述搜索到某一步时的局面(方向, 固定索引, 进度元组, 已完成掩码, 剩余步数)。方向表示“下一步是横着选还是竖着选”固定索引对应“现在被锁定的那一行或那一列”进度元组是每条 daemon 的匹配进度已完成掩码用一个二进制位标记哪些 daemon 已经收工。为什么这些字段就够用了因为下一步能选的格子只由“方向和固定索引”决定而最终得分只由“已完成掩码”决定剩下还没完成的 daemon 能不能补上只由“进度元组和剩余步数”决定。至于你是绕了远路还是抄了近道走过来的对未来的影响是零。这条“无后效性”是整个剪枝能成立的理论基础。4. 完整可跑的Python求解器DFS加分支限界状态设计好之后剩下的就是最经典的深度优先搜索加分支限界。我把它拆成三段讲最后给完整代码。第一段是局面输入。矩阵我建议直接手敲一个5×5也就25个格子比截图识别可靠得多不容易出识别错误。daemon 连同它的权重一起写成一个三元组列表。matrix [ [BD, FF, 1C, FF], [55, BD, 1C, FF], [FF, 55, FF, FF], [FF, BD, FF, FF], ] daemons [ (S1, [1C, 1C], 60), (S2, [BD, BD], 60), (Long, [BD, 55, BD, 55], 100), ] buffer_size 4 R, C len(matrix), len(matrix[0]) seqs [d[1] for d in daemons] rewards [d[2] for d in daemons] names [d[0] for d in daemons] ALPHABET sorted({code for row in matrix for code in row})第二段是上界估计也就是剪枝的灵魂。在任何一个搜索节点上我先乐观地估一下“从这里继续走最多还能拿多少分”。乐观的估法是对每条还没完成的 daemon只要剩余步数够它从头匹配一遍就先把它的奖励加进去。如果这个上界都不如已经找到的最好解那整棵子树直接砍掉一秒都不用多花。def upper_bound(progress, done_mask, steps_left): b 0 for i in range(len(seqs)): if done_mask i 1: b rewards[i] else: need len(seqs[i]) - progress[i] if steps_left need: b rewards[i] return b第三段是主搜索。初始状态是“方向横向、固定索引0、进度全0、什么都没完成”从一个空的缓冲序列出发。每选一个格子就更新进度、检查有没有 daemon 刚好完成、把格子加入已用集合然后递归。回溯时把现场还原。best {score: -1, path: [], buffer: [], done: []} def dfs(vertical, fixed_idx, depth, used, progress, done_mask, buffer, path): score sum(rewards[i] for i in range(len(seqs)) if done_mask i 1) if score best[score]: best[score] score best[path] path[:] best[buffer] buffer[:] best[done] [names[i] for i in range(len(seqs)) if done_mask i 1] if depth buffer_size: return if upper_bound(progress, done_mask, buffer_size - depth) best[score]: return options range(C) if not vertical else range(R) for k in options: r, c (fixed_idx, k) if not vertical else (k, fixed_idx) if (r, c) in used: continue code matrix[r][c] np list(progress) nd done_mask for i in range(len(seqs)): if nd i 1: continue np[i] autos[i][(np[i], code)] if np[i] len(seqs[i]): nd | (1 i) used.add((r, c)); buffer.append(code); path.append((r, c)) dfs(not vertical, c if not vertical else r, depth 1, used, tuple(np), nd, buffer, path) path.pop(); buffer.pop(); used.remove((r, c)) dfs(False, 0, 0, set(), tuple([0] * len(seqs)), 0, [], []) print(最高收益:, best[score]) print(命中 daemon:, best[done]) print(缓冲序列:, best[buffer]) print(坐标路径:, best[path])把我上一节那个4×4反例喂进去程序会稳定输出“最高收益 120”命中的是S1和S2路径正是(0,2) (1,2) (1,1) (3,1)。之所以敢在每一个节点都更新一次最优解是因为游戏里允许你提前停手不一定要把缓冲槽填满——这一手让程序天然覆盖了“少选几步反而更划算”的情况。注意dfs最后那个参数c if not vertical else r如果这一步是横向选的锁定了某一列下一轮就该纵向选固定索引变成这一列的列号反过来同理。写反了就会得到一堆看起来合理、实际完全违反规则的解这是最隐蔽的bug之一。5. 性能与正确性验证复杂度账本和几个边界情况先说复杂度好让你知道这方法在你自己的机器上能不能扛住。搜索树的最大分支因子是棋盘的行列最大值最大深度是缓冲槽长度。最坏情况下的路径数量是max(R,C)^buffer。拿常见的几种规模算一下棋盘规模缓冲槽理论路径量级说明5×54约 6×10²手点都能赢脚本秒出6×66约 5×10⁴剪枝后几乎瞬间6×68约 1.7×10⁶一般机器0.5秒内7×78约 5.8×10⁶加上剪枝后基本秒级真正让这个数量级变得可接受的是三件事一是“格子不可复用”天然砍掉了大量回路二是分支限界一旦找到好解后面大量子树直接被上界判定剪掉三是我在每个节点发现“剩余步数已经不够再完成任何新 daemon”时会提前收手。综合下来哪怕是最难的7×7加8格缓冲实测也是即时出结果不会有等待感。然后是正确性。我建议你做两个验证。第一个是暴力对照。写一个最朴素的版本不管剪枝把所有符合规则的路径全部枚举出来逐条算分取最大值。在5×5、4格缓冲这种小规模上跑一遍和剪枝版的输出对比。如果两者结果一致说明你的剪枝没有错误地砍掉最优解。这是我强烈推荐你花十分钟做的事因为剪枝写错是这类程序最常见的隐患——它不会报错只会悄悄给你一个“看起来对”的次优解。第二个是边界情况清单我踩过的几个坑列在这儿空 daemon 列表不应该崩直接返回0分。daemon 比缓冲槽还长永远无法完成上界估计里那个need会大于剩余步数自然被排除。序列存在自我重叠就是1C 1C BD那种必须靠自动机才能算对。起始格距离(0,0)或者(0,C-1)这种边角起始列方向的可用格会变少程序得正确处理越界。提前停手得分在缓冲槽没被填满时也可能最优所以要在每个节点都记录最优。有一件事我一开始想复杂了我原本打算用记忆化把重复状态缓存起来。后来发现根本用不上因为路径本身决定了缓冲序列而缓冲序列基本不会重复缓存命中率极低反而增加了哈希开销。直接DFS加剪枝在这个规模下更简单也更快。6. 回到游戏权重怎么定以及几条不写进文档的手感技巧算法跑通只是第一步真正决定你赢不赢得漂亮的是权重的设定。游戏里的 daemon 没有明码标价你得根据自己的玩法目标去排序。我一般是这么分的daemon 类型典型作用建议权重数据挖掘类V1/V2/V3换成钱和材料纯收益中高按等级递增炮塔/摄像头关闭潜行流的核心直接影响能不能不惊动人视任务定潜行流给最高战斗辅助类如削弱敌人硬刚流的救场手段中视走位习惯顺手能拿的短序列通常和长序列共享前缀中低作为填充关键在于不要给所有 daemon 定成一样的权重那等于放弃了“组合更优”这条信息。我那个反例里就是靠“两条短的加起来比一条长的更值”才能胜过贪心。你在游戏里设置的权重越贴近真实收益脚本给你的解就越接近手点的最优。再说几条实打实的手感技巧这些是我反复点废之后攒下来的攻略里基本不会写第一先数缓冲槽再数 daemon 总长度。如果所有 daemon 加起来需要的码数远超缓冲槽那这一局注定拿不全你的目标是“挑最值钱的组合”而不是“尽量多完成”。脚本里的上界估计会帮你自动做这个取舍。第二优先找能共享前缀的 daemon。两条 daemon 如果都以BD开头那么同一个起始格可能同时给它们两个起步性价比极高。这一条在肉眼判断时非常好用扫一眼第一行看哪个码能同时挂上两条以上的序列。第三别忽略“最后一格”的陷阱。因为格子不可复用有时候你的倒数第二步会锁死最后一格的可用性。脚本靠回溯天然处理了但手点的时候你很容易在这一步翻车。我的经验是手点到剩最后两格时先把两条候选路径在心里各走完一遍再落子。第四矩阵录入务必手敲核对。我试过用截图识别自动读格子识别错一位就是满盘皆错。25个格子手敲也就一分钟比后期debug省心得多。真要自动化也得加一步人工校对别全信识别结果。第五不要迷信“先点最顺眼的”。这个游戏最大的反直觉之处在于开场第一格选错后面再聪明也救不回来。我在反例里已经把这点演给你看了——同样是价值最高的那条 daemon 摆在那儿盯着它走的都输给了绕开它的那套组合。最后分享一个我自己常用的小技巧如果懒得开脚本就用“两到三步前瞻”来替代全量搜索。具体做法是把每个候选起始格往后展开两三层看两三层之后能同时保住几条 daemon 的进度选保住条数最多的那个。这个土办法没法保证全局最优但在6格以内的缓冲下它胜过单纯贪心的概率很高足够应付绝大多数接入点。真要卡在高难度局过不去再回头把上面那份脚本跑一遍就行。