Entries

スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。
この記事にトラックバックする(FC2ブログユーザー)
http://ysrken.blog.fc2.com/tb.php/61-86e19a1f

トラックバック

コメント

コメントの投稿

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

ペンシルパズル『美術館』のプログラミング part2

part1:http://ysrken.blog.fc2.com/blog-entry-59.html

○概要
 前回では、バックトラックを利用した『美術館』(パズルの方)の解析について述べました。
 流石にそれだけでは遅いので、ヒューリスティクス(手筋)を使って高速化します。


○実装の手引き
※以下の手筋名は、あさおきたん氏の「美術館手筋集」に依りました。

・『暗がり禁』『省エネ』『発光』
『暗がり禁』は、前回ではisClear関数で実装しています。
『省エネ』は照明をバックトラックで置く際に普通に考慮されています(データ構造からも明らか)。
『発光』はsetLight関数で実装しています。

・『単純発生』『単純否定』
 両方とも、前回ではcheckBoard関数で矛盾がないかのチェックはしていますが、置く際に最初に
考慮する、ということはしていません。
 要するに、ある数字マス(A)の上下左右にある照明の数(B)と白マスの数(C)を参照して、
  「もしA>Bなら、A=B+Cの時に限り白マス部分に照明を置く」
  「もしA=Bなら、上下左右の白マスに照明を置けないようにする」
とすれば良いのです。

・『孤立』『救出』
 前回では全く実装していません。実装の方針としては、
  「照明禁止マスまたは白マスにおいて、自身と、黒マスや数字マスに阻まれない限りでの
   上下左右における白マス数を数える。その値が1ならば、その白マス部分に照明を置く」

となります。

・『斜め飛び』
 前回では(ry。実は、前述の『単純発生』『単純否定』のコードに組み込むと書きやすいです。
アルゴリズムとしては、
  「A+1=B+Cの時、『真上マスとその左右』『右マスとその上下』『下マスとその左右』
   『左マススとその上下』をそれぞれ見て、『』毎に『3つとも白マス』が成立した場合、
   『』内の斜めマス(元の数字マスに対しての角位置)に照明を置けないようにする」

とすればいいです。これは例えば、ある数字マスの上と左上と右上が空白だった場合、左上と右上を
照明禁止にする、ということ。

・『斜め13』『斜め12』『パタパタ』
 ……この辺は実装が結構面倒なので、しばらくはスルーでも問題ないでしょう(理由は後述)。
 実装の際は、「13」「12」の内「1」の方が、「実質的な1」(もう一方の数字と向かい合った2マスの
どちらかにしか置けない)でもOKであることに注意が必要です。

・発展救出シリーズ
 抽象的すぎるだろ常識的に考えて……。

・1の定理シリーズ、占有シリーズ、数字系占有定理シリーズ
 発展救出シリーズほどではないですが、実装は難しいかと。状況をコードで長々と記述するか、
マスクパターンをあらかじめ作成しておくかの2つに一つだと思われます。

 当然ですが、これらの手筋をプログラムに組み込むと確かに速くなります。再帰ルーチンに
手筋確定ルーチンを組み込む方法が分からない人は、takaken氏の「確定探索付き再帰
を参照しましょう。


○演算時間の経過
 ……軽く実装して驚きました。恐ろしいほど効きます。
 まず、『単純発生』『単純否定』を突っ込むだけで、前回110.384秒掛かった問題を
解答前:
┌──────────────────┐
│    ■  ■  ■       │
│ 2  1        1 ■0 │
│ ■   0      1     │
│        0  0     0│
│   1      1    0  │
│  0    1      1   │
│0     1  0        │
│     1      1   1 │
│ 10 ■        ■  0 │
│       ■  1  0    │
└──────────────────┘
解答後:
┌──────────────────┐
│+○++■○+■+○■++++++○│
│○2+○1+++++++○1+■0+│
│+■+++0++++○+1++○++│
│++○+++++0++0++○++0│
│+++1○+++++1+○++0++│
│++0+++○1++○+++1+○+│
│0++○++1++0++++○+++│
│+○+++1+○++++1○++1○│
│+10+■○+++++++■++0+│
│○++++++■○+1○+0+○++│
└──────────────────┘
演算時間:51.535000[s]
半分以下の時間で解きます。そして更に、『孤立』『救出』『斜め飛び』を実装すると、
解答前:
┌──────────────────┐
│    ■  ■  ■       │
│ 2  1        1 ■0 │
│ ■   0      1     │
│        0  0     0│
│   1      1    0  │
│  0    1      1   │
│0     1  0        │
│     1      1   1 │
│ 10 ■        ■  0 │
│       ■  1  0    │
└──────────────────┘
解答後:
┌──────────────────┐
│+○++■○+■+○■++++++○│
│○2+○1+++++++○1+■0+│
│+■+++0++++○+1++○++│
│++○+++++0++0++○++0│
│+++1○+++++1+○++0++│
│++0+++○1++○+++1+○+│
│0++○++1++0++++○+++│
│+○+++1+○++++1○++1○│
│+10+■○+++++++■++0+│
│○++++++■○+1○+0+○++│
└──────────────────┘
演算時間:0.861000[s]
50倍以上速くなりました。わけがわからないよ。
 バックトラックにおいていかに枝刈りが大切かがよーく分かりますね。ちなみにこの最後のプログラムでは、
┌─────────────────────────┐
│ 3 ■ ■ ■■  ■  1  ■  1    │
│           ■  1  2  1 ■ 2│
│ ■ ■  ■  2  1  ■  1      │
│     1  ■   0  ■  0   1 1│
│ 2  1  2            1    │
│     ■  ■  1   1   1 0  ■│
│  ■0  1  ■  ■ ■   1   2  │
│■■           0  0   2   ■│
│       ■2       ■  ■ 1  1│
│  11 2   ■■    ■  1   1  │
│■■    3    ■■  0         │
│       2      1    ■   1■│
│  30  ■   1   ■   ■  2■  │
│■■   ■    1      1       │
│         ■  01    1    1■│
│  1   2  ■    ■■   ■ 01  │
│■  1 ■  2       ■1       │
│■   ■   1  ■           ■1│
│  ■   2   3 ■  ■  2  ■■  │
│■  2 ■   ■   2  ■  ■     │
│    ■            ■  3  0 │
│0 1   ■  ■  ■   0  2     │
│      ■  ■  ■  ■  ■  ■ 0 │
│■ ■ 4  ■  0  2           │
│       ■  ■  ■  ■■ ■ ■ 0 │
└─────────────────────────┘
(作・半袖愛好会の男 難易度:たいへん 初出:パズル通信ニコリ105号)
といった巨大なものですら10秒で解きます。アッチョンブリケ

 ……まあ、いくら速くなったとはいえ所詮バックトラック、盤面がグッと大きくなると辛くなるのはちかたないね。実際、今64x50のスーパージャイアント(105号の付録)を回してるけど解ける気がしないorz

 おしまい。
関連記事
スポンサーサイト
この記事にトラックバックする(FC2ブログユーザー)
http://ysrken.blog.fc2.com/tb.php/61-86e19a1f

トラックバック

コメント

コメントの投稿

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

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をご覧ください。

カレンダー(月別)

06 ≪│2017/07│≫ 08
- - - - - - 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 31 - - - - -

全記事表示リンク

全ての記事を表示する

QRコード

QR

総アクセス数

アクセス数

現在の閲覧者数:
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。