Entries

【保存版】コンピュータで解けるペンシルパズルをまとめてみた part1

○概要
 前回その前でも触れましたが、今や様々なペンシルパズルがコンピュータで解かれるようになってきました。
 もちろんその用途は懸賞でズルするため……ではなく、純粋な学術目的か、作成したパズルのチェックに使うかです。
 そこで、上記の真っ当な目的に使うためのソフトやコードを、色々と探してみました。
 なお、今回チェックしたパズルは、数独・カックロ・美術館・四角に切れ・ナンバーリンク・ましゅ・スリザーリンク・橋をかけろ・ぬりかべ・ひとりにしてくれです。


○確認事項
 どんなパズルにも言えることですが、
小問題ではバックトラックだけでも十分です。が、それ以上になると手筋を利用した確定探索が必要です。
『数独』なんかは大抵は9x9なのでバックトラックでも余裕だったりしますが、『お絵かきロジック』など巨大化が避けられない系のパズルでは嫌でも確定探索を実装する必要があります。かと思えば、背理法前提の手筋がゴロゴロしていることも多いので、ルール判定+背理法+バックトラックでもそこそこ戦えたりすることもあります。
 また、数学的には、適切に変換することにより、SAT(充足可能性問題)にして解くことができたり整数計画問題に直して解いたり動的生成したSQLに投げるだけで解答が出せたりします。オソロシイことにヘタなソルバーよりそっちの方が速かったりするから侮れない……。詳しくはリンク先を読んでね。



☆数独
 まあ言うまでもないですね。個人的には有名すぎて見飽きたのと解答作業が単調になりがちなのもあってあまり好きではないのですが、世間的には大人気なようです(そもそもニコリ社長の鍜治真起氏が命名したパズルなので、社長的にはむしろ大勝利なわけですが)。それだけに、ネットでちょっと探しただけでも、

