Entries

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

前に書いた数独ネタはこちら。

○概要
  株式会社ニコリという会社があります。日本最初のパズル雑誌を出しただけあって、その本業はパズル制作です。自社出版物以外にも、新聞や雑誌、果てはゲームソフトにまで作品を提供し続けています。作品……と言うかパズルの質自体が良いせいか模造品も多く、「ナンバープレイス」「足し算クロス」「ナンバーライン」などと呼ばれています。まあもちろん、全部の作品が人間の手で作られているニコリ製には勝てないのですが。
 個人的に好きなパズルトップ3は「美術館」「へやわけ」「ましゅ」、ワースト3は「スリザーリンク」「ナンバーリンク」「数独」です。前者は「アゼン」(最高難易度)のものも解けてしまうことが多いのですが、後者は「たいへん」(アゼンの一個下)ですらもう解けないレベルです(嫌いなわけではありません。スリリンは手筋が使いこなせないだけで、ナンリンは抽象的過ぎるだけ、数独はいい加減見飽きたのと解く時は候補を羅列して潰していく作業になるのが辛いだけです)
 こういったパズル群をコンピュータで攻略していくサイトは既にあるのですが、個人的にソルバーが欲しくなったので、C言語(C++)で自作してみることにします。今回はタイトル通り「美術館」について。


○解き方の方針
http://www.nikoli.co.jp/ja/puzzles/akari.html
http://ja.wikipedia.org/wiki/%E7%BE%8E%E8%A1%93%E9%A4%A8_%28%E3%83%91%E3%82%BA%E3%83%AB%29
 まず、ルールその他は上記URLをご覧ください。……て、手抜きじゃないんだからね!
 ルールから、要するに「全ての白マスが照らされるように照明を置くこと。ただし数字付きマスのルールは守って、照明同士で照らし合わないようにする」といった条件を満たす盤面を求める作業になります。
 パズルソルバーに限った話ではありませんが、最初に考えるべきはアルゴリズムとデータ構造です。とりあえず今回は、単なるバックトラック(照明を置くか置かないかで分岐)で問題を解かせることにしました。また、データ構造は以下の種類で構成された一次元配列(実質は番兵込みの二次元配列)を使用しました。

「0」と書かれたブロック→0 「0」
「1」と書かれたブロック→1 「1」
「2」と書かれたブロック→2 「2」
「3」と書かれたブロック→3 「3」
「4」と書かれたブロック→4 「4」
単なる黒塗りのブロック→5 「■」
照明→6 「○」
照明で照らされた白マス→7 「+」
照明が置けない場所→8 「×」
白マス→9 「 」

……こうして見ると、全部十進1桁に収まっています。キリガイイネ!
 この時、上記URL(Wikipediaの方)にあるサンプル問題は、次のように記号化されます。

9 9 9 9 9 1 9 9
9 3 5 9 9 9 9 9
9 9 9 9 9 9 0 9
5 9 9 9 5 9 9 9
9 9 9 4 9 9 9 0
9 2 9 9 9 9 9 9
9 9 9 9 9 1 5 9
9 9 5 9 9 9 9 9

ただ、これだと画面表示する際に見づらいことこの上ないので、次のように表示しておくことにします(この部分はソルバーとは関係ない)。
┌────────┐
│     1  │
│ 3■     │
│      0 │
│■   ■   │
│   4   0│
│ 2      │
│     1■ │
│  ■     │
└────────┘
 以下は、実際に私が組んだコードです。コメントは適当ですが、……たぶん分かりますよね?

