Entries

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

part1→http://ysrken.blog.fc2.com/blog-entry-63.html
(紹介パズル:数独・カックロ・美術館・四角に切れ・ナンバーリンク・ましゅ・スリザーリンク・橋をかけろ・ぬりかべ・ひとりにしてくれ)

○概要
 前回(part1)に引き続き、コンピュータで解けるパズルについて、ソフトやソースコードなどを色々と調べてみました。
 今回チェックしたパズルは、フィルオミノ・へやわけ・推理パズル・お絵かきロジック・波及効果・ヤジリン・シャカシャカ・クロスワード・黒マスはどこだです。


☆フィルオミノ
 未だにこいつの類似パズル(別出版社による同形パズル)を見たことがありません。だからと言って面白くないわけでは勿論なく、個人的には好きな方のパズルですね。
 ただ、ソルバーを作るのはかなり面倒らしく、ググってもそれらしきものは見つかりませんでした。と言うか定食パズルなのにnikoli.comにFlashが存在しないという特殊なパズルなので(シャカシャカはあるのに……)、ソルバを配布したらその道では有名になれるかもしれません。

「フィルオミノ・パズルをSugar制約ソルバーで解く」(http://bach.istc.kobe-u.ac.jp/sugar/puzzles/fillomino.html)
――お馴染みの制約ソルバーのページです。ただ、ページ自体が書きかけなので、詳しい制約条件を知りたい人は本文中にリンクされたcspファイルを頑張って読み解く必要があります。



☆へやわけ
 これも私が大好きなパズルの一つですね。へやわけ用語の基礎知識出没!アド街ック天国~へやわけ編~などがあることが、その手筋の奥深さを物語っています。

「へやわけパズルをSugar制約ソルバーで解く」(http://bach.istc.kobe-u.ac.jp/sugar/puzzles/heyawake.html)
――このページも書きかけなので、制約条件ファイルを読み解いてください。……説明が雑いのは分かってるんだ許してくれ。

「パズル「へやわけ」の難易度について」(http://repo.lib.hosei.ac.jp/bitstream/10114/197/1/21sato.pdf)
――まあ要するに、手筋を連発すれば大抵のへやわけは解けるのです。ただ、分断禁とかを実装するのって面倒そうだよね、とか思ったり。



☆推理パズル
 ある意味では一番「論理」らしいパズルですね。他のパズルと違い、制約プログラミングでしか解く手段がないんじゃないかと言う気がするのですが、実際はどうなんですかね?

「簡易推理ロジック」(http://homepage2.nifty.com/lonelyperzoo/tool/slogic/slogic.htm)
――使い方としては、「項目設定でグループ名と項目名を設定」→「作成モードで条件より決まる○と×を入力しておく」→「解答モードで自動解答ボタンをクリック」、といった手順になります。条件を示す文章から条件を自動設定したり、解候補を列挙したりする機能はないので気をつけて下さい。

「推理パズルが好きだ。あるいは推理パズルをSugar制約ソルバーで解く」(http://d.hatena.ne.jp/mainasuyon/20130503/p1)
――上記ソルバーの紹介ページ。如何にSATソルバー向けに条件を落とすのが簡単かがよく分かるはず。



☆お絵かきロジック
 おそらく(国内では)数独に匹敵するレベルで有名なパズルですね。「解けば絵が出る」というところが人気の秘密なんでしょうね、きっと。地味に呼び名が多いのが特徴で、「ののぐらむ」「イラストロジック」「エデル」等、出版社によって様々な呼び名が存在します。
 基本手筋がせいぜい「確実に塗るマス・塗らないマスを処理」「既存の確定場所から候補を絞る」「背理法」ぐらいしかないので、実装もそれほど難しくはありません。ただ、あるドットパターンを数字化してもそれが唯一解とは限らないので、問題を作成する側は唯一解になるようにドットパターンを工夫する必要があります。
 以下にソルバーを紹介しますが、ぶっちゃけ作成ソフトにソルバーが付属する場合が多い(例:「LogicLand」「LogiNeko」)ので、いちいち落とす必然性は薄いかもしれません。後、ソルバ間のファイル互換性は皆無に近いので、「イラロジ相互変換」もついでに導入しておくことをオススメします。

「お絵かきロジックソルバー」(http://www.kuroneko-square.net/services/oekakilogic/)
――数字だけテキストで入力すればOKなタイプのソルバーです。30x30まで。

「お絵描きロジック(ver2)」(http://www.ic-net.or.jp/home/takaken/so/logic/index.html)
――重複解も検出してくれるという優れものです。25x25まで。

「イラストロジック解読プログラム Ver.2.3」(http://www.race.u-tokyo.ac.jp/~moro/ilogic/index.html)
――Javaなので複数のOSで実行可能。64x64まで。



☆波及効果
 これはこれで好きなパズルです。ただ、大きな盤面は解いたことがないので、個人的にはペンパ本が欲しいところです。

「波及効果ソルバー(をひっつけたPencilBoxの波及効果)」(http://kazunegi.com/hakyuSolver/)
――こちらはJavaで動作します。

「波 及 効 果 Solver」(http://www016.upp.so-net.ne.jp/TokaiRenju2/puzzle/Hakyu.html)
――こっちはHTMLで動作。マウスクリックでぽちぽち入力すればOKなのが特徴ですね(楽かどうかはとにかく)。

「Hakyu Generator」(http://www.epii.jp/articles/product/hakyugen)
――本来は問題作成用プログラムですが、ソルバー機能も搭載しています。



☆ヤジリン
 ……これまでのパズルに比べて若干マイナー臭が漂っていますが、定食パズルには違いありません。残念ながらバイナリ形式のソルバーは見つかりませんでしたが、需要の問題だから仕方ないよね

「ヤジリン・パズルをSugar制約ソルバーで解く」(http://bach.istc.kobe-u.ac.jp/sugar/puzzles/yajilin.html)
――Sugarによる解法。

「ZDDのリンクパズルへの応用」(http://www.alg.cei.uec.ac.jp/itohiro/Games/110310/110310-04.pdf)
――ZDDによる概説。



☆シャカシャカ
 実は私、このパズルを解いたことはありません。なので、得意かどうかは分かりません、ごめんなさい。ソルバー自体は公開しようかという話がかつてありましたが、現在は実行ファイルとしては公開されていないようです。

「整数計画法によるパズル解法 シャカシャカ」(http://www21.tok2.com/home/kainaga11/glpkShaka/GLPKshaka.htm)
――前回でもおなじみ、GLPKMathProg言語による解法です。要するに、長方形判定を符号化によって対処しようという発想ですね。曰く、「このシャカシャカ、コンピュータが極端に得意なパズルといえよう」だとか。

「シャカシャカと整数計画法」(http://www.alg.cei.uec.ac.jp/itohiro/Games/130301/130301-01.pdf)
――電気通信大学岡本吉央氏による発表(PowerPointをPDFにしたもの)。線形計画法による解き方がより分かりやすく説明されているので必見かと。



☆クロスワード
 ま、説明は不要でしょうね。これの「ソルバー」としては、「カギから入る言葉を予測する」ものと、「盤面状況から入りうる言葉を予測する」ものとの2通りの方向性があります。後者の方が簡単ですが、前者も人工知能的な意味では非常に興味深いです。

「日本語クロスワードを解く:性能向上の検討」(https://kaigi.org/jsai/webprogram/2013/pdf/64.pdf)
――カギ情報を解析して解くソルバーについての研究論文。

「Crossword Builder」(http://xword.squares.net/soft.html)
――厳密には作成支援ソフトなのですが、単語リストを元に通常検索(文字数や途中文字を手がかりにする)・交差検索(交差する2本を元に検索)・串刺し検索(複数本の交差を考慮して検索)ができるので、クロスワードを解く際にも絶大な威力を発揮します。公式サイト曰く「クロスワードの解答は未実装」らしいので、将来のアップグレードに期待。

「クロスワード ギバー」(http://katahiromz.web.fc2.com/xword/)
――厳密には自動生成ソフトというべきものですが一応紹介。



☆ナンバークロス
 言うなれば「カギがないクロスワード」ですね。こちらのソルバーの方がより”ソルバーっぽい”気がします。

「ナンクロ解答」(http://www.kanpen.net/article/numcrosolution.html)
――製作者曰く、辞書に載っていないワードの存在を許容しないと正答率が低くなるそうです。単語を利用する系のパズルでは当然の話なのですが、これは「実装する際には数ワードぐらいは辞書に無い単語を許容できなければならない」ということでもあります。面倒な話ですね。

「ナンクロすいすい」(http://www.vector.co.jp/soft/win95/game/se169846.html)
――「20×20マス以上の大きなパズルもあっけなく解けてしまいます」だってよ。

「YMEナンクロツール」(http://www.vector.co.jp/soft/win95/game/se399181.html)
――こちらは文字検索用ツール。ま、拡張正規表現が使えるエディタを使えば、テキスト形式辞書ファイルから直に検索できるんですけどね?



☆黒マスはどこだ
 本記事のトリを務めるパズルです。現在では「黒どこ」と呼ばれているそうですね。
 あいにくソルバーは見つからなかったのですが、支援用ソフトを1つ紹介します。

「黒マスはどこだ Assistant for Windows」(http://www.vector.co.jp/soft/win31/game/se029063.html)



今回はここまで。もう流石にネタ切れっす……。
関連記事
スポンサーサイト
この記事にトラックバックする(FC2ブログユーザー)
http://ysrken.blog.fc2.com/tb.php/67-f364c716

トラックバック

コメント

[C59] お絵かきロジック・ソルバー作りました

お絵かきロジックのソルバー作りました
イラストロジック解析ソフトです
OSはウブンツなのですが
また数独解析ソフト「むさしの詰め合わせ」の作者でもあります
ありがとう

コメントの投稿

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

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

総アクセス数

アクセス数

現在の閲覧者数: