跳到主要内容

用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一起更放松地玩游戏吧!

访问MoonBit即可在线试玩使用MoonBit编写的数独求解器,点击链接查看完整源码仓库。