GLPKでの美術館パズルの攻略法(解法)

キューブ王

パズルの問題を解くプログラムに挑戦している。今回、「美術館パズル」に挑戦。GLPKMathProgで書いた。なお過去に、[スリリン]や「一人にしてくれ」などに挑戦している。旨く攻略できている。

美術館パズルの求解コード、少し考えて、MathProgで、非常に素直にまた簡単に記述できることが分かった。纏めるほどのことでは無い気もした。しかしこういうものは、必ず資料の形で纏める習慣になっており、気がついたら、資料が出来上がっていたのだが、人に紹介するほどのものではないと、放っておいた。これを敢えて紹介する。

この美術館、ニコリのパズルである。ニコリのページに従い[概要][ルール]を説明しておく。

 

[概要]

美術館は、2001年にニコリの雑誌「パズル通信ニコリ」の人気コーナー「オモロパズルのできるまで」から産まれたペンシルパズルです。誌面に掲載されるやいなや、たくさんの読者から支持を受け、初掲載からわずか2年足らずでニコリの看板パズルのひとつにのしあがってしまいました。パズル通信ニコリへの初登場は、95号。102号からは、レギュラーで掲載されるようになりました。

美術館の特徴は、わかりやすいルールと、その裏にある奥の深さです。「数字と照明とマスがこういう組みあわせになっているときは、必ずこう決まる」というパターンがとてもたくさんあるので、「新しいパターンを発見する喜び」をぞんぶんに味わうことができます。すべてのマスに照明を当てるために、考えなければならないことはいろいろあるのです。果てしなく広がる美術館ワールドを、あなたもぜひ体感してみてください。

 

[ルール]

 

 

以下のルールに従って盤面の白マスに照明(○)を配置します。

(1)   数字は、タテヨコ両隣の最大4つの白マスに入る照明の数を表す。

(2)   照明は、そのマスから上下左右に、黒マスか外枠にぶつかるまでの範囲を照らす。ナナメには照らさない。

(3)   どの照明にも照らされない白マスがあってはいけません。

(4)   また、照明のあるマスは、他の照明で照らされてはいけません。

 

 以上、ニコリの記事に従った説明。なお、左端の図が問題例。真ん中の図が解答例。

右端の図は、個人的な約束だが、問題定義例である。8は、「数字指定なし白マス」の代用。5は、「数字指定なし黒マス」の代用である。

 

 

[問題の記述、データ構造]

 このパズル、非常に素直に、GLPKMtahProg言語で記述できる。以下の図を考える。

 

まず、左端の図。白マスに照明灯が置いてあれば、上下左右に光線が放射される、と読む。

次の図。白マスに光線が到着すれば、次のマスまで光線が透過する、と読む。

次の図。黒マスに光線が到着しても、次のマスには光線は透過しない、と読む。

右端の図。2つの光線が正面衝突してはならない、と読む。

右の3つの図、右に進む光線だけ示してあるが、左下上も同様。

 

 左の3つの図がルール(2)に対応。右端の図はルール(4)に対応。ルール(1)(3)の指定は簡単。

 

[解法コード]

 解法コードを、説明しておく。

 

 

## ---------- museum -----------------------

              param Nr;

              param Nc;

              param ini{1..Nr,1..Nc} integer;

              var light{0..Nr+1,0..Nc+1} binary;

              var ll{0..Nr+1,0..Nc+1} binary;

              var lr{0..Nr+1,0..Nc+1} binary;

              var lu{0..Nr+1,0..Nc+1} binary;

              var ld{0..Nr+1,0..Nc+1} binary;

s.t. WALL{r in 0..Nr+1,c in 0..Nc+1: r=0||r=Nr+1||c=0||c=Nc+1}:

              light[r,c]+lu[r,c]+ld[r,c]+lr[r,c]+ll[r,c]=0;

s.t. POST{r in 1..Nr, c in 1..Nc: ini[r,c]<=5}:

              light[r,c]+lu[r,c]+ld[r,c]+lr[r,c]+ll[r,c]=0;

s.t. LIGHT{r in 1..Nr, c in 1..Nc: ini[r,c]<=4}:

              light[r-1,c]+light[r,c+1]+light[r+1,c]+light[r,c-1]=ini[r,c];

 

