数独求解器#
数独是一种基于逻辑的益智游戏，起源于 1979 年。它非常适合报纸等印刷媒体，即使在数字时代，许多数独游戏程序也可用于计算机和智能手机。尽管如今娱乐选择多种多样，但数独爱好者仍在继续组建活跃的社区（在线论坛，例如：enjoysudoku）。本文将演示如何使用 MoonBit 编写合适的程序来解决数独问题。
方格、单元和同级#
最常见的数独形式是在 9x9 网格上进行的。我们将从上到下的行标记为 A-I，从左到右的列标记为 1-9。这为网格中的每个方格提供了一个坐标，例如，下面网格中包含数字 0 的方格的坐标为 C3。
1 2 3 4 5 6 7 8 9
A . . . . . . . . .
B . . . . . . . . .
C . . 0 . . . . . .
D . . . . . . . . .
E . . . . . . . . .
F . . . . . . . . .
G . . . . . . . . .
H . . . . . . . . .
I . . . . . . . . .
这个 9x9 的网格共有 9 个单元，每个单元包含的方格必须具有从 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
除了单元之外，另一个重要概念是同级。一个方格的同级包括同一行、同一列和同一单位的其他方格。例如，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 个方格以及与每个方格相关的信息。这可以使用哈希表来实现，但使用数组会更紧凑、更简单。首先，我们编写一个函数将坐标 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")
}
}
// Helper function `in` checks if a character is between `lw` and `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 contains the coordinates of each square
let squares : List[String] = ......
// units[coord] contains the other squares in the unit of the square at coord
// for example：units["A3"] => [C3, C2, C1, B3, B2, B1, A2, A1]
let units : SquareMap[List[String]] = ......
// peers[coord] contains all the peers of the square at coord
// for example：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]] = ......
构建单元和同级表的过程非常繁琐，因此这里不再详述。
预处理网格#
我们使用字符串来表示初始数独网格。各种格式均可接受；. 和 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'] (a 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......"
// Using parseGrid and printGrid functions, skipping implementation details for simplicity
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]’）的可能值列表中不应该包含 `val’，因为这会违反同一单元、行或列中没有两个方块可以具有相同数字的规则。策略 2：如果一个单元中只有一个方格可以容纳特定的数字（在多次应用上述规则后可能发生），则应将该数字分配给该方格。
我们通过定义一个消除函数 eliminate 来调整代码，该函数从正方形的可能值中删除一个数字。执行消除任务后，它将上述策略应用于 key 和 val 以尝试进一步消除。请注意，它包含一个布尔返回值来处理可能的矛盾。如果方格的可能值列表为空，则出现问题，我们返回 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)
// If `key` has only one possible value left, remove this value from its peers
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
}
}
}
// If there is only one square in the unit of `key` that can hold `val`, assign `val` to that square
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)
}
}
}
// Return `Err(false)` if the list is empty
// Return `Ok(x)` if the list contains only `[x]`
// Return `Err(true)` if the list contains `[x1, x2, ......]`
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) 来从 key 的可能值中删除除 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)，而’分配’和’消除’是专门的弧一致性算法。有关此主题的更多信息，请参阅 Artificial Intelligence: A Modern Approach 第 6 章
搜索#
经过预处理后，我们可以大胆地使用蛮力枚举来搜索所有可行的组合。但是，在搜索过程中，我们仍然可以使用启发式策略。当尝试为某个方块赋值时，我们仍然使用 assign，这使我们能够应用先前的优化来消除搜索过程中的许多无效分支。
另外需要注意的是，搜索过程中可能会发生冲突（当一个方格的可能值耗尽时）。由于可变结构使回溯变得麻烦，因此我们每次分配值时都直接复制值。
fn search(values : SquareMap[List[Char]]) -> Option[SquareMap[List[Char]]] {
if values.contains(fn (digits){ not(isSingleton(digits)) }) {
// // Find the square with the smallest number of possible values greater than 1, and start the search from this square
// This is just a heuristic strategy; you can try finding a smarter and more effective one
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
}
}
})
// Iterate through assignments and stop if a successful search is found
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 online IDE 上运行，仅需大约 0.11 秒即可解决这个数独！
总结#
游戏的目的是为了缓解无聊并带来快乐。如果玩游戏让人感到焦虑而不是兴奋，那么它可能违背了游戏设计师的初衷。本文表明，简单的消除法和强力搜索可以快速解决一些数独难题。这并不意味着数独不值得玩；相反，它表明人们不应该过分担心无法解决的数独难题。
让我们轻松玩转 MoonBit 吧！
访问 MoonBit Gallery 来试用用 MoonBit 编写的数独解算器。单击 此链接 可查看完整源代码。
本教程参考了 Norvig 的博客：http://norvig.com/sudoku.html