RSS

  

RSS

プログラム


プ：スリザーリンク整数計画

  • いわいまさか
  • at 2014/7/26 11:42:38

スリザーリンクを解くプログラムができた。

１．表出数字まわり

表出まわりの条件を入力文を数字全部に対して書く
 x0203 + x0403 + x0302 + x0304 = 2

縦２ケタ横２ケタのインデックスは
プ：枠線も含めてテーブルで持つ
の方法で表現している。
偶数偶数は十字
偶数奇数は横線
奇数偶数が縦線
奇数奇数がマスメ

x0203 は(2,3)の横線がないかあるか　0 or 1。

２．十字部分の条件を書く

十字部分の条件を全部の十字点で書く

 x0102 + x0302 + x0201 + x0203 - 2 x0202 = 0

x0202の十字部分を通過しているならば、
そこにつながっている縦線横線の本数は２本

x0202を通過していないならば、
そこにつながっている縦線横線の本数は０本

x0202は（2,2)の十字を通過してないかしてるか　0 or 1

盤面に
プ：「パンの耳」法　
も採用したため。
角や辺に乗った十字も式の項数を減らさず同じ式でかける。
パンの耳部分の縦線横線はONにはならないので
x0102 = 0 と指定しておく。

３．　１個の輪ねらい　＋別解探索

以上の１、２でだいたい答えが出るけれど、「全体で１個の輪」にならない場合がある。

一方、「問題作成のおともに使う」ことを考えると別解探索も必要。

この二つは実は、対応方法が似ている。

「整数計画法内」で「１個の輪ねらい」をするのはやめて、以下のようにした。

最初の入力分作成
　　↓
くりかえし
{
　入力文
　　↓
　scipで答えを出す
　　↓
　答えのループの数を調べる
　　↓
　ループが０個　もう答えなし　終了();
　ループが１個　これは解答　 ２解目があると別解あり;　　(a)
  ループが複数　解答じゃない                                     (b)
　　↓
　入力文に(a)や(b)でたループは禁止するようにつけくわえる
｝

(b)で出た小ループは１個の「ループ毎」に禁止していくので、効率は悪くない。

縦線横線６本での小ループは
x2007 + x2009 + x2106 + x2110 + x2207 + x2209 <= 5
というような式で禁止できる。
他の盤面の部分に関係なくこの小ループはもうできない。

「別解があるなら」探索をやめる作戦でいくなら、
できうる「小ループ」を全部チェックする前に探索が終わる場合もある。

考えられる欠点：
　「唯一解だが、盤面にまだ小ループをつくる余裕がある」ときに「解なし」という誤判定をするかも。

追加2014-07-30
上記の「考えられる欠点」は些細のことで、
本当の欠点は、「処理速度が遅いこと」かも。







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

コメントを書く