9.2 Sudoku ソルバ
Game of lifeで使った、状態点を順にたどるのではなく状態集合を表す配列上の操作で一気に次状態集合を計算するという考え方が全く同じように使える別の例としてSudoku(数独)ソルバを考える。
幅優先探索版プログラム
まず参考にするのはAPLのオンラインREPL https://tryapl.org/ → 'LEARN'タブ → 'Sudoku Solver'である1。 手取り足取り説明してくれるのでそれを見ながら、BQNに直訳すると以下のようになる。
Box ← {>𝕩/<˘𝕩‿∘⥊𝕩/1+↕𝕩⋆2} # 盤面にブロック分割番号を割り当てる
RCB ← {(1+↕𝕩)∾¨Box⊑√𝕩} # row, column, blockの頭文字
Cmap ← {<˘˘1⊑∘∊¨=⌜˜𝕩}
Sudoku ← {
map ← Cmap RCB ≢𝕩
Avl ← {(1+↕⊑≢𝕩)(¬∘∊/⊣)0⊸≠⊸/⥊𝕩×𝕨⊑map}
Nxt ← {w 𝕊 x : (𝕨Avl𝕩){𝕨⌾(w⊸⊑)𝕩}¨<𝕩}
Nxtv ← {∾𝕨⊸Nxt¨𝕩} # (<s44)Nxtv´⟨0‿0,0‿1,1‿0⟩ のように呼び出す
>(<(Nxtv´)((0⊸=𝕩⊸(⊑˜))⊸/·⥊·↕≢))𝕩
}
説明
最初の3行はセル間の関係を作り出すための関数である。
4×4の盤面（従って出現する数字は1から4となる）に対するRCB 4‿4の計算結果を以下に示す。
RCB 4‿4
┌─
╵ ⟨ 1 1 1 ⟩ ⟨ 1 2 1 ⟩ ⟨ 1 3 2 ⟩ ⟨ 1 4 2 ⟩
⟨ 2 1 1 ⟩ ⟨ 2 2 1 ⟩ ⟨ 2 3 2 ⟩ ⟨ 2 4 2 ⟩
⟨ 3 1 3 ⟩ ⟨ 3 2 3 ⟩ ⟨ 3 3 4 ⟩ ⟨ 3 4 4 ⟩
⟨ 4 1 3 ⟩ ⟨ 4 2 3 ⟩ ⟨ 4 3 4 ⟩ ⟨ 4 4 4 ⟩
┘
各リストは順に横方向のグループ番号、縦方向のグループ番号、ブロック分割番号を要素として持つ。
次に4×4の盤面に対するmapを以下に示す。
map はセルが縦、横、ブロックのいずれかの観点から関係を持つかどうか(bool)を全てのセルに対して求めた配列である。
LifeNextでの全セルの近傍存在数の求め方と同じように配列の操作のみで全セルの関係セルを求めている。
Cmap Rcb ⟨4,4⟩
┌─
╵ ┌─ ┌─ ┌─ ┌─
╵ 1 1 1 1 ╵ 1 1 1 1 ╵ 1 1 1 1 ╵ 1 1 1 1
1 1 0 0 1 1 0 0 0 0 1 1 0 0 1 1
1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1
1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1
┘ ┘ ┘ ┘
┌─ ┌─ ┌─ ┌─
╵ 1 1 0 0 ╵ 1 1 0 0 ╵ 0 0 1 1 ╵ 0 0 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1
1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1
┘ ┘ ┘ ┘
┌─ ┌─ ┌─ ┌─
╵ 1 0 0 0 ╵ 0 1 0 0 ╵ 0 0 1 0 ╵ 0 0 0 1
1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 0 0 1 1 0 0 0 0 1 1 0 0 1 1
┘ ┘ ┘ ┘
┌─ ┌─ ┌─ ┌─
╵ 1 0 0 0 ╵ 0 1 0 0 ╵ 0 0 1 0 ╵ 0 0 0 1
1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1
1 1 0 0 1 1 0 0 0 0 1 1 0 0 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
┘ ┘ ┘ ┘
┘
例えば0‿0⊑mapの配列において値が1となっている添字のセルの集合中に同じ数が2回以上出現するなら添字0‿0のセルにおいてSudokuのルールが守られてないことを意味する。
逆にその中に出現していない数があれば(未割り当てならば)0‿0セルに割り当てることができる。
ということでこの操作を実行しているのがmap以降の4行になる。
実行例
s44 ← 4‿4⥊0‿0‿0‿0‿0‿0‿2‿1‿3‿0‿0‿4‿0‿0‿0‿0
s99 ← 9‿9⥊∾⟨
0‿0‿1‿6‿9‿0‿5‿0‿0
4‿0‿0‿2‿7‿0‿0‿0‿1
0‿7‿0‿0‿0‿0‿0‿9‿0
0‿0‿0‿0‿0‿0‿0‿3‿0
0‿0‿0‿4‿3‿0‿0‿0‿7
0‿0‿0‿7‿8‿0‿6‿0‿0
0‿0‿6‿0‿0‿0‿8‿0‿5
0‿2‿0‿1‿4‿0‿0‿6‿0
0‿1‿0‿3‿5‿0‿0‿4‿0
⟩
•Show Sudoku s44
┌─
╎ 2 1 4 3
4 3 2 1
3 2 1 4
1 4 3 2
┘
•Show Sudoku s99
┌─
╎ 2 8 1 6 9 3 5 7 4
4 6 9 2 7 5 3 8 1
5 7 3 8 1 4 2 9 6
7 9 2 5 6 1 4 3 8
6 5 8 4 3 9 1 2 7
1 3 4 7 8 2 6 5 9
3 4 6 9 2 7 8 1 5
9 2 5 1 4 8 7 6 3
8 1 7 3 5 6 9 4 2
┘
YouTubeにビデオも上がっているけど使い勝手が悪いのでは。
深さ優先探索版
次に、このプログラムをYouTubeのビデオを参考に深さ優先探索アルゴリズムに作り直したものが以下のプログラムである。
Box ← {>𝕩/<˘𝕩‿∘⥊𝕩/1+↕𝕩⋆2}
RCB ← {(1+↕𝕩)∾¨Box⊑√𝕩}
Cmap ← {<˘˘1⊑∘∊¨=⌜˜𝕩}
SudokuD ← {
map ← Cmap RCB ≢𝕩
Avl ← {(1+↕⊑≢𝕩)(¬∘∊/⊣)0⊸≠⊸/⥊𝕩×𝕨⊑map}
Nxt ← {w 𝕊 x : (𝕨Avl𝕩){𝕨⌾(w⊸⊑)𝕩}¨<𝕩}
ans ← ⟨⟩
{𝕊¨{0<≠p ← (0⊸=𝕩⊸(⊑˜))⊸/·⥊·↕≢𝕩 ? (⊑p)Nxt 𝕩 ; ans ↩ 𝕩 ⋄ !0}𝕩}⎊{𝕤 ⋄ ans}𝕩
}
説明
TODO
なお最初の解が見つかった時点でmapを強制に打ち切りたいので、Catch '⎊'を使っている。
元々は以下のように終了時の返値用のローカル変数を持たせていたが、関数終了時にローカル定数mapが壊れても問題なかろうということで簡略化した。
ans ← ⟨⟩
{𝕊¨{0<≠p ← (0⊸=𝕩⊸(⊑˜))⊸/·⥊·↕≢𝕩 ? (⊑p)Nxt 𝕩 ; ans ↩ 𝕩 ⋄ !0}𝕩}⎊{𝕤 ⋄ ans}𝕩
BQNプログラムに見る深さ優先探索と幅優先探索の対比
TODO: 以下への導出
2つの解法を得ることができたので両者がどれくらい似ているのか比較しよう。 編集距離をできるだけ近づけると以下のようになる。
Box ← {>𝕩/<˘𝕩‿∘⥊𝕩/1+↕𝕩⋆2}
RCB ← {(1+↕𝕩)∾¨Box⊑√𝕩}
Cmap ← {<˘˘1⊑∘∊¨=⌜˜𝕩}
Avl ← {map 𝕊 w‿x : (1+↕⊑≢x)(¬∘∊/⊣)0⊸≠⊸/⥊x×w⊑map}
Nxt ← {map 𝕊 w‿x : (𝕨 Avl 𝕩){𝕨⌾(w⊸⊑)𝕩}¨<x}
SudokuW ← {
map ← Cmap RCB ≢𝕩
{𝕊∾{0<≠p ← (0⊸=⊑⟜𝕩)⊸/⥊↕≢𝕩 ? map Nxt(⊑p)‿𝕩 ; map ↩ 𝕩 ⋄ !0}¨𝕩}⎊{𝕤 ⋄ map}<𝕩
}
SudokuD ← {
map ← Cmap RCB ≢𝕩
{𝕊¨{0<≠p ← (0⊸=⊑⟜𝕩)⊸/⥊↕≢𝕩 ? map Nxt(⊑p)‿𝕩 ; map ↩ 𝕩 ⋄ !0}¨𝕩}⎊{𝕤 ⋄ map}<𝕩
}
ということで、2つの探索アルゴリズムを並べるとご覧の通り。
| 手法 | 表現 |
|---|---|
| 幅優先 | 𝕊∾N¨ |
| 深さ優先 | 𝕊¨N¨ |
くそ美しいな！ BQNプログラマにとって幅優先はニョロ、深さ優先はチョンチョンなのだ2！
ただし、次に埋めるべきセルの位置は、最初の幅優先探索では状態集合ごとに1回のみの計算で済んでいたものがこのバージョンでは状態毎に（同じ）計算を繰り返すことになってしまっている。ちょっとここは目を瞑って欲しい。
golfの余地
最終版はそれぞれ本体が2行と大変短くなったが全く同じコード片を持つのでなんとかしたい。 同じ識別子が2回出現するなんてバカじゃねーの教徒的には。 しかし関数の中で親環境の変数に対する代入を行っているので
- 親を大域変数に格上げするか、
- 関数閉包生成式をTBC