RSS

 

RSS


パズル


ツインスネークSCIP その2

  • いわいまさか
  • at 2020/10/11 13:25:47

ツインスネークを整数計画ソルバーのSCIPで解く。その2。
もとの問題の盤面は、
参考に、手で解いてくと、
左上の33のところはつながらない。
左下の22のところはつながらない。
右上の11がつながっているなら、左下の11もつながっていて別蛇。。。みたいな感じで。

等式、あるいは不等式を立てて、SCIPにかければニョロニョロっと解いてくれる。式を立てていく。

式①蛇Aの頭パーツa0はc00-c33のどれか1つのマスに対応している。
 a0_c00 + a0_c01 + a0_c02 + a0_c03 + a0_c10 + a0_c11 + a0_c12 + a0_c13 + a0_c20 + a0_c21 + a0_c22 + a0_c23 + a0_c30 + a0_c31 + a0_c32 + a0_c33 = 1
それぞれの変数は0か1なので、16個の変数のうち1個が1で他が0になる。この式を蛇パーツ分16個。

式②c00はa0-a7,b0-b7のどれかの蛇パーツに対応している。
 a0_c00 + a1_c00 + a2_c00 + a3_c00 + a4_c00 + a5_c00 + a6_c00 + a7_c00 + b0_c00 + b1_c00 + b2_c00 + b3_c00 + b4_c00 + b5_c00 + b6_c00 + b7_c00 = 1
 ①があれば、鳩ノ巣原理とかで②はなくても答えがでるかもしれない。が、あっても邪魔しないし、なんなら速く解けるかもなので入れておく。全部のマス目分16個。

つづく。



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