ホームページへ戻る
お絵かきロジック(ののぐらむ)

　「確定探索付き再帰」を用いて雑誌系定番パズルの「お絵かきロジック」を解いてみます。自力で何問か解いてみると基本的な解き方のテクニックが見えてくるので、それを「確定探索」に使用するために先ずそれを説明します。その後に全体の探索システムを組み上げてみます。

　■１次元のモデルで確定探索部を作る

　このパズルの基本的な解法は、縦列・横列それぞれの１列だけに着目したアプローチです。
縦列で確定した情報は横列の確定探索に影響を与えるという互いの相乗効果が連鎖的に働きます。(制約伝播)

（１）重なりを調べる

　わざわざ説明するまでも無い基本技として、[■の塊]を矛盾なく出来るだけ左に寄せた場合と、出来るだけ右に寄せた場合との間で同一の■や×の塊が重なり合う部分は確定できます。
　この方法は、一回の工程で多くのマス目を確定できてしまう場合が多いので大変に有効な確定探索と言えます。ただし、「出来るだけ端に寄せる」という行為は自力で解く場合は楽なのですが、プログラムにすると結構面倒です。

（２）背理法を用いる
　「ある仮定によって矛盾した結果が導き出される時、最初の仮定は否定される。」という背理法を用いると、重なりを調べただけでは検出できない「実際は確定出来る場所」も確定することが出来ます。
　つまり、ある未確定のマスを■と仮定して矛盾した結果が出たら×に確定できます。未確定のマス一つ一つに行うのでちょっと処理が重くなりますが、矛盾した結果が導き出されるかのチェックは、上の「出来るだけ端に寄せる」という処理をそのまま流用出来る為、是非採用しておきたい確定探索です。

　■確定探索付き再帰の型枠に組込み

　さて、確定探索部は出来ました。後は「確定探索付き再帰」の型枠に組込むだけですが、ちょっと待って下さい。
　確定探索が２つあります。また、マス目が多いので再帰によるスタックオーバーも心配です。

　(a) 確定探索が複数あるときは、処理の軽い方を優先して実行されるように積み上げます。(この場合は重なり探索)
　　　そして、重い方の確定探索で１つでも新事実が発見されたら直ぐに軽い方へ移行するようにしておきます。
　(b) スタック処理は配列変数をグローバルで確保して、プログラム内で制御するようにします。


　int スタックテーブル[総マス目数]; /* 着手したマス目位置を記録 */

　int 重なり探索()
　{
　    do {
　        重なり探索を実行し確定着手をスタックテーブルに記録;
　        if (重なりの探索 == 矛盾あり) return 矛盾あり;
　    } while (重なり探索で着手更新あり);
　　   return 矛盾なし;
　}

　int 背理法探索()
　{
　    do {
　        if (重なり探索() == 矛盾あり) return 矛盾あり;

　        背理法探索を実行し確定着手をスタックテーブルに記録;
　        if (背理法の探索 == 矛盾あり) return 矛盾あり;
　    } while (背理法探索で着手更新あり);
　    return 矛盾なし;
　}

　void 再帰探索()
　{
　    現在のスタック位置を待避;

　    if (背理法探索() == 矛盾なし) {

　        未確定位置を１つ探す;
　        if (総て確定済み) {
　            解の記録;
　        } else {
　            for (×〜■) {
　                仮定着手;
　                再帰探索();
　                仮定戻す;
　            }
　        }
　    }

　    待避したスタック位置まで確定着手を戻す;
　}

　void main()
　{
　    再帰探索();
　}

　■お絵かきロジックを解く for Windows Ver2

　実行環境
　Windows
　ダウンロード
　logic.zip　(25K Byte / 圧縮版)
　インストール方法
　このソフトは「logic.exe」というファイル１つだけで動きますので、特にインストール作業は必要ありません。
　はじめに (サンブルデータ)
　サンプル問題が既にあります。[START]ボタンをクリックしてみて下さい。解を表示するはずです。
新たに問題を入力する時は[CLEAR]ボタン。

どんな難問でも、必ず答えが出ます。

問題の入力の仕方
・ 水色の■部分が入力位置です。[数字ボタン]をクリック、または、キーボードから数字を入力します。
・ マウス入力の場合は入力位置が自動的に次の位置(外側)へ移動します。
　 キーボード入力の場合はカーソルキーで移動します。
・ マウスクリックで直接入力位置を指定することも出来ます。

入力が終わったら
・ 上ブロックと左ブロックの合計カウンタが同じでなければなりません。
・ 違っていたら入力にミスがあります。
・ [START]ボタンで探索を開始します。
ホームページへ戻る