用VBA编程，破解史上最难数独题

先上结果，下图是号称史上最难的数独题。用自编的VBA程序，破解花了大约700多秒，状态栏里有运行的时间。破解过程很无聊，所以没有放出完整视频，放一小段视频，略微看个意思。

用VBA编程，破解史上最难数独题www.zhihu/video/1514542380157505536

这个故事开始发生在两周前。大一的儿子交VB作业，编写一段生成RSA-128密钥对的程序，调试不通跑来问我。我本人不是吃编程饭的，只因初中Basic开蒙，对编程一向有兴趣。大学用的是Fortune，毕业工作后自学过一些C++，foxbase，算是触类旁通，后来工作中略懂Html，Javescript。也用VBA写过一些办公自动化的小程序。

儿子小学时老师要求出2位数加减乘除法的练习题，我自己用随机数编了一个，保证每天有新题。当时就在想，用计算机的穷举法可以解决很多很枯燥的重复运算，其中包括数独。

如今儿子已经从小学到了大学，我始终没有去实现当初的一个小小的灵光乍现。近来上海封控在家，正好用来打发时间。

一、起步

首先解决人机交互界面的问题，Excel操作非常简单，做一个9x9的九宫格不费吹灰之力。后来陆续改进了少许细节，成了下图的样子。

Excel的人机交互界面

然后，把输入区的初始数据录入一个9x9的原始数组，与可视界面上单元格一一对应，并做了简单的校验，主要是排除非法数据（字符，多位数字等），然后做一个简单的校验，行、列、块（块指每一个3x3的小方格，也按从左至右由上到下的1~9编号）里没有重复。

为了避免试算过程中影响原始数米兰lady据，数据校验结束后，复制了一个新数组用于试算。准备工作到此结束。

一、V1.0，穷举试错法

做此事的初衷是为了利用计算机的重复计算能力，最先想到的就是穷举试唐七公子错法。

思路

按照行1-9、列1-9逐一轮询，如果遇到空格（试算数组对应元素数值为0），尝试输入1~9数字，和其所在行列块中已知解做校验，如果不冲突就写入一个9x9的字符串数组，存放试算数，并写在对应单元格中。将当前坐标和试算数记录到一个步骤的数组中。如果金刚经的作用从1试到9都不成功，就返回上一个试错单元格，读出上一步骤记录的数据，开始尝试下一个试算数。如果上一步骤已经试到了9，那么就继续再退一格。以此类推。

题头视频可以看见黄色单元格不停延伸又不停缩回，就是试算的过程。

心得体会消费者心理学

记录步骤的举措是关键，记录挺简单，但是回退的逻辑稍稍有些复杂。因为刚刚上手，很多VBA的变量声明和数组的上下界规则都遗忘了，颇费周折。可视化的过程展示也是一点点改进的。因为后台运算时，前台呈现了假死状态。为了解决这个问题，加入了状态栏进度展示，和计时器展示。但是效果不理想。后来找到了Doevents方法，放在大循环的末尾处，可以激活excel表格，展现试算数的展示，解决了这个问题。

实测

V1.0花费了将近一周，大约四五天。调通后很开心，网上找了不少题目，用穷举法运算，少则几秒，多则一千多秒，都能算出。

二、V2.0，唯一解法和基本摒除法

V1.0成功以后，成就感满满。然而，动辄十来分钟的速度等得让人心慌。于是打算尝试用计算机实现某些推理性的算法，看看编程思路能否增加更多技巧。

说来惭愧，以前从未好好研究数独。在本项目开始之前，还以为数独行列对角线相加之和需要相等。查阅了一些数独的入门读物，找到两条浅显易懂的方法：唯一解法和基本摒除法。

基本概念

唯一解法：如果经过行列块舒淇三级已知解的校验，某单元格只能有一个试算数合格，那么这个试算税负痛苦指数数就是唯一解。

基本摒除法：如果在某一行/列/块中，某数字只出现在某一处位置，那么这个位置的唯一解就是该数字。例如：第3行第7列中，数字456都有可能，但是在同一行中，数字5只出现在此处，那么这个单元格只能是5。

基本摒除法也可以描述为唯一位置法。所以我更愿意将二者称为唯一数字法和唯一位置法，统称唯一法。

思路

首先，建立一个9x9的字符串型数组存放未知单元格的可能解，初始值为”123456789“。然后逐个单元格向所在行列块中分别轮询，发现已知解就将该解中的相同数字剔除。同一个replace()函数轻松解决。唯一解法很直观，如果剩余的可能解字符串只有一位，那就是该单元格唯一解。将该解写入试算数组（注意：这个数组是电机原理整型的，是科学史当初从原始数组完整拷贝过来的，此时这个数组和原始数组开始不同）。同步一下可视界面，用洋红色标注出来。

基本摒除法相对复杂很多，首先需要将行/列/块逐个抽出放入一个一维的1x9的字符型数组。在一维数组中统计每个数字（字符型）出现中苏交恶的次数，如果统计值是1，这个数字就是该单元格的解。找到该数字在行/列/块中的位置，换算成9x9的二维坐标，将该数字写入可能解（字符型），同时更新试算数组对应坐标的元素，最后在可视界面上用青色标注出来。

