RSS

  

RSS

プログラム


三ケタ×三ケタを整数計画ソルバーで その１

  • いわいまさか
  • at 2019/6/05 01:37:16

虫食算や覆面算に関連して
三ケタ×三ケタの筆算を数字で埋めてみようということで。
それを整数計画ソルバーで解くためにそれようの不等式・等式に直す。

・・・□□□
×・・□□□
――――――
・・□□□□
・□□□□
□□□□
――――――
□□□□□□

・・・ＡＢＣ
×・・ＤＥＦ
――――――
・・ＧＨＩＪ
・ＫＬＭＮ
ＯＰＱＲ
――――――
ＳＴＵＶＷＸ

２４文字でアルファベットにも入って手ごろなサイズ。

①一つの文字に関して0～9の場合を全部binary変数にする。
例えば、a3 は「aは3だ」を表す。
どれか一個ヒットするわけ。

a0+a1+a2+a3+a4+a5+a6+a7+a8+a9=1

これをa～xについて全部立式

② やっぱり、その文字がいくつかを変数にして、①との因果関係を記載
a0=1 -> a=0
a1=1 -> a=1
a2=1 -> a=2
・・・
a9=1 -> a=9

a～xについて全部、立式。

③１行分のつながった文字列を変数として、各文字から計算すると

100 a + 10 b + c - abc = 0
同じようにdef ghij klmn opqr stuvwx も立式

④縦の足し算を計算する

100 opqr + 10 klmn + ghij - stuvw = 0

⑤ そして三段分の掛け算のところは
計算で書くと　abc * f = ghij　ではあるが、
入力として、「変数と変数の掛け算が使えない」ので、
fを全部場合わけして

f0=1 ->          ghij = 0
f1=1 ->    abc - ghij = 0
f2=1 ->  2 abc - ghij = 0
f3=1 ->  3 abc - ghij = 0
・・・
f9=1 ->  9 abc - ghij = 0
と書く

abc * e = klmn
abc * d = opqr
も同様　
これで出来上がり。

以上

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

コメントを書く