/* cl code1.c /O2 /favor:INTEL64 /arch:AVX */
//プリプロセッサ
#include <time.h>
#include <stdio.h>
#include <string.h>
//盤面サイズ
#define BoardSizeX 7
#define BoardSizeY 7
#define ArraySize (BoardSizeX + 2) * (BoardSizeY + 2)
//ブール表記用
#define TRUE 1
#define FALSE 0
//盤面状態を記述するための定数リテラル
enum Cell{Block0, Block1, Block2, Block3, Block4, BlockX, Light, Lighted, NoLight, Blank};
//盤面出力
void putBoard(int Board[]);
//盤面を投げると解答盤面を戻す
void solveBoard(int AnswerBoard[]);
//盤面を再帰で解く(解けたら返り値はTRUE)
int solve(int Board[], int AnswerBoard[]);
//異常な盤面ならFALSEを返す
int checkBoard(int Board[]);
//解答盤面ならTRUEを返す
int isClear(int Board[]);
//指定場所に照明をセットする
void setLight(int Board[], int SetPos);
//main関数
int main(void){
//時間測定用
clock_t StartTime, EndTime;
//盤面初期化
int Board[ArraySize] = {5,5,5,5,5,5,5,5,5,
5,9,9,9,9,9,9,9,5,
5,9,2,5,9,9,5,9,5,
5,9,1,9,9,5,9,9,5,
5,9,9,9,9,9,9,2,5,
5,9,5,9,9,5,9,9,5,
5,9,9,4,9,9,9,5,5,
5,9,9,9,9,9,9,9,5,
5,5,5,5,5,5,5,5,5};
printf("解答前:\n");
putBoard(Board);
StartTime = clock();
solveBoard(Board);
EndTime = clock();
printf("解答後:\n");
putBoard(Board);
printf("演算時間:%f[s]", (double)(EndTime - StartTime) / CLOCKS_PER_SEC);
return 0;
}
void putBoard(int Board[]){
int i, j, k;
//以下、出力用コード(お手製にも程がある^^;)
printf("┌");
for(k = 0; k < BoardSizeX; k++){
printf("─");
}
printf("┐\n");
for(i = 1; i <= BoardSizeY; i++){
printf("│");
k = i * (BoardSizeX + 2) + 1;
for(j = 1; j <= BoardSizeX; j++){
switch(Board[k]){
case Block0:
printf("0");
break;
case Block1:
printf("1");
break;
case Block2:
printf("2");
break;
case Block3:
printf("3");
break;
case Block4:
printf("4");
break;
case BlockX:
printf("■");
break;
case Light:
printf("○");
break;
case Lighted:
printf("+");
break;
case NoLight:
printf("×");
break;
case Blank:
printf(" ");
break;
}
++k;
}
printf("│\n");
}
printf("└");
for(k = 0; k < BoardSizeX; k++){
printf("─");
}
printf("┘\n");
}
void solveBoard(int Board[]){
int AnswerBoard[ArraySize];
//ハイ、solve関数のラッパーです
solve(Board, AnswerBoard);
memcpy(Board, AnswerBoard, ArraySize * sizeof(int));
}
int solve(int Board[], int AnswerBoard[]){
int i, j, k;
int Board_[ArraySize];
//putBoard(Board);
if(checkBoard(Board) == TRUE){
//盤面に異常がなければ
if(isClear(Board) == TRUE){
//解答盤面ならば
memcpy(AnswerBoard, Board, ArraySize * sizeof(int));
return TRUE;
}else{
//片っ端から走査して白マスを探す
for(i = 1; i <= BoardSizeY; i++){
k = i * (BoardSizeX + 2) + 1;
for(j = 1; j <= BoardSizeX; j++){
if(Board[k] == Blank){
//白マスなら、とりあえず照明を置いてみる
memcpy(Board_, Board, ArraySize * sizeof(int));
setLight(Board_, k);
if(solve(Board_, AnswerBoard) == TRUE){
//再帰結果、解が出てきたならそのままreturn
return TRUE;
}else{
//どうも照明を置くと解けないらしい。なら照明禁止な!
memcpy(Board_, Board, ArraySize * sizeof(int));
Board_[k] = NoLight;
if(solve(Board_, AnswerBoard) == TRUE){
//再帰結果、解が出てきたならそのままreturn
return TRUE;
}
else{
//照明の有無に関わらず解けない=矛盾!
return FALSE;
}
}
}
++k;
}
}
return FALSE;
}
}else{
return FALSE;
}
}
int checkBoard(int Board[]){
int i, j, k;
int SumLight, SumCanLight;
//片っ端から走査して矛盾がないかを探す
for(i = 1; i <= BoardSizeY; i++){
k = i * (BoardSizeX + 2) + 1;
for(j = 1; j <= BoardSizeX; j++){
//上下左右の「照明数」
SumLight = 0;
if(Board[k - (BoardSizeX + 2)] == Light) ++SumLight;
if(Board[k + 1 ] == Light) ++SumLight;
if(Board[k + (BoardSizeX + 2)] == Light) ++SumLight;
if(Board[k - 1 ] == Light) ++SumLight;
//上下左右の「(照明が置ける)空きマスの数」
SumCanLight = 0;
if(Board[k - (BoardSizeX + 2)] == Blank) ++SumCanLight;
if(Board[k + 1 ] == Blank) ++SumCanLight;
if(Board[k + (BoardSizeX + 2)] == Blank) ++SumCanLight;
if(Board[k - 1 ] == Blank) ++SumCanLight;
//「0」~「4」までで条件が異なるので場合分け
switch(Board[k]){
case Block0:
if(SumLight != 0) return FALSE;
break;
case Block1:
if((SumLight > 1) || (SumLight + SumCanLight < 1)) return FALSE;
break;
case Block2:
if((SumLight > 2) || (SumLight + SumCanLight < 2)) return FALSE;
break;
case Block3:
if((SumLight > 3) || (SumLight + SumCanLight < 3)) return FALSE;
break;
case Block4:
if(SumLight + SumCanLight != 4) return FALSE;
break;
}
++k;
}
}
return TRUE;
}
int isClear(int Board[]){
int i, j, k;
int SumLight, SumCanLight;
//要するに、「解答盤面なら照明禁止と白マスが無いはず」ということ
for(i = 1; i <= BoardSizeY; i++){
k = i * (BoardSizeX + 2) + 1;
for(j = 1; j <= BoardSizeX; j++){
if(Board[k] >= NoLight) return FALSE;
++k;
}
}
return TRUE;
}
void setLight(int Board[], int SetPos){
int SetPos_;
//要するに、照明から上下左右を照らすということ
Board[SetPos] = Light;
SetPos_ = SetPos - (BoardSizeX + 2);
while(Board[SetPos_] >= Lighted){
Board[SetPos_] = Lighted;
SetPos_ -= BoardSizeX + 2;
}
SetPos_ = SetPos + 1;
while(Board[SetPos_] >= Lighted){
Board[SetPos_] = Lighted;
++SetPos_;
}
SetPos_ = SetPos + (BoardSizeX + 2);
while(Board[SetPos_] >= Lighted){
Board[SetPos_] = Lighted;
SetPos_ += BoardSizeX + 2;
}
SetPos_ = SetPos - 1;
while(Board[SetPos_] >= Lighted){
Board[SetPos_] = Lighted;
--SetPos_;
}
}

