用MoonBit编写数独求解器
数独是一种起源于1979年的推理游戏，其形式很适合报刊这种纸质媒体，不过即使在传统报刊式微的今天，可以在电脑、手机上尝试的数独游戏程序仍然不少。虽然在娱乐方式多种多样的今天它很难引起大众的广泛关注，但数独爱好者聚集的社群并未消亡(在线论坛如enjoysudoku)。本文的意图并非劝大家都去玩数独，而是展示如何用MoonBit编写合适的程序求解数独。 1.jpg
本文内容参考了norvig的这篇博客。
方格, 单元与邻居
最普通的一种数独在9x9的方格上进行，我们将行(row)从上到下按A-I编号，列(column)从左到右按1-9编号, 这样就得到了网格中每个方格(square)的坐标，例如下面这个网格中数字0对应的坐标是C3。
1 2 3 4 5 6 7 8 9
A . . . . . . . . .
B . . . . . . . . .
C . . 0 . . . . . .
D . . . . . . . . .
E . . . . . . . . .
F . . . . . . . . .
G . . . . . . . . .
H . . . . . . . . .
I . . . . . . . . .
这个9x9的网格共有9个单元(unit), 每个单元内各个方格上最终所填写的数字互不重复，分别是1~9。但在游戏的初始状态下，大多数方格中没有数字。
4 1 7 | 3 6 9 | 8 2 5
6 3 2 | 1 5 8 | 9 4 7
9 5 8 | 7 2 4 | 3 1 6
---------+---------+---------
8 2 5 | 4 3 7 | 1 6 9
7 9 1 | 5 8 6 | 4 3 2
3 4 6 | 9 1 2 | 7 5 8
---------+---------+---------
2 8 9 | 6 4 3 | 5 7 1
5 7 3 | 2 9 1 | 6 8 4
1 6 4 | 8 7 5 | 2 9 3
在单元以外还有一个重要的概念是邻居(peer), 一个方格的邻居包含同一列，同一行以及同一单元中的其他格子。例如，C2的邻居包含这些方格：
A2 | |
B2 | |
C2 | |
---------+---------+---------
D2 | |
E2 | |
F2 | |
---------+---------+---------
G2 | |
H2 | |
I2 | |
| |
| |
C1 C2 C3| C4 C5 C6| C7 C8 C9
---------+---------+---------
| |
| |
| |
---------+---------+---------
| |
| |
| |
A1 A2 A3| |
B1 B2 B3| |
C1 C2 C3| |
---------+---------+---------
| |
| |
| |
---------+---------+---------
| |
| |
| |
方格和它的所有邻居数字均不可相同。
我们需要一个数据类型SquareMap[T]用来存放81个方格以及每个方格所关联的信息, 这个类型可以通过hashtable实现，但是使用数组实现会更紧凑也更简单。首先编写一个将坐标A1-I9转换到0-80的函数：
// A1 => 0, A2 => 1
fn square_to_int(s : String) -> Int {
if in(s[0], 'A', 'I') && in(s[1], '1', '9') {
let row = s[0].to_int() - 65 // 'A' <=> 0
let col = s[1].to_int() - 49 // '1' <=> 0
return row * 9 + col
} else {
abort("square_to_int(): \{s} is not a square")
}
}
// 辅助函数in判断某个字符的范围是否在lw和up之间
fn in(this : Char, lw : Char, up : Char) -> Bool {
this >= lw && this <= up
}
然后对数组包装一下，提供一套新建、以特定坐标访问赋值、复制SquareMap[T]的操作。通过重载op_get和op_set方法，可以编写形如table["A2"]，table["C3"] = Nil这样的代码，非常方便。
struct SquareMap[T] {
contents : Array[T]
}
fn SquareMap::new[T](val : T) -> SquareMap[T] {
{ contents : Array::make(81, val) }
}
fn copy[T](self : SquareMap[T]) -> SquareMap[T] {
let arr = Array::make(81, self.contents[0])
let mut i = 0
while i < 81 {
arr[i] = self.contents[i]
i = i + 1
}
return { contents : arr }
}
fn op_get[T](self : SquareMap[T], square : String) -> T {
self.contents[square_to_int(square)]
}
fn op_set[T](self : SquareMap[T], square : String, x : T) -> Unit {
self.contents[square_to_int(square)] = x
}
接下来我们要做的是准备一些常量
let rows = "ABCDEFGHI"
let cols = "123456789"
// squares包含了每个方格的坐标
let squares : List[String] = ......
// units[coord]包含了方格coord的所在单元其他方格
// 例：units["A3"] => [C3, C2, C1, B3, B2, B1, A2, A1]
let units : SquareMap[List[String]] = ......
// peers[coord]包含了方格coord的所有邻居
// 例：peers["A3"] => [A1, A2, A4, A5, A6, A7, A8, A9, B1, B2, B3, C1, C2, C3, D3, E3, F3, G3, H3, I3]
let peers : SquareMap[List[String]] = ......
如何构建units和peers两个表这个过程比较乏味，就不一一赘述了。
预处理网格
我们用字符串表示输入的初始数独网格，以下这些格式都是可以的, .和0都代表对应位置上没有数字，其他字符如回车空格则会被忽略。
"4.....8.5.3..........7......2.....6.....8.4......1.......6.3.7.5..2.....1.4......"
"
400000805
030000000
000700000
020000060
000080400
000010000
000603070
500200000
104000000"
让我们暂时不考虑太多游戏规则，如果只考虑一个方格里可能填充上的数字，那么1-9都是有可能的。据此我们将所有方格的初始内容设为['1', '2', '3', '4', '5', '6', '7', '8', '9'](这里表示的是个List)。
fn parseGrid(s : String) -> SquareMap[List[Char]] {
let digits = cols.to_list()
let values : SquareMap[List[Char]] = SquareMap::new(digits)
......
}
接下来要做的是对输入中已知数字的方格进行赋值，这个过程可以用函数assign(values, key, val)实现，key是一个形如A6的字符串，而val是一个字符，很容易写出这样的代码
fn assign(values : SquareMap[List[Char]], key : String, val : Char) {
values[key] = Cons(val, Nil)
}
运行一下看看
"4.....8.5.3..........7......2.....6.....8.4......1.......6.3.7.5..2.....1.4......"
// 此处使用了parseGrid和printGrid函数，因为比较枯燥忽略实现方式直接使用就好
4 123456789 123456789 | 123456789 123456789 123456789 | 8 123456789 5
123456789 3 123456789 | 123456789 123456789 123456789 | 123456789 123456789 123456789
123456789 123456789 123456789 | 7 123456789 123456789 | 123456789 123456789 123456789
---------------------------------+---------------------------------+---------------------------------
123456789 2 123456789 | 123456789 123456789 123456789 | 123456789 6 123456789
123456789 123456789 123456789 | 123456789 8 123456789 | 4 123456789 123456789
123456789 123456789 123456789 | 123456789 1 123456789 | 123456789 123456789 123456789
---------------------------------+---------------------------------+---------------------------------
123456789 123456789 123456789 | 6 123456789 3 | 123456789 7 123456789
5 123456789 123456789 | 2 123456789 123456789 | 123456789 123456789 123456789
1 123456789 4 | 123456789 123456789 123456789 | 123456789 123456789 123456789
这个实现简单而精确，但是我们可以做更多。
这个时候可以把先前搁置的规则请回来了，不过，规则本身是没法告诉我们该怎么做的，我们需要借助规则获得一些启发式的策略。就像用纸笔玩数独一样，我们首先请出排除法：
-
策略1：如果方格key被赋值的内容是val, 那显然它的邻居(peers[key])在values中所对应的列表不应该包含val, 因为这样会违背数独中每个方格所填数字与邻居不重复的规则。
-
策略2：如果key所在的单元只剩下一个方块可以容纳某个特定的数字(在应用了好几次上面那条规则之后就可能出现这种情况)，那显然就应该直接把这个数字赋给那个方块
调整一下代码，我们先定义出eliminate函数，它负责从某个方格删除一个数字. 在执行删除任务之后，它会对key和val分别应用上面的策略尝试消除一些多余的取值。可以注意到它增加了一个布尔返回值，这是为了应对可能存在的矛盾，如果方块key对应的列表为空列表，那显然有什么地方搞错了，我们直接返回false。
fn eliminate(values : SquareMap[List[Char]], key : String, val : Char) -> Bool {
if not(exist(values[key], fn (v) { v == val })) {
return true
}
values[key] = values[key].remove(val)
// 如果key对应的可能性只剩下一种，则从key的邻近位置中消除此可能性
match single(values[key]) {
Err(b) => {
if not(b) {
return false
}
}
Ok(val) => {
let mut result = true
peers[key].iter(fn (key) {
result = result && eliminate(values, key, val)
})
if not(result) {
return false
}
}
}
// 如果key所在的unit中只剩下一个方块可容纳val, 则把val赋值给该方块
let unit = units[key]
let places = unit.filter(fn (sq) {
exist(values[sq], fn (v) { v == val })
})
match single(places) {
Err(b) => {
return b
}
Ok(key) => {
return assign(values, key, val)
}
}
}
// 列表为空返回Err(false)
// 列表为[x]返回Ok(x)
// 列表为[x1, x2, ......]返回Err(true)
fn single[T](this : List[T]) -> Result[T, Bool] {
match this {
Nil => Err(false)
Cons(x, Nil) => Ok(x)
_ => Err(true)
}
}
接下来，我们把assign(values, key, val)定义为删除val以外的值
fn assign(values : SquareMap[List[Char]], key : String, val : Char) -> Bool {
let other_values = values[key].remove(val)
let mut result = true
other_values.iter(fn (val) {
result = result && eliminate(values, key, val)
})
return result
}
上面这两个函数会对它们所访问的每个方格应用启发式策略，一次成功的启发又会引入对新的方格的访问，让这些策略在网格间尽可能广地传播。这是快速消除无用选项的关键。
让我们再尝试一下上面的例子
"4.....8.5.3..........7......2.....6.....8.4......1.......6.3.7.5..2.....1.4......"
4 1679 12679 | 139 2369 269 | 8 1239 5
26789 3 1256789 | 14589 24569 245689 | 12679 1249 124679
2689 15689 125689 | 7 234569 245689 | 12369 12349 123469
---------------------------+---------------------------+---------------------------
3789 2 15789 | 3459 34579 4579 | 13579 6 13789
3679 15679 15679 | 359 8 25679 | 4 12359 12379
36789 4 56789 | 359 1 25679 | 23579 23589 23789
---------------------------+---------------------------+---------------------------
289 89 289 | 6 459 3 | 1259 7 12489
5 6789 3 | 2 479 1 | 69 489 4689
1 6789 4 | 589 579 5789 | 23569 23589 23689
非常大的提升！实际上，这样的预处理已经可以解决一些简单的数独了
"003020600900305001001806400008102900700000008006708200002609500800203009005010300"
4 8 3 | 9 2 1 | 6 5 7
9 6 7 | 3 4 5 | 8 2 1
2 5 1 | 8 7 6 | 4 9 3
---------+---------+---------
5 4 8 | 1 3 2 | 9 7 6
7 2 9 | 5 6 4 | 1 3 8
1 3 6 | 7 9 8 | 2 4 5
---------+---------+---------
3 7 2 | 6 8 9 | 5 1 4
8 1 4 | 2 5 3 | 7 6 9
6 9 5 | 4 1 7 | 3 8 2
如果你比较关注人工智能技术，你可能会注意到这是一个所谓的约束满足(CSP)问题，而assign和eliminate是一个经过特化的弧相容算法。有关此问题的更多介绍请参阅人工智能：一种现代方法一书的第6章
搜索
在完成预处理之后，我们可以大胆地采用暴力枚举来搜索所有可行组合。但同时我们仍然可以在搜索过程中使用之前所提到的启发式策略，在尝试为某个方格赋值时仍然使用assign即可，这可以在搜索过程中同样应用之前的优化去除大量无用分支。
还有个需要注意的地方是，搜索过程中可能会碰到矛盾(就是某个方格的数字被删光了)，可变结构的回溯有些麻烦，所以我们每次赋值时直接复制values。
fn search(values : SquareMap[List[Char]]) -> Option[SquareMap[List[Char]]] {
if values.contains(fn (digits){ not(isSingleton(digits)) }) {
// // 找出对应数字数量大于1且最小的方块，从这个方块开始搜索
// 这只是一个启发式的策略，你可以试着找个更聪明效果更好的
let mut minsq = ""
let mut n = 10
squares.iter(fn (sq) {
let len = values[sq].length()
if len > 1 {
if len < n {
n = len
minsq = sq
}
}
})
// 遍历赋值, 搜索成功则停止遍历
loop values[minsq] {
Nil => None
Cons(digit, rest) => {
let another = values.copy()
if assign(another, minsq, digit){
match search(another) {
None => continue rest
Some(_) as result => result
}
} else {
continue rest
}
}
}
} else {
return Some(values)
}
}
拿同一个例子再跑一遍看看(例子实际上是在magictour这个困难数独列表里抽取的，对人类而言不简单)
> solve("4.....8.5.3..........7......2.....6.....8.4......1.......6.3.7.5..2.....1.4......")
4 1 7 | 3 6 9 | 8 2 5
6 3 2 | 1 5 8 | 9 4 7
9 5 8 | 7 2 4 | 3 1 6
---------+---------+---------
8 2 5 | 4 3 7 | 1 6 9
7 9 1 | 5 8 6 | 4 3 2
3 4 6 | 9 1 2 | 7 5 8
---------+---------+---------
2 8 9 | 6 4 3 | 5 7 1
5 7 3 | 2 9 1 | 6 8 4
1 6 4 | 8 7 5 | 2 9 3
使用MoonBit的在线版本，解决这个数独只花费了0.11秒左右！
完整代码于此：try.moonbitlang.cn/#6806c2fe
结语
游戏的意义在于带走无聊，带来快乐，如果让玩游戏变成一件焦虑多过兴奋的事情，那可能与游戏设计者的初衷背道而驰了。上文展示了简单的排除法和暴力搜索可以很快地解决一些数独难题，这并不是说数独是不值得玩的游戏，我想这一事实所揭示的是不必为某个久思不得其解的数独过于介怀。
跟MoonBit一起更放松地玩游戏吧！