図は、2*2の問題の場合の例。上下左右に1つずつ拡大して4*4になっている。変数light,ll,lr,lu,ldの宣言コードも参照。

 制約WALLは拡大した部分のlight,lu,ld,lr,llを全て0にしているだけ。

 制約POSTは、「黒マス遮断」に対応。

 制約LIGHTは、数字0-4が指定してあった黒マスについて、周囲のその個数分の照明灯を設置するもの。

 

## ---------  lights ---------

s.t. LIG0{r in 1..Nr,c in 1..Nc}: 4*light[r,c]<=lu[r,c]+ld[r,c]+lr[r,c]+ll[r,c];

s.t. LIGl{r in 1..Nr,c in 1..Nc:ini[r,c]=8}: ll[r,c+1]<=ll[r,c];

s.t. LIGr{r in 1..Nr,c in 1..Nc:ini[r,c]=8}: lr[r,c-1]<=lr[r,c];

s.t. LIGd{r in 1..Nr,c in 1..Nc:ini[r,c]=8}: ld[r-1,c]<=ld[r,c];

s.t. LIGu{r in 1..Nr,c in 1..Nc:ini[r,c]=8}: lu[r+1,c]<=lu[r,c];

s.t. LIHl{r in 1..Nr,c in 1..Nc:ini[r,c]=8}: ll[r,c+1]+light[r,c]>=ll[r,c];

s.t. LIHr{r in 1..Nr,c in 1..Nc:ini[r,c]=8}: lr[r,c-1]+light[r,c]>=lr[r,c];

s.t. LIHd{r in 1..Nr,c in 1..Nc:ini[r,c]=8}: ld[r-1,c]+light[r,c]>=ld[r,c];

s.t. LIHu{r in 1..Nr,c in 1..Nc:ini[r,c]=8}: lu[r+1,c]+light[r,c]>=lu[r,c];

 

 制約LIG0は、マス[r,c]に照明灯があれば上下左右に光線が放射される、というもの。

 制約LIGlは、白マスに左向き光線が到着すれば、次のマスに左向き光線が透過するというもの。次の3つも、同様。勿論、方向は違う。

 制約LIHlは、白マスが左向き光線を出しているなら、そのマスに左向き光線が到着しているか、そのマスに照明灯があるというもの。次の3つも同様。

 なお、制約LIGlなど、範囲指定に:ll[r,c]=8などとあるが、指定外のマスについては、光線は透過しない、「黒マス遮断」となる点に注目要。

 

## ---------  rays  ---------

s.t. RAYx{r in 1..Nr, c in 1..Nc}: lr[r,c-1]+ll[r,c]<=1;

s.t. RAYy{r in 1..Nr, c in 1..Nc}: ld[r-1,c]+lu[r,c]<=1;

s.t. RRRR{r in 1..Nr,c in 1..Nc:ini[r,c]=8}: lr[r,c]+ll[r,c]+lu[r,c]+ld[r,c]>=1;

 

制約RAYxは、x軸方向で光線が衝突してはならないことを示す。

制約RAYyは、y軸方向で光線が衝突してはならないことを示す。

制約RRRRは、個別の白マスに到着する光線があることを示す。

 

 以上で終わり。結果を表示するコードも必要だがそれは省略。最後尾のコードには示してある。

 

 

[美術館とMathProgの親和性]

  美術館、MathProgで簡単に記述できると思っていた。実際に、非常に素直に、簡単に記述できた。

 10*10問題であれば、普通のPCで求解時間0.0secと表示される。求解時間は問題とならない。

 

[MathProg求解コード]

 

## ---------- museum -----------------------

              param Nr;

              param Nc;

              param ini{1..Nr,1..Nc} integer;

              var light{0..Nr+1,0..Nc+1} binary;

              var ll{0..Nr+1,0..Nc+1} binary;

              var lr{0..Nr+1,0..Nc+1} binary;

              var lu{0..Nr+1,0..Nc+1} binary;

              var ld{0..Nr+1,0..Nc+1} binary;

## ----------- init ------------

s.t. WALL{r in 0..Nr+1,c in 0..Nc+1: r=0||r=Nr+1||c=0||c=Nc+1}:

              light[r,c]+lu[r,c]+ld[r,c]+lr[r,c]+ll[r,c]=0;

s.t. POST{r in 1..Nr, c in 1..Nc: ini[r,c]<=5}:

              light[r,c]+lu[r,c]+ld[r,c]+lr[r,c]+ll[r,c]=0;