心得体会

字符型可能解数组是神来之笔。VBA的字符串处理功能比较强大，使用起来得心应手。代码比v1.0复杂很多，开始大量用子程序和函数简化程序结构。子程序和函数与上一级程序的数据交换需要保持数据类型一致，还有数组的维数和上下界的问题开始出现，变量申明和数组声明必须非常严谨规范，否则调试起来很麻烦。

实测

多一个确定解就可以减少大量试错工作。但是唯一法无法保证解决所有问题，当用唯一法重复推理、排除，获得最多的确定解以后，依然需要用穷举试错法求解剩余空格。比较普遍的是解题时间由5~6分钟降到30秒左右。因题而异，最理想的一道题目，完全用这两种推导出完整答案，没有穷举试错。但是也有原先十秒不到的题目，用新方法以后反而增加了数秒，这也不难理解。

三、V3.0，一次意外变招

由于VBA的语法逐渐熟悉，V2.0开发用时比前一版本略少。V2.0新增的唯一解算法对于大多数题目，只能求出为数不多的确定解，而且解题思路没有太多挑战性。于是打算在上一层楼，挑战更复杂的推理方法。

复更高级的推理方法称呼不大统一，揣摩其意思，大概是唯一法向上的延展。照老规矩，笔者应该用自己的语言通俗地表述一遍，但是暂时容我按下不表。

在花了不少于两天时间着手写代码以后，突然发现我犯了方向性错误。寻找多个可能解组合用if then或者select case非常麻烦，因为有层层嵌套关系，后面如果穷举试错走不下去，应该回到哪一层非常烧脑。废了九牛二虎之力写出来的子程序，找到了可能解组合，但是在调试观察可视界面时观察到数字组合找到了，但不是不具备唯一性。逻辑应该是”有且仅有“，而不是仅仅只是”有“。再往下写，程泰国缅甸序更加复杂，逻辑更混乱。但是在寻找算法的时候，发现用数组矩阵处理，统计出现频率和服务三农位置相当简单。用这个算法，V2.0中的唯一解法和基本摒除法（唯一位置法）殊途同归，可以大大简化代码，各种算法的结合应用也可以更紧密。改造后，子程序可以很方便用于高级的推理方法。

于是着手改造算法，引入矩阵算法，用于统计可能解的频率和寻找特定条件的位置。

思路

首先，改造可能解的9x9字符数组。可能解不仅仅是抽出确定解，而是用0占位。比如：原先可能解描述为”124679“，改造后呈现为”120406709“。如此占位符也携带信息，有实际意义。改造仅是在使用replace()函数时，替代符不再是""，而是"0"。

然后，在研究某一行/列/块的一维1x9字符数组时，将该数组转化为一个一个tudor手表9x9的二维整型数组。对这个矩阵进行行列运算可以快速得出某些结果。比如列与列相乘，有0乘数的消除另一边相应位置的可能解，意味着相乘后剩余的位置，二者有共同可能解。再比如，统计行里非0数字个数，表明某数字出现的频率。

在此基础上，编写了若干子程序，用于矩阵的生成，校验和统计。

最用新的子程序对原先的基本摒除法子程序进行改造，成功将两个算法合并为一。为了区别，还特地增加了一个开关，以控制显示颜色，和原先展示习惯保持一致。

心得体会

用函数返回数组时相当麻烦。数组变量必须是variant型，上一级接收的数组变量也必origin下载速度慢须同型。

数组赋值的规则也非常模糊，很难找到明确的手册和规则。上下界和变量类型都严谨到苛刻程度。为了无穷无尽的报错，不得不编写了测试用的母程序，调用新的子程序，以验证数据准确传递到位。

VBA的字符串函数想当方便而数组函数则非常贫乏，和数组有关的函数大多都是为了方便处理字符串，比如array()，split()，都是从下界毛笔字生成器0开始无法修改。而我对矩阵的编号都习惯1~9的顺序号。所以输入输出时不得不做上下界的变更，或者做变量类型的转化。虽然不难，但是很烦人。数组统计函数查找函数都没有现成的，必须自己编。为了不影响主线思路，我没考虑通用性，自定义子程序和函数只是为了处理9x9矩阵。

幸好本项目计算不多，尽可能用字符串处理函数。

实测

因为解题方法没有根本改变，运算速度和V2.0没有明显差异。拿测算的旧题比较，甚至还慢1~2秒。也可能和测试环境相关，测V3.0时电脑开了很多应用没关。测试时debug.print输出和写文件日志也会明显减慢运算速度。

V3.0展示，该题用时21swww.zhihu/video/1514656879896260608四、V4.0，”唯二法“

因为前一阶段解题思路进入歧途，在V3.0中没有增加新的解题思路。但是在工具开发上已经开始考虑新方法的运用。新的思路将在V4.0中实现。查找资料时发现，人们对高级推理方法的称呼不尽统一，所以我姑且用自己的命名：唯二法（杜撰的）。理论上唯二法包括二位或者更多位数的可能解组合，因为前面走过弯路，所以先限定二位可能解组合作为开始。

