さくさく理解する Godot 入門（ただし2Dに限る）応用編ナンプレ（数独）基本問題自動生成【第2回】

解答パターン生成(後半)

以下に、gen_ans_sub(ix, line_used) の実装コードを示す。

func gen_ans_sub(ix : int, line_used):  # ix: 次のセル位置、line_used: 現在行の使用済み数字ビット
    var x : int = ix % N_HORZ           # x 座標取得
    if x == 0: line_used = 0            # 左端なら line_used（現在行の使用済み数字ビット）をクリア
    var x3 = x / 3
    var y3 = ix / (N_HORZ*3)
    var bix = y3 * 3 + x3               # 3x3ブロックインデックス計算
    var used = line_used | column_used[x] | box_used[bix]       # 使用済み数字ビット計算
    if used == ALL_BITS: return false       # 全数字が使用済み → 行き詰まり
    var lst = []    # 入力可能数字ビット配列
    var mask = BIT_1            # セルに入れる数字ビット候補
    for i in range(N_HORZ):
        if (used & mask) == 0: lst.push_back(mask)      # 数字未使用の場合
        mask <<= 1
    if ix == N_CELLS - 1:       # 最後のセルの場合
        cell_bit[ix] = lst[0]   # 入れる数字は lst 先頭にあるはず
        return true             # 解答生成完了
    if lst.size() > 1: lst.shuffle()    # 入力可能数字ビット配列をシャフル
    for i in range(lst.size()):         # 入力可能数字ビットを順に試す
        cell_bit[ix] = lst[i]           # セルに数字を入れる
        column_used[x] |= lst[i]        # 使用済み数字ビット更新
        box_used[bix] |= lst[i]
        if gen_ans_sub(ix+1, line_used | lst[i]):   # 再帰コール
            return true                 # 解答生成完了の場合
        column_used[x] ^= lst[i]       # 使用済み数字ビットを元に戻す
        box_used[bix] ^= lst[i]
    cell_bit[ix] = 0            # 現セルを空に戻しておく（念の為）
    return false;

第1引数の ix は次に数字を入れる場所を示し、第2引数の line_used は現在行で使用済み数字のビット列を持つ。

最初に、ix からx座標と3×3ブロックのインデックスを計算し、ix位置に関係してすでに使われている数字ビットを used に入れる。 used == ALL_BITS であればすべての数字が使われていることになるので、行き詰まりとして false を返す。
次に未使用数字のビットを分解し、lst 配列に格納する。
ix が盤面最後の位置であれば、未使用数字がひとつだけのはずなので、それを ix に入れ、true を返して探索を終了する。
そうでなければ、lst をシャフルする。これは常に小さい数字から先に入れていくと解答が偏ってしまうから、それを避けるためだ。
i を for 文でまわして、ix 位置に lst[i] を格納し、カラムと3×3ブロックの使用済み数字を更新し、自分自身を再帰コールする。もし true が返ってくれば、解を見つけたということなので、その時点で true を返す。そうでなければ使用済みビットを元に戻す。
for 文が終了すると、解答が見つかっていないということなので false を返す。

ソルバーとユニーク解チェック

問題が与えられた時、その解を探索するプログラムを「ソルバー」と呼ぶ。
9×9盤面サイズのナンプレは意外と探索空間が小さく、単純なバックトラッキングでも短い時間で解を得ることができる。
ソルバーを問題自動生成のどこで使うのだ？と疑問に思う読者もいるかもしれないが、実はいっさい使わない。じゃあなぜ解説するかというと、ソルバーをちょっとだけ修正するだけでユニーク解チェックになるからだ。

というわけで、ソルバーのコードを以下に示す。

const N_CELLS = 9*9     # 盤面セル数
var cell_bit = []          # 盤面配列
func _ready():          # 初期化関数
    cell_bit.resize(N_CELLS)   # 盤面サイズ設定
    cell_bit.set_quest("..8516（略）56..")     # 盤面に問題設定
    solve(0)            # 最初から探索
func solve(ix) -> bool: # 解を発見した場合は true を返す
    if ix == N_CELLS:
        return true     # 解発見
    if cell_bit[ix] が空欄でない場合:
        return solve(ix+1)      # 次のセル位置で探索
    else:
        for n in range(1, 9+1):     # １～9
            if cell_bit[ix] に n を入れても重なりが無い:
                cell_bit[ix] = 1<<(n-1)     # 数値→数字ビット変換
                if solve(ix+1):
                    return true     # 解発見の場合
        cell_bit[ix] = 0   # cell_bit[ix] を空欄に
    return false        # 解未発見の場合

処理内容は解答パターン生成に比較的似ている。solve(ix) が順に解を求めていくバックトラッキングを行う再帰関数だ。第1引数に次の場所を持つのも一緒だ。

最初に、盤面に全部数字を入れ終わったかを判定し、そうであれば解発見したことになるので true を返す。
後の処理も単純で、1～9を順に盤面のix位置に入れていき、重なりがなければ ix をひとつ進めて自分自身を再帰コールしている。 for 文が終了した場合は、解が発見できなかったということなので false を返している。

問題生成においては、与えられた問題の解が欲しいのではなく、ランダムに作った問題がユニーク（一意）な解を持つかどうかをチェックする必要がある。
ナンプレのように条件が与えられ、それを満たす解を求める問題を「制約充足問題」と呼ぶ。
制約充足問題では、解が無い問題は文字通り問題外で、解が複数ある問題も適切な問題ではないとされている。

解がユニークかどうかをチェックするには、ソルバーを少し修正するだけでよい。
具体的には、解がひとつ見つかっても、そこで探索を終了せずに探索を続け、解の個数をカウントする。
探索の途中で２つ目の解を発見した場合は、解がユニークでないことが確定なので、そこで探索を終了する。

ユニーク解チェックのコードを以下に示す。

const N_CELLS = 9*9     # 盤面セル数
var nAnswer = 0
var cell_bit = []          # 盤面配列
func _ready():          # 初期化関数
    cell_bit.resize(N_CELLS)   # 盤面サイズ設定
    cell_bit.set_quest("..8516（略）56..")     # 盤面に問題設定
    nAnswer = 0
    is_proper(0)            # 最初から探索
func is_proper(ix) -> bool: # 複数解を発見した場合は false を返す
    if ix == N_CELLS:   # 解発見
        nAnswer += 1    # 解個数インクリメント
        return nAnswer < 2      # 解を複数発見した場合は false を返す
    if cell_bit[ix] が空欄でない場合:
        return solve(ix+1)      # 次のセル位置で探索
    else:
        for n in range(1, 9+1):     # １～9
            if cell_bit[ix] に n を入れても重なりが無い:
                cell_bit[ix] = 1<<(n-1)     # 数値→数字ビット変換
                if !is_proper(ix+1):
                    return false     #複数の解を発見した場合
        cell_bit[ix] = 0   # cell_bit[ix] を空欄に
    return true         # 解探索を継続

コードはソルバーのそれとほとんど同じだ。nAnswer という変数を用意し、それで解の個数をカウントしている。解をひとつみつけても処理を継続し、nAnswer が2になった時点で false を返し、処理を終了する。