「Sudoku Susser」(http://www.madoverlord.com/projects/sudoku.t)
――プロ仕様(バックトラックか手筋解法かを選べる)な高性能ソルバー。盤面画像読み込み対応。

「数独解析ソフト「むさし」シリーズ詰め合わせ」(http://www.vector.co.jp/soft/win95/game/se385247.htmlなど)
――通常盤面だけでなく、対角線・重複(盤面が複数くっついたもの)・25x25等他サイズ・不等式ナンプレなどが解析できる凄まじい一品。

「ナンプレ自動生成エンジン」(http://puzzle.gr.jp/show/Japanese/NPV2)
――本来はパズル自動作成ソフトなのだが、ソルバーとしても使用可能。柔軟性を持たせた設計により、変形ナンプレ(枠が正方形 or 長方形じゃない奴)も楽勝なのがウリ。

などといった素晴らしいソフトがあります。極論すれば懸賞が無意味になるレベルの威力ですが、自学自習用に使えば問題ナッシング。つーか懸賞って普通は抽選じゃね? 早く解けてもあまり意味なくね?

 アルゴリズムとしては……バックトラックだけでも許容範囲内の時間で解ける珍しい例ですね、これ。ただ、9x9じゃなくて16x16とか25x25とかになるとバックトラックだけじゃ無理ゲーになるので、どうしても「n国同盟」などの手筋をぶっ込む必要があります。全部突っ込むのが面倒臭い人はせめて前に紹介したページの奴だけでも実装してみるだけでもだいぶ違うんじゃないですかね?



☆カックロ
 バックトラック無しでも、パターン(3マスで合計24なら7・8・9しかありえない、とか。実は自作でソフトをうpしています)に当てはめて候補を絞っていくだけで大分解けるというイージーステージ。私は普通に好きですが、ニコリ本誌でパターン表を載せないのはなにか理由があるんですかね?
 ソフトは3つ紹介。

「KakuroPlayer」(http://www.takana.info/kakuro/)
――パターン解析とバックトラックによりどんな問題も解ける(ただしJava)。作者曰く、背理法も1マスだけで十分だとか。

「Kacraid」(http://www.geocities.jp/inaeggmon/soft/tool.html)
――正確には回答支援ソフト。

「クロスサム自動生成エンジン」(http://puzzle.gr.jp/show/Japanese/CrossSums)
――これはどちらかと言えば問題作成用ですね。



☆美術館
 ググってみたところ、「自作でソルバを作ってみた」といった報告は(私を含めて)多数あったものの、配布している例が全然見つかりませんでした……。つまり、新規開拓やり放題な分野ですね、わかります。自作するぐらいなのでもちろん大好きなパズルであり、「アゼン」レベルも解ける程度には慣れているつもりです。

「ソルバ for パズル『美術館』」(http://dev.onionsoft.net/seed/info.ax?id=441)
――ブログ内でC++で実装した奴をHSPに移植。「アゼン」レベルでもない限りはだいたい10秒以内で解ける。え、C++版はって?スーパージャイアントすら1.5秒で解く奴を配布するのは人道的な問題が……

「美術館パズルをSugar制約ソルバーで解く」(http://bach.istc.kobe-u.ac.jp/sugar/puzzles/akari.html)
――SAT(充足可能性問題)に問題を翻訳(変換)した上で、SATを高速に処理するソルバの一つ「Sugar」に食わせて解かせてみたページ。制約条件しか書いていないのでちょっと遅いのはちかたないね。あ、SATが出てきた時点で薄々感づいた人もいると思うけど、美術館等ペンシルパズルは軒並みNP完全だから。

「ペンシルパズル「美術館」における難易度判定に関する研究」(http://www2.teu.ac.jp/aqua/3D/2010/Paper/Kashima_2010.pdf)
――パズル『美術館』を手筋の種類によって難易度分類しようという研究。細かく分けてもせいぜい25種類しかないというのはむしろ意外。使用条件も細かく書かれているので、プログラマにも優しい内容になっているのも○。



☆四角に切れ
 好きは好きなのですが、あまり手応えのある奴を解いていないのでペンパ本購入を検討中。ググってみたところ、意外と美術館以上に研究は進んでいる模様。コレ以外にも色々あるから探してみてね!

「四角に切れソルバー(をひっつけたPencilBoxの四角に切れ)」(http://kazunegi.com/shikakuSolver/)
――質はそこそこ高そうですが、GUI部分を他から持ってくるとかそこにシビれる!あこがれるゥ!

「四角に切れ Solver」(http://www016.upp.so-net.ne.jp/TokaiRenju2/puzzle/Shikaku.html)
――上と違ってこちらはWebアプリ。入力が面倒だけどソルバとしては本物。

「Dancing Linksを用いたKnuth's Algorithm Xによる「四角に切れ」ソルバーの実装」(http://qnighy.hatenablog.com/entry/20100117/1263689587)
――C++のソースコードですよ、ソースコード!



☆ナンバーリンク
 最も問題を作りづらい&解きづらいパズルなだけあって、ソルバーを作るのも相当大変なようです。つーかお前抽象的すぎるんだよ常考。普通に解くのと短絡解をチェックするのとでは、後者の方が膨大な時間が掛かることに注意な。以下、ソフトとかの紹介。

「ナンバーリンクソルバー」(http://www.interq.or.jp/moonstone/person/numlink/)
――作成記を読めば、作者の苦労も分かるはず。短絡解を考慮しだすと、ヒューリスティクスを目一杯活用して枝刈りしないと使い物にならないのです。どうあがいてもNP完全ですが、その分努力が実る分野でもあるのです>ペンシルパズル

「ナンバーリンクを、解けるところまで解くプログラム」(http://d.hatena.ne.jp/ta-nuki/touch/20110918)
――正確にはソフトへの直リンではなく説明記事。作者が紆余曲折の末挫折し、ある程度までしか解けない奴をうpせざるを得なくなった過程が書かれています(実際のソフトはリンク先にて公開されている)。使用アルゴリズムの説明がネタ満載なので一度は読んでみては?

「ナンバーリンク ショートカット チェッカ」(http://www5e.biglobe.ne.jp/~jyokun/numlin/)
――短絡解を調べる用のソルバー。開発には、上記「ナンバーリンクソルバー」の作成記などを参考にしたそうで。

「ナンバーリンク・パズルをSugar制約ソルバーで解く」(http://bach.istc.kobe-u.ac.jp/sugar/puzzles/numberlink.html)
――みんな大好きSATソルバーで定式化してぶちかましてみたパターン。他にも、数理計画法で解いてみたパターンもあって、定式化(一般化)してカタを付ける情報学の恐ろしさの片鱗を味わったぜ…



☆ましゅ
 スリザーリンクと同じく、輪っかを作る系のパズル(ただし私にとってはましゅ>>>スリリン)。ググってみると、手筋を利用して解く系が多いようですね。みさくら語とは何の関係もないのぉぉおッ!

「ましゅ解答プログラム」(http://rogiken.org/puzz/program/masyu.html)
――手筋のみを利用して解くもの。当然、完全には解けない問題もあり。背理法は、演算時間が増加することから実装していない模様。

「MashPlayer」(http://www.oct.zaq.ne.jp/woodside/mash/)
――解答だけでなく作成なども支援するソフト。盤面はXMLで保存するんですってよ。

「ニコリのパズル「ましゅ」の解法」(http://mediatips.co.jp/puzzle/mashu-tech.html)
――ましゅにおける手筋を一通りまとめたもの。実装が面倒そうなものもあるけどきっと気のせい。



☆スリザーリンク
 他に比べても特異な盤面が特色。何故か「たいへん」以上の問題がさっぱり解けないのですが、手筋を把握しきれていないだけなんでしょうか。ググってみたところ、コンピュータによる解決法としては、

「SlitherLinkPlayer」(http://www.takana.info/sl/)
――バックトラックによりどんな問題も解ける(ただしJava)。

「スリザーリンク解答プログラム」(http://www2.ttcn.ne.jp/~itogawa/product/slitherlink.html)
――名前が安直なのは仕様です。tar.gzってことはソースのみ or Linux用?

「フロンティア法:BDD/ZDDを用いた高速なグラフ列挙索引化アルゴリズム」(http://www.ieice.org/~netsci/wp-content/uploads/2012/08/NetSci201208_Minato.pdf)
――これはソフトではなく研究(のPowerPointをPDFにしたもの)。BDD/ZDDはあのフカシギの数え方を解決するためにも使われる結構凄い奴。スリザーリンクの盤面も一種のグラフなので、それらの手法が使えるというわけ。一見の価値有りか。

といった感じ。特に最後の奴は、バックトラックではとても解けないような巨大問題(スーパージャイアントとか)も瞬殺できる可能性があります。実装できたらヒーローですよ、ヒーロー!



☆橋をかけろ
 盤面に数字しかない(罫線がない)ので数字の座標が微妙に分かりにくいパズル。四角に切れと同じ意味でペンパ本が欲しい……。とりあえずググった結果がこちら。

「HashioKakero」(http://www.pro.or.jp/~fuji/puzzlestudy/hashiokakero.html)
――ソースのみだが、g++等でコンパイルすれば問題ナッシング。作者曰く残念なソースらしいが、それなりに速いそうだ。

「整数計画法によるパズル解法 橋をかけろ」(http://www21.tok2.com/home/kainaga11/glpkBridges/GLPKbridges.htm)
――GLPKに投げてみた結果。13x22問題も1秒以内で解けている。

「パズル「橋をかけろ」のNP完全性」(http://np.cs.uec.ac.jp/StudentResults/Bridges.pdf)
――これを書いたのは電通大の学生さんですかね? やっぱりNP問題だったのか……



☆ぬりかべ
 実はニコリのパズルの中でも古参な方だったりする。個人的にはあまり好きではない(感覚的に)が、手筋が割と少ないなど、楽ではあるらしい。

「ぬりかべパズルをSugar制約ソルバーで解く」(http://bach.istc.kobe-u.ac.jp/sugar/puzzles/nurikabe.html)
――おためし問題10(36x20)を8分半で解く程度の能力

「GLPKによるパズル解法 ぬりかべ」(http://www21.tok2.com/home/kainaga11/glpkBricks/GLPKbricks.htm)
――10x10を数秒で解く程度の能力。曰く、「ぬりかべとMathProgの相性はよくない。ただこれは、どの言語で書いても同様な気がする」とのこと(原文ママ)。

「DotNet Nurikabe Solver」(http://sourceforge.net/projects/nurikabedotnet/)
――どうも海外製っぽい。C#で組まれているらしいが未確認。



☆ひとりにしてくれ
 どう考えても傷ついた人かヒキコモリのセリフにしか聞こえないのですが、立派なパズル名です。「たいへん」レベルですら難しくて埋められないでござる……。

「ひとりにしてくれパズルをSugar制約ソルバーで解く」(http://bach.istc.kobe-u.ac.jp/sugar/puzzles/hitori.html)
――SATソルバーによる解析。

「GLPKでの「ひとりにしてくれ」の攻略法(解法)」(http://www21.tok2.com/home/kainaga11/glpkAlone/GLPK_alone.htm)
――整数計画法ソルバーによる解析。

「パズル「ひとりにしてくれ」の難易度について」(http://repo.lib.hosei.ac.jp/bitstream/10114/7382/1/24sato.pdf)
――要するに、使用手筋による分類。上の美術館の奴に比べてより複雑で、そして定義部分とソースコードが長いなが~い!!



今回はここまで。次回は紹介していない他のパズル用ソルバについて解説する予定。


2013/8/24追記:
・リンク記述のHTMLを書き間違えていたので修正。
・舞那 素遥氏(https://twitter.com/mainasuyon)の投稿により、新たなソフトを発見できたので追加(ありがとうございます!)。元々は各パズル毎に3項目づつ紹介する予定(足りない分は汎用ソルバーの記事で埋める)でしたので、追加分が蛇足に見えるかもしれません。
関連記事
スポンサーサイト
この記事にトラックバックする(FC2ブログユーザー)
http://ysrken.blog.fc2.com/tb.php/63-c84037ff

トラックバック

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

Appendix

プロフィール

YSR

Author:YSR
「YSR」「YSRKEN」「◆YSRKENkO6Y(~2013/08/25)」「◆YSRKEN.ceVZZ(2013/08/26~)」として活動しています。
プログラミングと艦これが趣味です。
プロフ画像はCrystalDiskInfoの水晶雫ちゃんです。
主な創作物についてはhttp://ysrken.blog.fc2.com/blog-entry-76.htmlをご覧ください。

カレンダー(月別)

08 ≪│2017/09│≫ 10
- - - - - 1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30

全記事表示リンク

全ての記事を表示する

QRコード

QR

総アクセス数

アクセス数

現在の閲覧者数: