さくさく理解する Godot 入門（ただし2Dに限る）応用編お絵かきパズル【第7回】

ソルバー

問題を解くプログラムを「ソルバー」と呼ぶ。本アプリには、問題を入力し解答を提示する機能は実装していないのだが、ユーザが問題を作成することが出来、作られた問題が解をひとつだけ持っている適切な問題かどうかをチェックする必要があり、そのためにソルバーを使用する。

■ラインソルバー

難しい問題を一度に解こうとするのではなく、部分問題に分けて解くのは、問題解決におけるよくあるテクニックのひとつだ。お絵かきパズルには行・列はたくさん（本アプリでは 15×15）あるのだが、まずは、1行または１列だけに着目する。 1行または１列だけであれば、いろいろ話が簡単になる。
１行または１列の手がかり数字だけを使って、行または列の解を求めるプログラムを「ラインソルバー」と呼ぶ。ただし、解がひとつだけとは限らないので、可能な解のリストを計算することになる。
で、このラインソルバーが実装できれば、それを使って２次元的にお絵かきパズルを解くことができる、という作戦だ。

ラインソルバーを解くために、単純な全探索を使うと、セル数がNであれば O(2^N) の処理時間を要してしまう。競技プログラミングで高速化のためによく使われる DP（動的プログラミング）テクニックを使うと、セル数に対して低いオーダー（おおよそ O(N)）で解を求めることができる。具体的なアルゴリズムについては、An Efficient Approach to Solving Nonograms などを参照していただきたい。
で、ソルバーはラインソルバーを縦横方向に繰り返し使用することで、解を探索していく。

だがしかし、本アプリではキャンパスが 15×15 とそう大きくないサイズで固定なので、DP のような高度なアルゴリズムを使うのではなく、手がかり数字の全パターン → 可能な解リストをあらかじめ計算し、辞書（ハッシュマップ）に保存しておくことにした。こうしておけば、O(1) の時間で手がかり数字から可能な解のリストを得ることができる。これは全パターンが 2^15 = 32768 しかないおかげだ。
ちなみに、20×20 の場合も同様の実装を行ってみたが、全パターンの計算を行うのに数秒を要し、実用に耐えなかった。

GDScript での辞書は非常に簡単で取り扱いやすい。辞書は波括弧 { } で表し、「var dict = {}」で空辞書を初期化できる。初期化時にキーと値を指定する場合は、{key1: val1, key2, val2, … } のように記述する。初期化後に「dict[key] = val」でキーに対応する値を設定したり、 dict[key] でキーに対応する値を参照できる。キー・値は整数・浮動小数点はもちろん、配列やオブジェクトも使用可能で、非常に柔軟性が高い。

下記のように、メンバ変数として g_map を定義し、 _ready() で、辞書を初期化する build_map() をコールする。

var g_map = {}      # 水平・垂直方向手がかり数字配列 → 候補数値マップ
func _ready():
    build_map()
    .....

build_map() の実装は下記の通り。

# key は連配列、下位ビットの方が配列先頭
func build_map():
    g_map.clear()
    for data in range(1<<N_IMG_CELL_HORZ):
        var key = data_to_clues(data)
        if g_map.has(key):      # すでにキーが登録されている場合
            g_map[key].push_back(data)      # データをそのキーに追加
        else:
            g_map[key] = [data]             # キーに対応するデータとして新規要素作成

for 文でビットパターンを回しながら、data_to_clues(data) で手がかり数字配列を取得し、それをキーに辞書に登録していくだけだ。ひとつの手がかり数字に対応する解はひとつとは限らないので、配列に解のリストを格納している。

data_to_clues(data) の実装は、本連載第３回「手がかり数字更新」の節を参照。
以上のコードで、build_map() 実行後には g_map[手がかり数字配列] で可能なビットパターン配列を O(1) で取得できるようになる。