タイルペイント http://www.nikoli.co.jp/ja/puzzles/tile_paint,html 例題 (ニコリのパズル紹介より) 2 1 4 1 解答 1 1 1 2 2 3 3 2 2 4 1 2 ルール ①盤面上にある、太線で区切られた部分(タイルと呼ぶ)のいくつかを黒く塗る。 ②盤面の数字は、その右あるいは下の、外周か次の斜線のマスまでの区切られた一列のうちで、 黒く塗られるマスの数を表す。 ③どのタイルも、すべてのマスを塗るか、すべてのマスを塗らずにおくかのどちらかにする。 タイルの一部のマスだけを塗ってはいけない。 注)②で示されているように、数は少ないが盤面のまん中付近にも\と数字を書いたマスのある 問題が存在する。 マスの行番号をI、列番号をJとし、タイルに番号を振り、マス座標との対応を取った表を用意する。 J → 1 2 3 . . . Nc I 1 ↓ 1 2 3 4 2 5 2 6 6 3 7 8 8 9 10 11 12 9 . . . Nr 変数 B(I,J) = 1 = 0 マス(I,J)を黒く塗るとき 〃 塗らないとき W(I,J) = 1 = 0 マス(I,J)を黒く塗らないとき 〃 塗るとき TB(K) = = TW(K) = = タイル(K)を黒く塗るとき 〃 塗らないとき 1 0 1 0 タイル(K)を黒く塗らないとき 〃 塗るとき 目的関数 minimize (ダミー) x 制約式 subject to 1.マスは白または黒である B(I,J)+W(I,J) = 1 (I=1,2,....Nr) (J=1,2,....Nc) 2.斜線マスは白マスである W(I,J) = 1 (I,J)は盤中の斜線マス(もしあれば) 3.タイルは白または黒である (K=1,2,....Nt) TB(K)+TW(K) = 1 Ntはタイル総数 4.タイルKが黒のときの黒マスB(I,J) TB(K) ≦ B(I,J) (K=1,2,....Nt) (I,J)はタイルとマス座標との対応表から 5.タイルKが白のときの白マスW(I,J) TW(K) ≦ W(I,J) (K=1,2,....Nt) (I,J)はタイルとマス座標との対応表から 6.タテ方向黒マスの数 K B(I,J)=Nf Σ I=1 (J=1,2,....Nc) KはNrまたは斜線マスI座標、Nfは盤面指定数字 7.ヨコ方向黒マスの数 K B(I,J)=Nf Σ J=1 (I=1,2,....Nr) KはNcまたは斜線マスJ座標、Nfは盤面指定数字 上下界 bounds 変数型 binary B(I,J) W(I,J) (I=1,2….…Nr) (J=1,2….…Nc) TB(K) TW(K) (K=1,2….…Nt) general 終端 end
© Copyright 2024 ExpyDoc