タイルペイント 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 ルール ①盤面上にある、太線で区切られた部分（タイルと呼ぶ）のいくつかを黒く塗る。 ②盤面の数字は、その右あるいは下の、外周か次の斜線のマスまでの区切られた一列のうちで、黒く塗られるマスの数を表す。 ③どのタイルも、すべてのマスを塗るか、すべてのマスを塗らずにおくかのどちらかにする。タイルの一部のマスだけを塗ってはいけない。注）②で示されているように、数は少ないが盤面のまん中付近にも＼と数字を書いたマスのある問題が存在する。マスの行番号をＩ、列番号をＪとし、タイルに番号を振り、マス座標との対応を取った表を用意する。 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 １．マスは白または黒である B(I,J)+W(I,J) ＝ 1 (I=1,2,....Nr) (J=1,2,....Nc) ２．斜線マスは白マスである W(I,J) ＝ 1 (I,J)は盤中の斜線マス（もしあれば）３．タイルは白または黒である (K=1,2,....Nt) TB(K)+TW(K) ＝ 1 Ntはタイル総数４．タイルKが黒のときの黒マスB(I,J) TB(K) ≦ B(I,J) (K=1,2,....Nt) (I,J)はタイルとマス座標との対応表から５．タイルKが白のときの白マスW(I,J) TW(K) ≦ W(I,J) (K=1,2,....Nt) (I,J)はタイルとマス座標との対応表から６．タテ方向黒マスの数 K B(I,J)＝Nf Σ I=1 (J=1,2,....Nc) KはNrまたは斜線マスI座標、Nfは盤面指定数字７．ヨコ方向黒マスの数 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