又来到 leetcode,刚做完 Zigzag 转换的我觉得不能把时间浪费在这么没有意义的题目上。沿着算法这个标签页往下读,我看到第 37 题:Sudoku Solver,难度是困难,接受率 33%。

莫名其妙住进 522 房间的一号上铺以后,我买来下学期的化学教辅,一边配平化学方程式扫描任何没见过的分子式,一边在大脑里随机组合此起彼伏的名词与动词。十一月以后,大陆风渐渐盛行,干燥的天气让太阳光变得平易近人。诺大的操场跑着我丝毫不感兴趣的校运会,但是也因此有机会,能在太阳下,低着头听铅笔写在《数独 5》上喳喳的声音。

首先想到的是维护一个 9×9×9 的候选组,前两维是位置,后面是每个方格能填哪些候选值。第一次先扫描整个数独,同行、同列、同方块这个三个约束可以让候选组缩小,如果发现了哪个候选组长度是1,那就说明已经通过排除法确定这个元素是什么。这个时候填入这个元素,同时更新与这个元素同列、同行、同方块的候选值,然后接着找长度是 1 的候选组。这样就又回到之前的状态。

横竖的约束就像中国象棋里的車,每一个数字都能把同行同列杀得片甲不留,而那团团的九宫格里空位有时候本就不多,几趟車开下来,躲起来的数字就没地方跑了。新的数字又是新的車,奔向新的远方。侧过头看看X君,淡绿色制服,短发及肩。广播里单曲循环着已经是第47个年头的《运动员进行曲》,又被体育教头的「请某某、某某某同学到主席台前面……」打断,再被裁判的「预备……跑!」打断,再被班主任的「大家不要光在这里坐着……」打断,直到心里说:「这个地方要填3。」

候选组的思路和从前我做数独很相似,但我也知道有些标记成困难的题目实在找不到只有一个候选值的情况,这个时候就只能挨个去试验,也是非常苦恼且容易出错的一过程。回到刚才的算法,我们并不能断言每次总能运气这么好找到长度为1的候选组,所以需要教会计算机,或者是教会自己,如果最短候选组的长度大于1,应该怎么做。

应该怎么做呢?每个用来填数字的方格有四个顶点,于是我可以用铅笔在方格的四个角落里用八号字体的蝇头小楷注上候选值,然后照着假设接着去做就好了。实在运气不好要推翻一堆数字的时候,那就拿个简单难度的数独来撒气吧。话是这么说,我看到只做了一半的数独,心中总是充满了挫败感。

可是编程就是不停地和自己的挫败感打架。你可以想象在 Visual Studio 2008 里面给一个几百行的 main 函数设置断点一步一步点击跳转监控整个状态集么?这个没有类型、没有内存安全的语言让调试过程充满了各种各样的惊喜。从来没有测试驱动的理念,大学里的编程教育也和现实工程脱节太远,于是验证算法的正确性的唯一方式就变成了人类本能——看 log。在晚上十一点半以后,我终于把笨拙的加法计算器写出来。程序输出结果的那一刻,我没有想到十年后的自己在书写着数独求解器的测试用例。既然对候选组长度大于1的情形没有思路,那不如先把测试写了吧。

偶尔翻到一页有X君的笔迹,心中的一秒钟欢喜给下一分钟的波澜不惊做好了铺垫,还是不叨扰她的未完成吧。快到中学的时候爸妈给我买了一本三十九块钱的接力出版社出版的《彩图袖珍自然百科》,全彩铜版纸印刷的三十二开本,讽刺的是每天睡觉前我都喜欢把书拿到床头,然后就这么放在边桌上,看书页边缘溢出来的一点点彩色油墨,每16页叠成一个书帖,30多个书帖沿着锁线的方向起伏,这些头发丝里的般点也竟铺成了一窗夜空。我惊讶于这本书的精致,尽管只是普通的精装书而已,而只愿我永不打开这书,也就永远能看到它最完美的样子了。也正如彼时一样,这一页未完成也因X君而带上了无瑕,如果要让它停在最完美的时刻,最好的便是逃跑一般地翻到下一页。

撇开实现看测试,书写测试本身是直接的。原问题使用[][]byte来建模一个数独,每个 byte 取19这九个 ASCII 字符作为数字1到9,取.作为空白的方格。SolveSudoku本身修改这个二维切片引用的数据,修改完后再取这个切片把数据打印出来就可以了。测试数据为了人类输入方便,是一个换行分割的字符串,最终打印出来的也是这样的格式。

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
func ExampleSolveSudoku() {
sudoku :=
`
53..7....
6..195...
.98....6.
8...6...3
4..8.3..1
7...2...6
.6....28.
...419..5
....8..79
`
board := stringToBoard(sudoku)
SolveSudoku(board)
result := BoardToString(board)
fmt.Println(result)
// Output:
// 534678912
// 672195348
// 198342567
// 859761423
// 426853791
// 713924856
// 961537284
// 287419635
// 345286179
}

