数独求解器

数独求解器#

数独是一种基于逻辑的益智游戏，起源于 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 的唯一数字。但是在游戏的初始状态下，大多数方格不包含任何数字。

1  7 | 3  6  9 | 8  2  5
3  2 | 1  5  8 | 9  4  7
5  8 | 7  2  4 | 3  1  6
---------+---------+---------
2  5 | 4  3  7 | 1  6  9
9  1 | 5  8  6 | 4  3  2
4  6 | 9  1  2 | 7  5  8
---------+---------+---------
8  9 | 6  4  3 | 5  7  1
7  3 | 2  9  1 | 6  8  4
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|         |
---------+---------+---------
         |         |
         |         |
         |         |
---------+---------+---------
         |         |
         |         |
         |         |

没有两个同级的格子可以包含相同的数字。

我们需要一个数据类型 Grid[T] 来存储这 81 个方格以及与每个方格相关的信息。这可以使用哈希表来实现，但使用数组会更紧凑、更简单。首先，我们编写一个函数将坐标 A1-I9 转换为索引 0-80：

// A1 => 0, A2 => 1
fn square_to_int(s : String) -> Int {
  if s.charcode_at(0) is ('A'..='I') && s.charcode_at(1) is ('1'..='9') {
    let row = s.charcode_at(0) - 65 // 'A' <=> 0
    let col = s.charcode_at(1) - 49 // '1' <=> 0
    return row * 9 + col
  } else {
    abort("Grid_to_int(): \{s} is not a Grid")
  }
}

///|
test {
  inspect(square_to_int("A1"), content="0")
  inspect(square_to_int("A7"), content="6")
  inspect(square_to_int("I9"), content="80")
}

然后我们包装这个数组，并提供创建、访问、为特定坐标赋值以及复制 Grid[T] 的操作。通过重载 op_get 和 op_set 方法，我们可以编写类似 table["A2"] 和 table["C3"] = ... 的便捷代码。

///|
type Grid[T] FixedArray[T]

///|
fn[T] Grid::new(val : T) -> Grid[T] {
  FixedArray::make(81, val)
}

///|
fn[T] Grid::copy(self : Grid[T]) -> Grid[T] {
  if self.inner().length() == 0 {
    return []
  }
  let arr = FixedArray::make(81, self.inner()[0])
  let mut i = 0
  while i < 81 {
    arr[i] = self.inner()[i]
    i = i + 1
  }
  return arr
}

///|
fn[T] Grid::op_get(self : Grid[T], square : String) -> T {
  let i = square_to_int(square)
  self.inner()[i]
}

///|
fn[T] Grid::op_set(self : Grid[T], square : String, x : T) -> Unit {
  let i = square_to_int(square)
  self.inner()[i] = x
}

接下来我们准备一些常量：

let rows = "ABCDEFGHI"

let cols = "123456789"

typealias Squares = @immut/sorted_set.T[String]

// squares contains the coordinates of each square
let squares : Squares = ......

// 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 : Grid[Squares] = ......

// 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 : Grid[Squares] = ......

构建单元和同级表的过程非常繁琐，因此这里不再详述。

预处理网格#

我们使用字符串来表示初始数独网格。各种格式均可接受；. 和 0 均表示空方块，其他字符（如空格和换行符）将被忽略。

#|400000805
#|030000000
#|000700000
#|020000060
#|000080400
#|000010000
#|000603070
#|500200000
#|104000000

#|4 . .   . . .   8 . 5
#|. 3 .   . . .   . . .
#|. . .   7 . .   . . .
#|
#|. 2 .   . . .   . 6 .
#|. . .   . 8 .   4 . .
#|. . .   . 1 .   . . .
#|
#|. . .   6 . 3   . 7 .
#|5 . .   2 . .   . . .
#|1 . 4   . . .   . . .

暂时先不考虑太多游戏规则，如果只考虑每个方格能填入的数字，那么 1-9 都是有可能的，因此我们初始将所有方格的内容设置为['1', '2', '3', '4', '5', '6', '7', '8', '9'] (a List)。

fn Grid::parse(s : String) -> Grid[@immut/sorted_set.T[Char]] {
  let digits = @immut/sorted_set.from_array(cols.to_array())
  let values = Grid::new(digits)
  ...
}

接下来，我们需要将输入中已知数字的方块赋值。这个过程可以用函数 assign(values, key, val) 来实现，其中 key 是一个字符串，比如 A6，val 是一个字符。这样的代码写起来很容易。

fn assign(values : Grid[@immut/sorted_set.T[Char]], key : String, val : Char) -> Unit {
  values[key] = @immut/sorted_set.singleton(val)
}