s.t. LIGHT{r in 1..Nr, c in 1..Nc: ini[r,c]<=4}:

              light[r-1,c]+light[r,c+1]+light[r+1,c]+light[r,c-1]=ini[r,c];

## ---------  lights ---------

s.t. LIG0{r in 1..Nr,c in 1..Nc}: 4*light[r,c]<=lu[r,c]+ld[r,c]+lr[r,c]+ll[r,c];

s.t. LIGl{r in 1..Nr,c in 1..Nc:ini[r,c]=8}: ll[r,c+1]<=ll[r,c];

s.t. LIGr{r in 1..Nr,c in 1..Nc:ini[r,c]=8}: lr[r,c-1]<=lr[r,c];

s.t. LIGd{r in 1..Nr,c in 1..Nc:ini[r,c]=8}: ld[r-1,c]<=ld[r,c];

s.t. LIGu{r in 1..Nr,c in 1..Nc:ini[r,c]=8}: lu[r+1,c]<=lu[r,c];

s.t. LIHl{r in 1..Nr,c in 1..Nc:ini[r,c]=8}: ll[r,c+1]+light[r,c]>=ll[r,c];

s.t. LIHr{r in 1..Nr,c in 1..Nc:ini[r,c]=8}: lr[r,c-1]+light[r,c]>=lr[r,c];

s.t. LIHd{r in 1..Nr,c in 1..Nc:ini[r,c]=8}: ld[r-1,c]+light[r,c]>=ld[r,c];

s.t. LIHu{r in 1..Nr,c in 1..Nc:ini[r,c]=8}: lu[r+1,c]+light[r,c]>=lu[r,c];

## ---------  rays  ---------

s.t. RAYx{r in 1..Nr, c in 1..Nc}: lr[r,c-1]+ll[r,c]<=1;

s.t. RAYy{r in 1..Nr, c in 1..Nc}: ld[r-1,c]+lu[r,c]<=1;

s.t. RRRR{r in 1..Nr,c in 1..Nc:ini[r,c]=8}: lr[r,c]+ll[r,c]+lu[r,c]+ld[r,c]>=1;

## ---------- solve and dump --------------

var maxvalue >=0;

s.t. MAX0: maxvalue=sum{r in 1..Nr,c in 1..Nc}light[r,c];

minimize MAX1: maxvalue;

 

solve ;

printf "--ini--lights=%d\n", maxvalue;

for {r in 1..Nr}{ 

  for{c in 1..Nc}{

    printf" %s",if light[r,c]then"@"else if ini[r,c]-8 then ini[r,c] else ".";

  }printf"\n";

}

end;

 

 

[問題定義コード]

 ニコリから、お試し問題を2つ載せておく。解答は、ニコリのページ参照。

 

## p01.txt


data;

              param Nr:=10;

              param Nc:=10;

param ini: 1 2 3 4 5 6 7 8 9 10:=

              1  8 8 8 8 8 8 8 8 8 8

              2  8 4 8 8 5 8 8 8 2 8

              3  8 8 5 8 8 8 8 8 5 8

              4  8 8 8 8 5 0 8 8 8 8

              5  8 8 8 8 8 8 8 8 8 8

              6  8 8 8 8 8 8 8 8 8 8

              7  8 8 8 8 1 5 8 8 8 8

              8  8 1 8 8 8 8 8 0 8 8

              9  8 1 8 8 8 1 8 8 5 8

              10 8 8 8 8 8 8 8 8 8 8;

end;

 

##p02.txt

data;

              param Nr:=10;

              param Nc:=10;

param ini: 1 2 3 4 5 6 7 8 9 10:=

              1  8 8 8 8 8 8 8 8 8 8

              2  8 8 3 8 8 8 8 1 1 8

              3  8 5 5 5 8 8 5 8 8 8

              4  8 8 1 8 8 8 5 8 8 8

              5  8 8 8 8 4 8 8 8 8 8

              6  8 8 8 8 8 5 8 8 8 8

              7  8 8 8 5 8 8 8 2 8 8

              8  8 8 8 5 8 8 5 5 5 8

              9  8 2 2 8 8 8 8 5 8 8

              10 8 8 8 8 8 8 8 8 8 8;

end;

 

 

トップページへ

 

 

Ads by TOK2