北京
在大学《算法与数据结构》这门课上，教授抛出了一个让人跃跃欲试的挑战：写个程序，解开所有数独谜题。这听上去不难，但经典的“暴力穷举法”有个致命的缺陷——它得对着空格一个个地试数字，最坏情况下的时间复杂度高达指数级的 O(nm)。n 代表可能的数字，m 代表空格的个数。教授以此激励大家，要想出比这个“指数级数学上界”更优雅的解法。
我脑子一热，立刻开始琢磨怎么动手。直到下一节课，教授才笑眯眯地“补刀”，说他上次“忘了”提最重要的一点：在计算机科学领域，找到一种高效、非指数级的完美解法，其实是一个悬而未决的著名数学难题。换句话说，我当时一头扎进去想摆平的，其实是一个数学界的“无解之局”。但因为已经画好了草图又骑虎难下，我决定硬着头皮继续往下挖。
我开始反思人类解数独和机器暴力破解的本质区别。计算机是在盲目地“瞎猜”，直到碰对为止。而我自己玩数独时，眼睛本能地只会交叉对比三个维度：目标格子所在的行、列，还有那个小的九宫格。这个想法让我开始尝试引入集合论。为了把数学模型搞简单点，我先没敢碰 9x9 的复杂棋盘，而是把问题压缩到了一个只有 4x4 的迷你棋盘上，并给每个方格分配了从 a 到 p 的代号。
当人在看方格 a 时，完全不会随机试数，而是立刻调取三个物理约束：它所在的行、列，以及 2x2 的小宫格。数学上看，方格 a 并不是孤立存在的，它恰恰坐落在三个完全不同的集合交汇处。我把 4x4 棋盘上的每一个格子都映射到了它们各自的行、列、宫格集合中，总共生成了 12 个最基本的约束集合。这样一来，原本笨拙的指数级搜索，瞬间被压成了纯逻辑推演。
打个比方，如果有一格是空的，我们根本不需要猜。只要去看它所在的三个交叉集合里，已经有哪些已知数字。经过简单去重查表，一旦发现数字 {1, 3, 4} 已经被占用了，那么通过纯集合的删除推演，即可判定这一格只能是 2。完全不需要分支回溯，连一个多余的 CPU 周期都不必浪费。我把同样的消元逻辑套用在方格 d 上，立刻算出 d 必须是 3。如果整张棋盘的空格都像这样存在唯一解，这套算法就能以极其轻量的线性时间 O(3m) 直通终点。
可惜，数学的“围墙”就在这里。如果棋盘走到某个死胡同，所有空格都无法通过唯一的集合交集锁定，那还得回到去处理“非强制选择”的棘手状况。虽然这套借助集合论“投机取巧”的算法没能彻底打破那个计算机领域的未解魔咒，但在解决单道数独题时，它通过对逻辑的极致压榨，确实在对比暴力穷举时省下了高达 1000 万次的 CPU 运算量。
特别声明：以上内容(如有图片或视频亦包括在内)为自媒体平台“网易号”用户上传并发布，本平台仅提供信息存储服务。
Notice: The content above (including the pictures and videos if any) is uploaded and posted by a user of NetEase Hao, which is a social media platform and only provides information storage services.