这个实现简单而精确，但我们可以做得更多。

现在，我们可以重新引入之前搁置的规则。但是，规则本身并没有告诉我们该做什么。我们需要启发式策略来从规则中获得见解，类似于用笔和纸解决数独。让我们从消除法开始：

策略 1：如果为一个方块 key 分配了一个值 val，则其对同级（’peers[key]’）的可能值列表中不应该包含 `val’，因为这会违反同一单元、行或列中没有两个方块可以具有相同数字的规则。
策略 2：如果一个单元中只有一个方格可以容纳特定的数字（在多次应用上述规则后可能发生），则应将该数字分配给该方格。

我们通过定义一个消除函数 eliminate 来调整代码，该函数从正方形的可能值中删除一个数字。执行消除任务后，它将上述策略应用于 key 和 val 以尝试进一步消除。请注意，它包含一个布尔返回值来处理可能的矛盾。如果方格的可能值列表为空，则出现问题，我们返回 false。

fn eliminate(
  values : Grid[@immut/sorted_set.T[Char]],
  key : String,
  val : Char
) -> Bool {
  if not(values[key].contains(val)) {
    return true
  }
  values[key] = values[key].remove(val)
  // If `key` has only one possible value left, remove this value from its peers
  match values[key].size() {
    1 => {
      let val = values[key].min()
      let mut res = true
      for key in peers[key] {
        res = res && eliminate(values, key, val)
      }
      if not(res) {
        return res
      }
    }
    0 => 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) { values[sq].contains(val) })
  match places.size() {
    1 => {
      let key = places.min()
      return assign(values, key, val)
    }
    0 => return false
    _ => return true
  }
}

接下来，我们定义 assign(values, key, val) 来从 key 的可能值中删除除 val 之外的所有值。

///|
fn assign(
  values : Grid[@immut/sorted_set.T[Char]],
  key : String,
  val : Char
) -> Bool {
  let other_values = values[key].remove(val)
  let mut result = true
  for val in other_values {
    result = result && eliminate(values, key, val)
  }
  return result
}

这两个函数将启发式策略应用于它们访问的每个方格。成功的启发式应用会引入新的方格供考虑，从而使这些策略在整个网格中广泛传播。这是快速消除无效选项的关键。事实上，这种预处理已经可以解决一些简单的数独难题。

let grid2 =
  #|0 0 3   0 2 0   6 0 0
  #|9 0 0   3 0 5   0 0 1
  #|0 0 1   8 0 6   4 0 0
  #|
  #|0 0 8   1 0 2   9 0 0
  #|7 0 0   0 0 0   0 0 8
  #|0 0 6   7 0 8   2 0 0
  #|
  #|0 0 2   6 0 9   5 0 0
  #|8 0 0   2 0 3   0 0 9
  #|0 0 5   0 1 0   3 0 0

test {
  inspect(
    Grid::parse(grid2).format(),
    content=
      #| 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 : Grid[@immut/sorted_set.T[Char]]
) -> Grid[@immut/sorted_set.T[Char]]? {
  if values.contains(fn(digits) { not(digits.size() == 1) }) {
    let mut minsq = ""
    let mut n = 10
    for sq in squares {
      let len = values[sq].size()
      if len > 1 {
        if len < n {
          n = len
          minsq = sq
        }
      }
    }
    for digit in values[minsq] {
      let another = values.copy()
      if assign(another, minsq, digit) {
        let temp = search(another)
        match temp {
          None => continue
          Some(v) => return Some(v)
        }
      }
    } else {
      return None
    }
  } else {
    return Some(values)
  }
}

fn solve(g : String) -> String {
  match search(Grid::parse(g)) {
    None => "can't solve \{g}"
    Some(v) => v.format()
  }
}

我们运行一个来自 magictour （一个困难数独谜题列表，对人类来说并不容易）的例子

let grid1 =
  #|4 . .   . . .   8 . 5
  #|. 3 .   . . .   . . .
  #|. . .   7 . .   . . .
  #|
  #|. 2 .   . . .   . 6 .
  #|. . .   . 8 .   4 . .
  #|. . .   . 1 .   . . .
  #|
  #|. . .   6 . 3   . 7 .
  #|5 . .   2 . .   . . .
  #|1 . 4   . . .   . . .

test {
  inspect(
    solve(grid1),
    content=
      #| 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 吧！

本教程参考了 Norvig 的博客：http://norvig.com/sudoku.html

数独求解器

目录

数独求解器#

方格、单元和同级#

预处理网格#

搜索#

总结#