RSS

  

RSS

パズル


パ：波及効果整数計画

  • いわいまさか
  • at 2014/8/12 10:50:21

ニコリの波及効果というパズルを整数計画で解く。
ために、大筋をメモっておく。

パズル的にも数独には似ているし解き方も似ている。

エリアの最大面積は８として

変数を設けて
ｘ ( t, y, n)　= 0  or 1
意味は「縦がt 横がyのマス目に入る数字がnだ」
n=1,2,3,4,5,6,7,8

①マス目一個に関して

x(t,y,1)+x(t,y,2)+x(t,y,3)+x(t,y,4)+x(t,y,5)+x(t,y,6)+x(t,y,7)+x(t,y,8)=1

②同エリアの１個の数字に関して

たとえば、面積４エリアの３に関しては
x(t0,y0,3)+x(t1,y1,3)+x(t2,y2,3)+x(t3,y3,3)=1
な感じ

③横へは
　数字１に関しては
　幅２のところに１が２個入るとアウト
　x(t,y,1)+x(t,y+1,1)<=1 

　数字２に関しては
　幅３のところに２が２個以上入るとアウト
　x(t,y,2)+x(t,y+1,2)+x(t,y+1,2)<=1 

　以下同様

④縦は
　横と同様

⑤表出文字は
　縦ｔ横ｙのマス目が３って表出しているなら
　x(t,y,3)=1

条件式的なところは以上

////////////

「問題の入力がたいへんだ」とネット内の情報に書いてあった。
確かに、そう思う。

プ：枠線も含めてテーブルで持つ
を使うとよい。

テキストで
①入力重視、半角で線ありなしを"*"と"."で入れる
とか
②全角でそのまま打ち出せば人がとけるようなのを入力にも使う

さらには、ＧＵＩを使うとよいかも。

エリア分けはプログラムで。

以上

  • コメント (0)
  • トラックバック (0)
トラックバックURL :
http://www.iwai-masaka.jp/tb.cgi/56111

コメントを書く