数独是一种起源于1979年的推理游戏，其形式很适合报刊这种纸质媒体，不过即使在传统报刊式微的今日，能够在电脑、手机上测验的数独游戏程序依然不少。虽然在文娱办法多种多样的今日它很难引起大众的广泛关注，但数独爱好者集合的社群并未消亡。
本文的目的并非劝咱们都去玩数独，而是展现如何用MoonBit编写合适的程序来求本领独。游戏界面如下图所示
现在数独求解器已上线官网样例中，咱们能够自行测验。
01方格、单位与街坊
最普通的一种数独在9×9的方格上进行，咱们将行(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 . . . . . . . . .
这个9×9的网格共有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的函数：
fn square_to_int(s : String) -> Int {
if s[0].in('A', 'I') && s[1].in('1', '9') {
let row = s[0].to_int() - 65// 'A' <=> 0let col = s[1].to_int() - 49// '1' <=> 0return row * 9 col
} else {
abort("square_to_int(): (s) is not a square")
}
}
// 辅佐函数in判别某个字符的规模是否在lw和up之间fn in(self : Char, lw : Char, up : Char) -> Bool {
self >= lw && self <= 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])
var 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) {
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两个表这个进程比较庸俗，就不一一赘述了。
02预处理网格
咱们用字符串表明输入的初始数独网格，以下这些格式都是能够的，.和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(values[key].exist(fn (v) { v == val })) {
return true
}
values[key] = values[key].remove(val)
// 假如key对应的或许性只剩下一种，则从key的邻近位置中消除此或许性match values[key].single() {
Err(b) => {
if not(b) {
return false
}
}
Ok(val) => {
var 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) {
values[sq].exist(fn (v) { v == val })
})
match places.single() {
Err(b) => {
if not(b) {
return false
}
}
Ok(key) => {
return assign(values, key, val)
}
}
return true
}
// 列表为空回来Err(false)// 列表为[x]回来Ok(x)// 列表为[x1, x2, ......]回来Err(true)fn single[T](self : List[T]) -> Result[T, Bool] {
match self {
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)
var 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章
03查找
在完成预处理之后，咱们能够大胆地采用暴力枚举来查找一切可行组合。但一起咱们依然能够在查找进程中使用之前所说到的启发式战略，在测验为某个方格赋值时仍使用assign即可，这能够在查找进程中相同使用之前的优化去除大量无用分支。
还有个需要注意的地方是，查找进程中或许会碰到对立(就是某个方格的数字被删了)，可变结构的回溯有些费事，所以咱们每次赋值时直接复制values。
fn search(values : SquareMap[List[Char]]) -> Option[SquareMap[List[Char]]] {
if values.contains(fn (digits){ not(digits.isSingleton()) }) {
// 找出对应数字数量大于1且最小的方块，从这个方块开始查找// 这只是一个启发式的战略，你能够试着找个更聪明作用更好的
var minsq = ""
var n = 10
squares.iter(fn (sq) {
let len = values[sq].length()
if len > 1 {
if len < n {
n = len
minsq = sq
}
}
})
var result : Option[SquareMap[List[Char]]] = None
// 遍历赋值, 查找成功则中止遍历// iter_if(callback)在callback回来值为false时中止遍历//
values[minsq].iter_if(fn (digit) {
let another = values.copy()
if assign(another, minsq, digit) {
let temp = search(another)
match temp {
None => true
Some(v) => {
result = Some(v)
false
}
}
} else {
true
}
})
return result
} else {
return Some(values)
}
}
fn solve(g : String) -> SquareMap[List[Char]] {
match search(parseGrid(g)) {
None => abort("solve() : cant solve (g)")
Some(v) => v
}
}
拿同一个比如再跑一遍看看（比如实际上是在magictour.free.fr/top95这个困难数独…
> 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秒左右！
完好代码于此：完好代码
04结语
游戏的意义在于带走无聊，带来高兴，假如让玩游戏变成一件焦虑多过兴奋的事情，那或许与游戏设计者的初衷背道而驰了。上文展现了简略的排除法和暴力查找能够很快地处理一些数独难题，这并不是说数独是不值得玩的游戏，我想这一现实所揭示的是不必为某个久思不得其解的数独过于介意。
跟MoonBit一起更放松地玩游戏吧！
参阅：
1/ 本文参阅norvig的博客「Solving Every Sudoku Puzzle」
