Entries

スポンサーサイト

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

トラックバック

コメント

コメントの投稿

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

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

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

○概要
 背理法最強伝説。


○詳細
 前回でも紹介した美術館手筋集」(あさおきたん氏)ですが、「発展救出」や「1の定理」など、直接実装しようとするとかなーり面倒なことになりそうな手筋も多いです。ただ、これらの手筋を統一的に処理する作戦が無いわけではありません。それが、今回紹介する背理法と呼ばれるものです。

 「背理法」については、数学の方で馴染みがある人も多いかもしれません。要するに、「『A』か『Aでない』かの2通りしかない状況で、片方を仮定して矛盾が生じた場合はもう片方が真である」とする論法のことです。これをパズルに当てはめると、『あるマスにある値が入る』『あるマスにある値は入らない』かの2通りとなります……ただし、盤面の状況によっては、『(そもそも盤面に解が存在しないので)あるマスにある値が入ろうが入らなかろうが解が出てこない』かもしれません。コード化する際は、その対策も取り入れる必要があります。
 このアルゴリズムを(パズル『美術館』向けに)擬似コードで示すとこんな感じです。

ある白マスに照明「○」を置く
if(盤面に矛盾がある){
//照明を置くと矛盾⇒照明が置けない場所
盤面を元に戻す
ある白マスを照明禁止「×」にする
}else{
ある白マスを照明禁止「×」にする
if(盤面に矛盾がある){
//照明を置けなくすると矛盾⇒照明を置く場所
盤面を元に戻す
ある白マスに照明「○」を置く
}else{
//元の盤面自体に矛盾がある
「解なし」と出力 or 例外発生 or 返り値にする
}
}

これに、前回触れたヒューリスティクス(手筋)を組み込むとこんな感じ。

//解を見つけたら返り値TRUE、そうでなければFALSE
int 探索(盤面){
if(盤面に矛盾がない){
if(盤面が解答である){
盤面を出力
return TRUE;
}else{
ある白マスに照明を置く
確定探索(盤面);
if(探索(盤面) == TRUE){
return TRUE;
}else{
盤面を戻す
ある白マスを照明禁止にする
確定探索(盤面);
if(探索(盤面) == TRUE){
return TRUE;
}else{
//そもそもの盤面に矛盾があった
return FALSE;
}
}
}
return FALSE;
}else{
//矛盾が発生したので戻る
return FALSE;
}
}
void 確定探索(盤面){
(先に、自然発生・斜め飛び等の処理をしておくことを推奨)
ある白マスに照明「○」を置く
if(盤面に矛盾がある){
//照明を置くと矛盾⇒照明が置けない場所
盤面を元に戻す
ある白マスを照明禁止「×」にする
}else{
ある白マスを照明禁止「×」にする
if(盤面に矛盾がある){
//照明を置けなくすると矛盾⇒照明を置く場所
盤面を元に戻す
ある白マスに照明「○」を置く
}else{
//元の盤面自体に矛盾がある
「解なし」と出力 or 例外発生 or 返り値にする
}
}
}

……一応補足しますが、ここでの「盤面に矛盾がある」とは、「ルールに反している」(「1」の周りに照明が4個あるとか)という意味であって、「解答ではない」という意味ではない(「3」の周りに照明が2個しかなくてもとりあえず通すということ)です。


○結果
 実は当初、「これ背理法をワザワザ仕込む意味あるのか?」と疑問に思っていました。なぜなら、上の擬似コードを見れば分かるように、素の探索でも「矛盾があれば戻す」ということを行なっているので、あえて確定探索部分で取り込む価値が有るのか疑問だったからです。
 ですが、その心配は杞憂だったようです。nikoli公式の「パズル早解き選手権」の第63回の問題を解かせたところ、前回の時点でのコードでは5000秒以上掛かっていたところ、背理法を取り入れたコードでは僅か0.15秒! 前回では「解ける気がしないorz」と言っていた問題(パズル通信ニコリ105号の付録・64x50スーパージャイアントサイズの『美術館』)も1.5秒で片付ける、世にも恐ろしい存在に生まれ変わったのです! え、懸賞でズルなんてしないよ? 普通にやってもアゼン問題解けるしね!
( ゚∀゚)アハハ八八ノヽノヽノヽノ \ / \/ \


 ……もう、(開発を)ゴールしてもいいよね?
関連記事
スポンサーサイト
この記事にトラックバックする(FC2ブログユーザー)
http://ysrken.blog.fc2.com/tb.php/62-77ab61ec

トラックバック

コメント

コメントの投稿

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

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ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。