RSS

  

RSS

プログラム


整数計画ソルバーでカックロ

  • いわいまさか
  • at 2019/7/13 15:33:13

制約ソルバー
整数計画ソルバー
SCIP
で過去、解いてみたのは、

シャカシャカ
スリザーリンク
ミッドループ
古典の碁石拾い
とかとか


カックロはまだ、解いてない。
盤面入力の問題はさておき、コアのところだけ、考えてみると。

カックロ
①ひとつの空白マスAに対して 
 a1 a2 a3 a4 a5 a6 a7 a8 a9 という変数を用意。
 binary値（論理値）でそのマスが、1であるかどうか、2であるかどうか・・・・という値。
どれか１個が1(true)になるので
 a1+a2+a3+a4+a5+a6+a7+a8+a9=1  となる。
それを全空白マス分

②その空白マスＡがいくつかという変数も用意する。
a1=1 =>  a=1
a2=1 =>  a=2
a3=1 =>  a=3
・・・4～9も同様
となる。
全空白マス分。

③すべての表出数字に対して、合計の式をたてる
a + b + c + d =15　
全表出数字分。

④「同じ数字を使ってはいけない」
ひとつの表出数字に対応した一連の縦、横のマスメに対して、
a1 + b1 + c1 + d1 <=1
a2 + b2 + c2 + d2 <=1
a3 + b3 + c3 + d3 <=1
・・・3～9も同様
全表出数字分。

これで、おしまい。
数独の解き方の、ちょいプラスぐらいの感じ。

⑤ 唯一解チェック

①～④までの式をたてて溶かして、解がなければ、解なし
解があれば、解あり。
「一番目の答え封じの式」を付け加えてもう１回解いて
解があれば、別解あり。

答え封じの式は
例えば全空白マス目が40個だったら。
１番目の解の①での変数のtrueになったものを全空白マス目分足して
a? + b? + c? + d? + e? + f? + ........ <=39
といったところ。


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

コメントを書く