これで解かせてみると、計算時間は1ミリ秒を切ります。まあ盤面が小さいからなのですが、10x10マスぐらいまでは全部一瞬で解いてくるので、小問題相手にはバックトラックは強力無比であることが分かります。ただし、18x10ぐらいになると、私のノートパソコン(K55VD K55VD-SXBROWNのOSを64bit版Win7に、メモリは8GBまで増設したもの)ですっきり実行して走らせた結果、
解答前:
┌──────────────────┐
│    ■  ■  ■       │
│ 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+○++│
└──────────────────┘
演算時間:110.384000[s]
となりました(問題はこのサンプル問題から引用)。単なるバックトラックだと演算量が指数関数に比例しますので(上記ソースだとちゃんと枝狩りはしているのですが)、36x20なんて解かせた日には解き終わるまでに宇宙が終わってしまう可能性が高いでしょう。次回は、適切なヒューリスティクスを導入した際の演算時間について述べます。

2013/08/19追記:
 一部のリンクが間違っていたので修正。
関連記事
スポンサーサイト
この記事にトラックバックする(FC2ブログユーザー)
http://ysrken.blog.fc2.com/tb.php/59-a1317792

トラックバック

コメント

コメントの投稿

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

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

カレンダー(月別)

10 ≪│2017/11│≫ 12
- - - 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

総アクセス数

アクセス数

現在の閲覧者数: