mate法を用いた Numberlink 問題自動生成
3-Jly-2016
概要
mate法を用いて、ナンバーリンクパズルの問題を自動生成するプログラマムを実装してみた。
（高度な枝刈りを行わない単純な）バックトラッキングに比べ、かなり高速な処理が実現でき、
バックトラッキングでは 5x5 までの問題自動生成が限度だったのが、
PCでは 9x9 まで、タブレットでは 8x8 まで、リアルタイム（0.5秒程度以下）な問題生成が可能になった。
背景
- ナンバーリンク（Numberlink, Flow）は同じ数字同士を線でつなぐペンシルパズル
- ※ 「ナンバーリンク」は Nikori の登録商標
- 参照：ナンバーリンク, Numberlink
- 問題例：
┌─┬─┬─┬─┐ │１│ │ │２│ ├─┼─┼─┼─┤ │３│ │ │３│ ├─┼─┼─┼─┤ │ │１│２│ │ ├─┼─┼─┼─┤ │ │ │ │ │ └─┴─┴─┴─┘
┌─┬─┬─┬─┐ │１┿┓│┏┿２│ ├─┼╂┼╂┼─┤ │３│┃│┃│３│ ├╂┼╂┼╂┼╂┤ │┃│１│２│┃│ ├╂┼─┼─┼╂┤ │┗┿━┿━┿┛│ └─┴─┴─┴─┘
┌─┬─┬─┬─┬─┬─┬─┬─┬─┐ │ │ │ │ │２│ │ │ │１│ ├─┼─┼─┼─┼─┼─┼─┼─┼─┤ │ │３│ │ │ │ │ │１│２│ ├─┼─┼─┼─┼─┼─┼─┼─┼─┤ │ │ │ │ │ │４│ │ │ │ ├─┼─┼─┼─┼─┼─┼─┼─┼─┤ │７│ │ │５│ │ │ │ │ │ ├─┼─┼─┼─┼─┼─┼─┼─┼─┤ │ │ │ │ │ │ │ │ │ │ ├─┼─┼─┼─┼─┼─┼─┼─┼─┤ │６│ │ │４│ │ │ │ │３│ ├─┼─┼─┼─┼─┼─┼─┼─┼─┤ │ │ │ │ │ │８│ │ │ │ ├─┼─┼─┼─┼─┼─┼─┼─┼─┤ │ │８│ │ │ │ │ │７│ │ ├─┼─┼─┼─┼─┼─┼─┼─┼─┤ │ │ │ │ │ │６│５│ │ │ └─┴─┴─┴─┴─┴─┴─┴─┴─┘
- 矩形盤面にある同じ数字同士を線でつなぐ
- 線は縦横方向のみ
- セルで、90度方向転換可能
- ひとつのセルには１つの線のみ必須
- 通常はユニーク解を持つもののみが問題となる
- が、セル数に対して処理時間が指数関数的に増大する
- 数字をランダムに配置し、それがユニークな解を持つかどうかチェックすることで可能。
- だが、セル数が増えると、処理時間が指数関数的に増大し、実時間での問題生成が不可能
バックトラッキング ソルバー
- 空欄は ━ ┃ ┏ ┓ ┗ ┛ の6種類の可能性
- 数字のあるセルは上下左右の4種類の可能性
- バックトラッキング（DFS）により解探索を行うことができる
- 状態を決めていく順番は 行→列 の順が自然で、コーディングが楽
- 対角線状の順番の方が枝刈りが発生しやすく高速という説がある（未確認）
- 分岐数を5、セル数を N とすれば、探索全ノード数は 5^N
- セルの状態を決めるときに、リンクの接続性をチェック可能なので、実際には 2^N 程度
- それでも 10x10 の盤面で 2^100 = 1.27*10^30 となってしまい、実用的ではない
- 空欄のみでのループチェック、同じ数字がリンクされているかなどのチェックをいつ行うか？
┌─┬─┬─┬─┐ │┏┿┓│１│２│ ├╂┼╂┼╂┼╂┤ │┗┿┛│┃│┃│ ├─┼─┼╂┼╂┤ │２┿━┿┛│┃│ ├─┼─┼─┼╂┤ │１┿━┿━┿┛│ └─┴─┴─┴─┘
- セルの状態を決めるときに毎回チェック？ → チェックコストが大きい
- 全セルを埋めたときにチェック？ → 枝刈りが起こらない
- 単純なのは後者
int g_count = 0;
void solve(int ix) { // 位置
if( ix が矩形外 ) {
if( 空ループ、異なる数字をリンクしていない )
++g_count;
return;
}
if( ix 位置に数字がある ) {
if( 上方向に連結可能 ) {
ix から上方向にリンク;
solve(ix+1);
}
左・右・下方向についても同様の処理;
} else {
if( ━ のそれぞれが設置可能 ) {
それを配置;
solve(ix+1);
}
┃ ┏ ┓ ┗ ┛ についても同様の処理;
}
}
単純な問題自動生成アルゴリズム
- セル数をN、配置する数字の種類数を √(N) - 1 とする
- ランダムに数字を配置し問題候補とする
- ソルバーでその問題がユニーク解を持つかどうかをチェック
- セル数が増えると、ランダム配置問題候補がユニーク解を持つ確率は急激に低下
- 単純な問題自動生成アルゴリズム：
for(;;) {
盤面に数字をランダムに配置
if( 盤面がユニーク解を持つ )
break;
}
mate法
- 問題候補がユニーク解を持つかどうかを判定したいだけ
- 解を具体的に求める必要は無い → 高速化の可能性がある
- Knuth が提案した Simpath アルゴリズム で採用された mate 配列を用いることで実現できる
- mate配列：
- 各セルの結合状態を保持する配列
- i番目のセルの結合先を mate[i] で保持する
- リンクの途中の場合は 0 を値とする（0 はセル番号としてありえない値とする）
- どこにも接続していないセルは mate[i] == i となる
- セル番号例（4x4）：
①②③④ ⑤⑥⑦⑧ ⑨⑩⑪⑫ ⑬⑭⑮⑯
┌─┬─┬─┬─┐
│┏┿━┿┓│１│ ← この行まで処理した場合
├╂┼─┼╂┼╂┤
│ │ │ │ │
├─┼─┼─┼─┤
│ │ │ │ │
├─┼─┼─┼─┤
│ │ │ │ │
└─┴─┴─┴─┘
mate[] ： {0, 0, 0, 8, 7, 6, 5, 4}
- 数字があるかどうかで処理を分ける
- すべての可能な状態を生成する
- 最後の４つの要素のみを保持していればよい
- 可能な mate配列集合をハッシュで管理する
- mate配列の組み合わせ数をカウントしておく
- mate配列集合が空になった場合は解無し
- 後戻りを行わない。→ O(N)
結果・考察
- 処理時間計測結果は下図のとおり
- X軸はセル数、Y軸は処理時間（の対数）
- バックトラッキングは指数関数時間を要するが、mate法は多項式時間で処理することができた
- mate法はそれなりに重い
- 少ないセル数では、単純なバックトラッキング法の方がむしろ高速
- バックトラッキングは深さ優先探索、mate法は幅優先探索に相当する
まとめ
- mate法を用いることで、9x9までのナンバーリンク問題自動生成に成功した
- mate法は真に必要な情報だけをメモリに置くことで、探索を高速化する手法だ
- さらなる高速化を行い、10x10以上の問題もリアルタイム時間で生成可能にしたい
宣伝
本稿のアルゴリズムを使用して問題を作成したパズルをリリースしてるよ。
ここ からダウンロードできるので、よかったら遊んであげてね。