基本概念

唯二法：在一维可能解的1x9字符串数组中，及其转化而成的9x9整型矩阵中，如果有两位数字组合，出现在、且仅出现在某两个位置，其他位置中的可能解也不存在这两个数任何一个，那么说明这两个数只能存在这两个位置，这两个位置中除该两数的其他可能解都被排除。唯二法不能直接生成确定解，但是可以减少两个单元格的可能解，增加唯一法求解的成功率，以及减少穷举法的尝试次数。

思路

延续矩阵计算的运算方法，研究某一行/列/块的一维1x9字符数组。由上至下先取一行数字，非0的位置必须正好两位。然后取其后续的行，与其相加，生成新矩英文书阵的非0元素如果正好也是两位，说明这两个数字出现的位置完全一致，这一对数字就是这两个单元唯二解。将这两个可能解的字符串替换原来这两个单元格的字符串，相当于排除其他可能解。因为没有找到确定解，所以不要变更试算数组。最后在可视界面上更新对应两个单元格的字符串，用淡紫色标记出来。

心得体会

应用了矩阵计算的方法，使得解题思路大大简化了。子程序逻辑通俗易懂，调试比较方便，所以只花了一天时间就完成了。

实测

毕竟唯二法只能排除部分可能解，不能直接找到可能解。从大多数测试题看，唯一法找到确定解后，留给唯二法的测算空间已经不多。偶有遇到唯二法排除以后，用唯一法又找到新解。在少数情况下，可能还不如穷举试错直接、快速。说明相比计算量，收获有限，性价比不高。但是数组题目千差万别，或许适合其他题型也未可知，毕竟三组单元的一维可能解统统筛一遍，大约只需5~6秒，如果没有找到解就进入穷举子程序，不耽误事。

虽然我明白解题方法千差万别，各有利弊，或许数独题不存在”史上最难“一说，然而题头视频那道题还是颇有道理的。那是我试算到如今，遇到的唯一一道题，从唯一法开始各种推理方法就用不上，只能靠穷举试错暴力破解。

V4.0展示，用时28swww.zhihu/video/1514666948466524160

五、V4.0a，区块摒除法，水到渠成

有了矩阵计算和一些矩阵运算的子程序加持，唯二法出乎意料的顺利。在此找到唯二解基础上，如果这两个位置满足特定条件，可以迅速叠加区块摒除法，进一步紧缩可能什么是宫颈糜烂解的解集。投资产出比不错，值得尝试。但是算不得什么断代的德国帅哥升级，所以不提升版本号。

基本概念

区块摒除法：如果”唯二“的两个单元格正好在3x3的块单元内，又处于同行或同列，那么在这个块单元内，不同行/不同列的单元格不可能出现这两个值，应予以排除。如果经过排除后剩余的可能解恰好只剩一个，那么里昂二大这个值就是确定解。搜索唯二解时是在特定的行/列/块的一维数组中搜索，按照唯二解的定义被搜索的一维数组中的其他单元格已经天然排除这两个数值组合。但是如果搜索的是行/列，恰巧处于同一块单元，那么将对其他两行/列的判断。若是搜索的是块单元，反之亦然。和唯二法不同，区块摒除法有概率获得确定解。

思路

在V4.0寻找符合唯二条件的函数中，做完符合条件的判断以后再次调用一个新的子程序，这个子程序中对唯二的两个坐标j1，j2整除，整除数相等意味着两个解在同一行，或是如果原先在块单元外贸尾货中找的的两个解，那么整除余数相等表明两个解在同一列。如果符合这个条件，则轮询所在行/列的其他无解单元格，将这唯二数值剔除出可能解集。进一步判断，如果所剩可能解只有一个，那么这个解写入确定解数组，同步更新数组和可视界面的显示，用淡紫色标注。

理论上，区块摒除法包括”唯三“情况。因为要对V4.0的算法进行拓展，计算逻辑复杂很多，且在实题演算时这种情况极为罕见（从未遇到），开发性价比不高。在测试演算时观察到经过唯二法排除后，不确定单元格只剩50%左右，此时还有更加方便的算绳艺摄影法，实在不知道去做”唯三“的判断。

心得体会

逻辑简单，几乎一遍调通。

实测

唯二法获得的双单元格往往跨块分布，区块摒除法能够获得确定解不多，循环测算的时间明显延长了。说明走到这一步，能够推理的空间所剩无几。

下一步最便捷的算法应该是”丢硬币法“。在所剩一半左右的未知单元格内寻找仅剩两个可能解的单元，先用一个临时数组记录当前状态，然后粗暴地在两个可能解中二选一，以此为起点从头开始推理、排除和试算，如果能走到头就算成功。如果走不到头，则恢复临时数组，将当时二选一的解排除，剩余的就是确定解。以此类推。鉴于如今兴趣渐消，这个点子就暂且束之高阁吧。

=========笔者还在探索中，未完待续<2022.06.03>=========