数独ソルバー#
数独は、1979 年に生まれた論理パズルゲームです。新聞のような印刷媒体と相性がよく、デジタル時代の今でも、コンピュータやスマートフォン向けに多くの数独プログラムがあります。今日では娯楽の選択肢が多様になっていますが、数独愛好家は今なお活発なオンラインコミュニティを形成しています。この記事では、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| |
---------+---------+---------
| |
| |
| |
---------+---------+---------
| |
| |
| |
ピア同士の 2 つのマスに同じ数字を入れることはできません。
81 個のマスと各マスに関連する情報を保存するために、Grid[T] というデータ型が必要です。これはハッシュテーブルでも実装できますが、配列を使う方がコンパクトで単純です。まず、A1-I9 の座標を 0-80 の添字に変換する関数を書きます。
// A1 => 0, A2 => 1
fn square_to_int(s : String) -> Int {
if s is [('A'..='I') as a, ('1'..='9') as b, ..] {
let row = a.to_int() - 'A'.to_int() // 'A' <=> 0
let col = b.to_int() - '1'.to_int() // '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"] = ... のような便利なコードを書けます。
///|
struct 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.0.length() == 0 {
return []
}
let arr = FixedArray::make(81, self.0[0])
let mut i = 0
while i < 81 {
arr[i] = self.0[i]
i = i + 1
}
return arr
}
///|
#alias("_[_]")
fn[T] Grid::at(self : Grid[T], square : String) -> T {
let i = square_to_int(square)
self.0[i]
}
///|
#alias("_[_]=_")
fn[T] Grid::set(self : Grid[T], square : String, x : T) -> Unit {
let i = square_to_int(square)
self.0[i] = x
}
次に、いくつかの定数を用意します:
let rows = "ABCDEFGHI"
let cols = "123456789"
type Squares = @immut/sorted_set.SortedSet[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] = ......
units と peers の表を構築する処理は煩雑なので、ここでは詳しく扱いません。
盤面の前処理#
初期の数独盤面は文字列で表します。形式はさまざまでも構いません。. と 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']（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 つのマスに同じ数字は入れられないからです。戦略 2: あるユニットの中で、特定の数字を入れられるマスが 1 つしかない場合（これは上の規則を何度か適用した後に起こりえます）、その数字はそのマスに割り当てるべきです。
コードを調整するために、あるマスの候補値から数字を取り除く eliminate 関数を定義します。消去処理を行ったあと、この関数は key と val に対して上記の戦略を適用し、さらに消去を進めようとします。なお、矛盾の可能性を扱うために真偽値を返す点に注意してください。あるマスの候補値リストが空になってしまったら、どこかで破綻しているので false を返します。
fn eliminate(
values : Grid[@sorted_set.SortedSet[Char]],
key : String,
val : Char
) -> Bool {
if !(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].length() {
1 => {
let val = values[key].min()
let mut res = true
for key in peers[key] {
res = res && eliminate(values, key, val)
}
if !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.length() {
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[@sorted_set.SortedSet[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
}
この 2 つの関数は、アクセスする各マスに対してヒューリスティック戦略を適用します。戦略がうまく働くと、新たに検討すべきマスが生まれ、それによって戦略が盤面全体へ広く伝播していきます。これが無効な候補を素早く取り除く鍵です。実際、この前処理だけで解ける簡単な数独もあります。
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）であり、assign と eliminate が特化したアーク整合性アルゴリズムであることに気づくかもしれません。この話題について詳しくは、Artificial Intelligence: A Modern Approach の第 6 章を参照してください。
探索#
前処理のあとでは、実行可能な組み合わせを探すために総当たり探索を大胆に使えます。ただし、探索の途中でもヒューリスティック戦略は引き続き利用できます。あるマスに値を割り当てようとするときにも assign を使うことで、これまでの最適化を適用し、多くの無効な分岐を探索中に取り除けます。
もう一つ注意すべき点は、探索中に衝突が起こりうることです（あるマスの候補値が尽きたときなど）。可変構造だとバックトラックが面倒になるため、ここでは値を割り当てるたびに直接コピーを作ります。
fn search(
values : Grid[@sorted_set.SortedSet[Char]],
) -> Grid[@sorted_set.SortedSet[Char]]? {
if values.contains(fn(digits) { !(digits.length() == 1) }) {
let mut minsq = ""
let mut n = 10
for sq in squares {
let len = values[sq].length()
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)
}
}
} nobreak {
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
#|
),
)
}
一般的な開発マシンでは、この数独を解くのにかかる時間は約 0.11 秒です。
まとめ#
ゲームの目的は、退屈を紛らわせ、楽しさをもたらすことです。ゲームを遊ぶことがワクワクすることより不安の原因になってしまうなら、それはゲームデザイナーの本来の意図に反しているかもしれません。この記事では、単純な消去法と総当たり探索だけでいくつかの数独を素早く解けることを示しました。これは数独に遊ぶ価値がないという意味ではなく、解けない数独にあまり思い詰める必要はない、ということを示しています。
気軽に MoonBit を楽しみましょう！
このチュートリアルは Peter Norvig の数独解法の記事を参考にしています。