不管是横竖的约束,还是九宫格的约束,人做数独的喜悦都在于搜索所有条件并寄希望于能靠运气碰到一个靠约束可以唯一确定的空格。明白这个问题本质上是在潜在解空间中寻找一个解,那么对计算机来说,它不需要像人类这么左顾右盼找运气,它只需要踏踏实实从第一个空开始尝试就可以了。寻找到第一个空格的地方,从1试到9,如果没有冲突,再继续尝试下一个数字。它不必焦虑于从1尝试到9是不是显得很蠢。这个空格左边就是一个1,怎么可能从1开始试呢?但本质而言,填了1被左边的1否决掉,和填了293 才发现第 3 个空格里的 3 不满足约束,从而必须尝试下一个 294 的解这两件事情对计算机来说毫无区别,如果第一个1就被否决掉,那么就从下一个解开始继续试。1的下一个是2293的下一个是 294,无论长短,无论是填了一个就被否掉,抑或是填完了快一半的空格才沮丧地发现要推倒重来,计算机没有情绪起伏,它不因「似乎可以直接否定某个候选值」而开心,也不因「为什么做了一半才发现整个假设从头开始就错了」而难过。它简单而愚蠢,但这个方法却因为它可以在初期就排除掉很多不可能的解而在实际运算中经常非常高效。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
func bt(solution PartialSolution) *PartialSolution {
if reject(solution) {
return nil
}
if accept(solution) {
return &solution
}

for s := first(solution); s != nil; {
result := bt(*s)
if result != nil {
return result
}
s = next(*s)
}

return nil
}

剩下就只需要按照数独的规则实现 reject, accept, first, next 这几个函数就可以了。

印象中bt更多是变态的拼音首字母缩写和 BitTorrent 的大写字母缩写。「变态」这个词一方面来源于对生物学上的 metamorphosis 的翻译,另一方面却又因为日本人率先把 Sexual Perversion 翻译成「変態性欲」而又传回中国被大家意指「怪胎」或是「色狼」。一个词带上了色情意味就总会让含蓄的中国人想办法去避讳,避讳的结果就是新创出行话以显示自己在社会活得长了,也是见过世面的。于是从「傻屄」到「傻逼」到「傻B」到「sb」,侮辱意味的名词不断地吞噬同音字、拼音缩写词,最后以至于「jb」的原字「𣬠𣬶」竟然只能放在 CJK 表意文字扩展 B 区了,而近于无人知晓了。也罢,这些奇怪的□□不都是叫做「乱码」了。有了这顶帽子,也就不必追寻本来的意味了。

这个时候已经有了计算机批量生成的数独,编者要在前言中注明这些数独都是人精心构造出来的。与机器生成的不同,这些数独会有着独特的美感,例如某几个数字的对称性,数独的提示只有固定的两三个数字,其实就是计算机算出来的数独再加上一些审美的价值判断。但多巴胺总会激励你继续往前做,翻过一座又一座的山,直到频次降低,漫长而不经意地把这个习惯丢失。但人不甘心从有到无的过程变化得那么缓慢,而总愿意安排一个模糊而又实质的时间——「在那一刻,我不再做数独了。」——显得改变总是一瞬间,千丝万缕,斩不断理还乱,而不愿明说这一刻的 Unix 纪元。

只要十一点过后是九点半,地球又往西摆动了 22.5°,二年级的体育生又一次打破了年级记录,运动员进行曲又提前了80秒,《数独 5》又往前翻八页(不想说还有六页是X君的未完成),X君始终低着头,看不清楚颜面。那么永恒,就是这样一个回圈。

而我不愿意就这样草草收场。如果说 for { } 就是一个最简单的回环,什么事情也不做,来回地困在当下。我更愿意回圈是一个生成器,一个取票机的工厂:

1
2
3
4
5
6
function *fibonacci(current = BigInt(0), next = BigInt(1)) {
yield current;
yield *fibonacci(next, current + next);
}
const ticket = fibonacci();
ticket.next();

每次都能通过ticket.next(ticket.value)取出一张新的船票。永远在沉睡,永远不结束,永远在等待下一次计算;但没有不确定性,没有噪音,没有抬头,没有句号。

110 纳秒以后,它输出了这个数独的解。