编程实践｜用MoonBit实现数独求解器，秒变最强大脑！

Original MoonBit运营组 MoonBit 2024-04-02

数独是一种起源于1979年的推理游戏，其形式很适合报刊这种纸质媒体，不过即使在传统报刊式微的今天，可以在电脑、手机上尝试的数独游戏程序仍然不少。虽然在娱乐方式多种多样的今天它很难引起大众的广泛关注，但数独爱好者聚集的社群并未消亡。(在线论坛如：

http://forum.enjoysudoku.com/)

来源于：https://chromewebstore.google.com/

本文的意图并非劝大家都去玩数独，而是展示如何用MoonBit编写合适的程序来求解数独。游戏界面如下图所示👇

目前数独求解器已上线官网gallery中，大家可以自行尝试。链接是：

www.moonbitlang.cn/gallery/sudoku/

01方格、单位与邻居

最普通的一种数独在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的函数：

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' <=> 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(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
  }
}

拿同一个例子再跑一遍看看（例子实际上是在http://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秒左右！

完整代码于此：try.moonbitlang.cn/#9f99136e

04结语

游戏的意义在于带走无聊，带来快乐。如果让玩游戏变成一件焦虑多过兴奋的事情，那可能与游戏设计者的初衷背道而驰了。上文展示了简单的排除法和暴力搜索可以很快地解决一些数独难题，这并不是说数独是不值得玩的游戏，我想这一事实所揭示的是不必为某个久思不得其解的数独过于介怀。

跟MoonBit一起更放松地玩游戏吧！

参考：

1/ 本文参考norvig的博客「Solving Every Sudoku Puzzle」，链接是：http://norvig.com/sudoku.html

官方平台账号，欢迎扫码关注

MoonBit

知乎｜@张宏波 / @MoonBit

小红书｜MoonBit月兔

Twitter丨@Moonbitlang

Bilibili丨MoonBit月兔

MoonBit用户交流群｜添加小助手moonbit_helper

继续滑动看下一个

MoonBit

向上滑动看下一个

李尚福、魏凤和双双被拿下，与美国一份报告是否有关？

有的人走了，却永远活着

圈内疯传某谣言

不要放过这些人渣

最大“独立日烟花秀”存恐怖威胁纽约市警全力部署

编程实践｜用MoonBit实现数独求解器，秒变最强大脑！

您可能也对以下帖子感兴趣

李尚福、魏凤和双双被拿下，与美国一份报告是否有关？

有的人走了，却永远活着

圈内疯传某谣言

不要放过这些人渣

最大“独立日烟花秀”存恐怖威胁 纽约市警全力部署

生成图片，分享到微信朋友圈

编程实践｜用MoonBit实现数独求解器，秒变最强大脑！

您可能也对以下帖子感兴趣

最大“独立日烟花秀”存恐怖威胁纽约市警全力部署