電子情報工学特別実験 (森研究室) 制約充足問題を解くプログラムの作成 '93 --- パズル「イラストロジック」を解こう --- 解説編 森辰則 一部のＭ１の方に院実験の課題として出題しました「イラストロジック解法プ ログラム」ですが，締切を半月ほどすぎましたので，ここで総評をしてみたい と思います．興味のある方は読んでくださいね． まず，知らない方のために，イラストロジックあるいはお絵書きロジック，の のぐらむなどと呼ばれるこのパズルについて簡単に説明しておきます．以下の 例題を見てください． 　　　　┏━━┳━━━━━┓　　　┏━━┳━━━━━┓ 　　　　┃　　┃１１５１３┃　　　┃　　┃１１５１３┃ 　　　　┃　　┃３１　１１┃　　　┃　　┃３１　１１┃ 　　　　┣━━╋━━━━━┫　　　┣━━╋━━━━━┫ 　　　　┃３１┃・・・・・┃　　　┃３１┃■■■□■┃ 　　　　┃１１┃・・・・・┃　　　┃１１┃□□■□■┃ 　　　　┃　５┃・・・・・┃　　　┃　５┃■■■■■┃ 　　　　┃１１┃・・・・・┃　　　┃１１┃■□■□□┃ 　　　　┃１３┃・・・・・┃　　　┃１３┃■□■■■┃ 　　　　┗━━┻━━━━━┛　　　┗━━┻━━━━━┛ 　　　　　　　　例題　　　　　　　　　　　解答 左に示されている数字付きの盤面がこのパズルの問題です．各行または列につ けられている数字はそれぞれ対応する塗りつぶしの長さ(黒のランレングス)を 表しています．数字の順番には意味があって，その順に対応するランが現れな ければなりません．また，それぞれのランは隣接してはいけません．隣接する とさらに長いランになってしまうからです．ここでは，この数字のことを「鍵」 と呼ぶことにします．例えば，長さ5の行に対して[3,1]という鍵が付加されて いる場合には以下の解しかありません． ■■■□■ このように各行・列に付加されているすべての鍵を満足するように盤面を埋め ていくことがこのパズルの解になります．先ほどの例題では同図右が解になり ます． さて，このパズルをプログラムにより解こうというのが課題でした．どのよう な解法がされたかを次に述べてみましょう．（もちろんプログラムができるこ とを確認するためにぼくもつくりましたが，それはあとで述べます） 基本的なアルゴリズムとしては以下の３タイプに分類されました．これはぼく の予想通りでした． １．全解探索による生成検査型アルゴリズム 1人 これは， (1-a) すべての行(もしくは列)の鍵を満足する候補を一つ生成する． (1-b) それがすべての列(もしくは行)の鍵を満足するかどうかを検査する． もし満足するならば解を得たことになる． もし満足しないならば，(1-a)に戻る． というものです．この方法はアルゴリズムが簡単かつ直観的なのですが，問題 の規模が大きくなると計算量の爆発が起こります．この方法を採った人のプロ グラムは問題１について５分ほどかかってます． 残りの二つの方法の基本アルゴリズムは同じでだいたい以下のようになります (各プログラムの細かいところはフォローしきれていませんが)． (2-a) 盤面を初期化する． (2-b) 行もしくは列を選択する． (2-c) 盤面上で現在決定されている状態のもとで鍵を満足する様に(2-b)で選 択した行もしくは列の状態を更新する． (2-d) (2-c)の操作により盤面の状態が変化したかを検査する． 変化している場合は，(2-b)に戻る． 変化していない場合は，終了． (2-b)の行列の選択はなくてもよいのですが，直前の更新で変化を受けたとこ ろだけを選択するようにしたほうが効率が向上します．二つの方法において違 いがでるのは，(2-c)の部分です．この部分のアルゴリズムとしては以下の二 つがありました． ２．ヒューリスティックを用いる方法 ８人 ３．選択された行または列について全解探索を行い論理積をとる方法　２人 ２のヒューリスティックを用いる方法の人が一番多くいました．ヒューリスティッ クは発見的手法と翻訳されるように一般解を求めるものではないがある局面で は解を求めるのに有効な方法を指します． 以下に実際に用いられたヒューリスティックについて挙げておきます．ただし， ぼくなりにアレンジしてありますので，実際にＭ１のみなさんが使われたもの とは少し異なる部分もあります． (H1)ランの移動できる範囲から必ず埋まるマスを求めることができる場合がある． (H1-a) すでに決まっているマスがなければ，ランの移動できる最初の位 置と最後の位置においてランの重なっている部分が塗りつぶせる． 例) 長さ7の行に 2,3 という鍵が与えられているとすると，2のランに ついては，3のランを一番右に寄せておいて， 2,3 ・・・・・・・ ■■ ×○○○ ■■×○○○ より， 2,3 ・■・・・・・ が決定できます．同様に3のランも行うと最終的には， 2,3 ・■・・■■・ と決定できます． 移動できる範囲はすでに決まっているマスにより制限を受けるのでこれも 考慮します．例えば， (H1-b) 列もしくは行の先端(後端)に塗りつぶしが有るときには，最初(最 後)の鍵からえられるランをそこに固定できその次(前)のマスは空 白になる． (H1-c) 塗りつぶしに空白が隣接しているときには，その塗りつぶしに対 応可能な鍵のうち一番小さい数の長さだけのランを空白に隣接し て構成できる． (H1-d) 未定マスを挟むランは接続され，大きなランになる可能性がある が，そのようなランが存在しえない場合は間に空白が少なくとも 一つ入る． (H2)ランの移動できる範囲から必ず空白になるマスを求めることができる場合がある． (H2-a) 決定されたランの両端は空白になる． 例) 2,3 ・■・・■■■ ならば 2,3 ・■・□■■■ と決定できる (H2-b) (H1)の適用において絶対にランが移動しないマスがあれば，そこ は空白になる． ヒューリスティックを用いる方法は，探索をする方法に比べて計算量が少なく てすむという利点があります．いくつかのヒューリィスティックを適切に組み 合わせることによりほとんどの問題を解くことができることは経験的にわかっ ております．ただし，以下に述べる方法のように理論的に必ず解が求められる ことがわかっているわけではありません． ３の方法は各行列について全解探索を行いその解の論理積を求めるというもの です．これにより何がわかるかというと現在の盤面の状態で「必ず塗りつぶせ るマス」がわかります(塗りつぶしを１，空白を０と考えてください)．ただし， これでは空白の位置についてはでませんので，「鍵をすべて満足した行，列の 残りのマスは空白」という規則を用いているようです． この方法はある行の情報を全てつかうことが理論的に可能ですが(後に述べる ぼくの方法のように直さなければなりませんが)，解を求める行もしくは列の 選択を上手に行わないと，効率がわるくなります．たとえば，ほとんど盤面が 埋まっていない状態で解の数が多い行を選択するのは避けるべきでしょう． ぼくの採った方法は基本的には３ですが，いくつか工夫をしています． まず，盤面の更新の部分が以下のようになっています． ３'．選択された行もしくは列について現在の盤面の状態のもとで全解探索を 行い(基本的にはここまでは同じ)，(論理積を取るのではなく)その解の 一般化を行う． 一般化というのはそれぞれのマスにおいて， 全ての解について塗りつぶし(１) → 塗りつぶし(１) 全ての解について空白(０) → 空白(０) それ以外 → 未定(現在の情報では決まらない) という更新を行うことです．つまり，全ての解を満足する最も特殊な解を求め るわけです．これによりある行もしくは列の状態の情報と鍵の情報を完全につ かうことができます． それから，行もしくは列の選択において，まず，解の候補の数の少ない順にソー トしてからその順番に一つづつ考慮する行または列を増やして行きます．考慮 する行もしくは列を増やすタイミングは考慮している行もしくは列のに変化が 起こらなくなった場合です．こうすることにより，各行の探索量をかなり減ら すことができ，やらない場合と比較すると実行時間にかなりの差がでます．な お，各行,列において盤面に何も置かれていないときの解の数は簡単に正確な 値が計算できます．(簡単な組み合わせ問題です) また，ある行もしくは列の状態を仮定して盤面の決定を行う探索モードも取り 入れています．この探索に関しては何人かの人が言及していましたが，実際に プログラムに組み入れている人はいませんでした．出題した問題では探索が必 要にならなかったためだと思われます．しかし，実際には(2-a)〜(2-d)のアル ゴリズムでは解けない問題があることがわかっています．たとえば，以下の問 題(ソニーの野村氏作)は，解がユニークに決まりますが，(2-a)〜(2-d)のアル ゴリズムでは解けません．やってみてください． 　　　　┏━━┳━━━━┯━━━━┯━━━━━┓ 　　　　┃　　┃１１３２│１２２１│２２３３１┃ 　　　　┃　　┃２２　　│　　　　│　　　　　┃ 　　　　┣━━╋━━━━┿━━━━┿━━━━━┫ 　　　　┃３３┃■■■□│□□□□│□□■■■┃ 　　　　┃２２┃□□■■│□□□□│□□■■□┃ 　　　　┃２２┃□□■■│□□□□│□□■■□┃ 　　　　┃２２┃■■□□│□□□□│■■□□□┃ 　　　　┃２２┃■■□□│□□□□│■■□□□┃ 　　　　┠──╂────┼────┼─────┨ 　　　　┃２　┃□□□□│□■■□│□□□□□┃ 　　　　┃４　┃□□□□│■■■■│□□□□□┃ 　　　　┗━━┻━━━━┷━━━━┷━━━━━┛ この種の問題は探索モードをいれれば解けます．探索のやり方ですが，これは， １のアルゴリズムのようにやると探索空間が爆発するのは明かですから，次の ようにします．(2-a)〜(2-d)までを resolv という名前で定義しておきますと， (s-0) resolvを実行 search (s-1) 未定のマスがあるか？ なければ解が求まっているので終了．あれば次のステップへ． (s-2) 未決定のマスのある行もしくは列を一つ選択する． (s-3) その行もしくは列に対して現在の状態において鍵を満足する解 を一つ生成する． (s-4) その行もしくは列に対してその解を仮定して，resolv を実行 する． (s-5) 矛盾なく解を求めることができれば，search を再帰的に実行． 矛盾があれば，(s-3)に戻る(バックトラック)． というアルゴリズムで全ての場合が解けます． さて，実際に解かれた問題ですが，４題出題した問題を全て解いた人は一人で した．ほとんどの人は必須問題の１だけでした．ということで，例の懸賞問題 を解いた人はいませんでした．懸賞問題を解いたのを確認したのは実験とは直 接関係ない有澤研のＭ２の石川くんのプログラムとぼくのプログラムだけです． 石川くんのプログラムはヒューリスティック型で探索モードも入ってますので， ぼくのプログラムと同様おそらく全ての問題が解けるでしょう．しかもヒュー リィスティックによるのでぼくのプログラムよりも高速です． ということで，以上，森研究室大学院実験の報告でした． あ，そうだ，ぼくのプログラムを使ってみたいという人がひょっとするといる かも知れませんので(実際に学外の何カ所かにも配布している)，anonymous FTP できるようにしておきます． ftp.forest.dnj.ynu.ac.jp:/misc/IllustLogic/il-mori.tar.gz /doc/MExperiment/93/il-mori.tar.gz にキットを置いておきます．詳しくは各ファイルの先頭を読んでください．各 種ツールもついています．探索モードがついているので，オリジナルの問題を つくるときにも利用できます．