鉛筆パズルの整数計画法による解法定式化集

                                                                         T.K.Oddzissan

定年で暇になった機会に、岡本吉央整数計画法によるパズル解法の演習問題を解いてみようと思い立ち、ついでに手近に見られる鉛筆パズルを解いてみることにした。途中で気が付いたが、知恵の輪パズル、キューブパズル攻略法(解法) - TOK2.com というのがあり、ほとんど研究済みのようである。しかし、折角やったのだし、多少は方法も違うし、GLPKコードに慣れない人には、CPLEXのLPファイルの方が分かり易かろうということで掲載することにした。ご意見、苦情、悪口などはおじさんの掲示板へ。

１．ボンバーパズル
　まず一番簡単なものから。鉛筆パズルの整数計画法定式化には、普通多少は頭を使うものであるが、これは全く考える必要がない。ルールを不等式に直すだけでおしまいという、サルでもできるようなものである。あまりに短く終わってしまうので、Excel VBAによるソルバー入力ファイル作成プログラムを添付した。2015.7.31 改訂、2016.2.10追加。

２．ナンバーリンク
　多少は考えるが、特に悩むような箇所はない、比較的易しいものである。2016.11.05追記

３．スリザーリンク
　2015.5.20改訂　2015.6.20二訂大きな問題も解けるようになった。　2015.6.30 三訂

４．ぬりかべ
　ぬりかべも全体が繋がらねばならないが、ぬりかべの黒塗り領域は繋がり易く分断することはないので、スリザーリンクよりも随分楽である。2015.7.20 訂正　ルールを間違えていた。スリリンより楽ではない。2015.8.01 全面改訂

５．へやわけ
　2014.12.19改訂。白マス全体のつなぎ方変更。

６．美術館
　難しいところはないが、事前準備のテーブル作りのほうが面倒くさい。

７．ひとりにしてくれ
　この白マスはつながらない。ホントに泣ける。勝手な禁則作って無理やり解けるようにしたが、インチキかもしれない。 2014.12.24 改訂。白マスつなぎは、「へやわけ」方式に変更。インチキはなくなった。 2015.05.21 改訂。制約式の脱落部を補正。

８．ましゅ
　数式は書ききれないので、やり方のみを記す。スリザーリンクと同じ方法を採った。 2015.05.21 改訂。まともに全部書くことにした。改訂版スリザーリンクと同じ方法とした。

９．四角に切れ
　インプットファイルを作るのが大変で、整数計画法ソルバーは大きなサイズの問題でも一瞬で終わる。 2015.05.23 全面改訂　ジグゾーパズル方式を止める。

１０．ののぐらむ
　冒頭に掲げた「整数計画法によるパズル解法」に詳細な解説があるので、これは省略。なお、そこにLP形式ファイルを出力するＣ言語プログラムリストが付いているが、このプログラム、長方形の絵を入力すると分かるように、つまらないバグがある。出力リストを眺めるとオカシナ箇所がすぐ分かるのがLPファイルの長所であるが、ちょっと大きな問題をいれると何万行にもなるのが欠点である。

１１．カックロ
　鉛筆パズルをExcelで扱う者にとって、カックロはやりにくい。セルに数値を二つ入れられると、文字列分解しなければならない。

１２．覆面算
　計算値を１の位、１０の位と分けるのが面倒である。

１３．ウォールロジック
　　比較的簡単で特に問題はない。

１４．ビルディングパズル
　　易しそうに見えるが、見える見えないの判定が相当難しい。

１５．不等式パズル
　これは易しい。

１６．ナンバースケルトン
　易しいが面倒くさい。

１７．数独
　これも「整数計画法によるパズル解法」に詳細な解説があるので省略。

１８．ヤジリン
　2015.04.20 改訂しました。2015.06.25 二訂　矢印の番号付条件式を直す。2015.08.06 三訂　元に戻す。

１９．シャカシャカ
　式は書ききれないので、やり方のみ。

２０．橋をかけろ
　「全体が繋がる」が「二重結合の数をminimize」で実現するので非常に楽である。そうは行かない問題があってもよいような気がするが、未だお目に掛からない。パズルの整数計画法は、minimize,maximizeがダミーのものばかりであるが、これが有効に働く唯一のものであろう。2015.05.26 改訂　2015.06.09 二訂

２１．さとがえり
　データ作りのテーブルを準備するのが大変である。

２２．スターバトル
　　

２３．ＡＢＣプレース
　2015.11.29 Easy as ABC 追加。

２４．ブロック分割
　きちんとやると面倒なので、いい加減版。

２５．黒どこ
　黒どこの白マス領域は非常に繋がり易くて楽である。2015.06.10 改訂

２６．碁石ひろい
　巡回セールスマン問題である。碁石の数は大抵２０～３０個なので、なんとか解けるが、動かなくなることもある。その時は、始点、終点など適当に見当つけて入力して手伝ってあげるとよい。

２７．因子の部屋
　数字が６でマスの数が２であれば、本来は（６，１）または（３，２）の組み合わせのどちらかにせよ、という条件を付ける必要があるが、このパズルでは（６，３，２，１）のどれかにせよ、という緩くだらしない条件で正解が得られてしまう。

２８．パイプリンク
　2014/10.16改訂　2015.7.03 二訂　ようやく完成した？。

２９．ごきげんななめ
　閉ループを作ってはいけないという条件で苦労したが、無事できた。

３０．モチコロ
　黒マスが点接触で繋がるので、結合矢印が８方向になり面倒だがなんとか解ける。６３．モチにょろ　参照のこと。

３１．スラローム
　大きな問題では整数計画法が動かなくなることがある。ただ付番するマス数が盤面より少ないので、１０ｘ１０マス程度まで解ける。2015.06.25 改訂

３２．ヘルゴルフ
　変数に４次元配列を使っているので、整数計画法の入力ファイルは猛烈に長くなるが、解析は時間が掛からず、大きな問題でもすぐ解ける。