ホームページへ戻る 開発ノートメニューへ戻る
お絵かきロジックを解く

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

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

(1)重なりを調べる

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

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


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

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


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

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

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

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

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

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

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

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

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

ホームページへ戻る 開発ノートメニューへ戻る