RSS

 

RSS


整数計画ソルバーで唯一解判定 その2

  • いわいまさか
  • at 2019/6/16 19:59:06


前回の記事からのつづき

問題:
 自然数の2個の和で5を表す。
 使う自然数は違うもの。

という問題を解くためのLPはこれ。
sum5.lp

a君用に・・・

a1 a2 a3 a4 a5 は和に1を使うか、2を使うか、3を使うかというbinary変数(bool変数)

①要素が2個だということの式
a1 + a2 + a3 + a4 + a5 = 2 
②和が5になることの式
1 a1 + 2 a2 + 3 a3 + 4 a4 + 5 a5 = 5
③全部の解に番号をふる。2進数的なことで。
a君とb君の答えの比較用に。
1 a1 + 2 a2 + 4 a3 + 8 a4 + 16 a5 = an

同じことをb君にもやってあげて。

解の番号を比較して
diff = an - bn
それができるだけ最大(Maximaize)になるようにしている。

a君b君答えがなければ、解なし
a君b君の答えがあってdiffが0なら、a君とb君が同じ答えを提出しているので、唯一解。
a君b君の答えがあってdiffが0より大きいなら複数解
ということになる。

n=5のところの数字をかえて試してみると、

n=2  解なし
n=3  diff=0  唯一解
n=4  diff=0  唯一解
n=5  diff=3  複数解
n=6  diff=7  複数解

と結果がでる。

考察:
前回の記事で提示した「解なし、唯一解、複数解を1回のLPで判定する」という目的は達成した。
だけど、「解が2個以上あれば、複数解だよん」というゆるい要求に対して「解番号の差を最大にする」というギンギンな計算をさせてるため、無駄がある。
今回の問題は小さかったため、問題にならなかったが、大きい問題を解くときには、その無駄が問題になる。このままでは使えない。



整数計画ソルバーで唯一解判定 その1

  • いわいまさか
  • at 2019/6/16 10:08:58


整数計画ソルバーでパズル(的なもの)の唯一解判定に関して、いままで、自分の作戦では。

①LPを書いて答えを出す。
②もとのLPに対して①の答えを禁じた条件を追加したものを書き、答えを出す。
「①が解ありで、②で解なしだと、唯一解だ」という作戦を使っていた。

これだと、LPを2回解くことになり、つまり、2回目で同じ計算をまた解かせるので、もったいなさそうなのだった。

今回、LP1回分で、解なし、唯一解、複数解を判定することにチャレンジ。

簡単な問題で進める。
問題は「数nを2個の自然数の和で表す。ただし、使う自然数はみんな違うもの」

n=2だと 解なし
n=3だと 1+2の唯一解
n=4だと 1+3の唯一解
n=5だと 1+4 2+3 解が2個
n=6だと 1+5 2+4 解が2個
ニコリのペンシルパズルのカックロの要素的問題。

大枠の展望

a君に解かせて
同じ問題をb君にも解かせて
a君とb君の答えが違う方をよりよいとしておき(maximizeとかが使えるかなぁ)
①a君とb君が違う答えを出してくれば、複数解
②それでも、a君とb君が同じ答えを出してくれば、唯一解
③a君もb君も答えられなければ、解なし

ということで。

つづく



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

  • いわいまさか
  • at 2019/6/07 01:13:24


その1その2の記事は、
三ケタ×三ケタを整数計画ソルバーで その1
三ケタ×三ケタを整数計画ソルバーで その2
ということで問題を作ってみる。

来年は2020年の令和2年なのでそのあたりに絡めて

・・・□□□
×・・□□2
――――――
・・?□0□
・?□2□・
?□0□・・
――――――
?2□□□□

みたいな形を狙ってみる。

解がいっぱい出るようだったので、もう1個2を表出させ、桁を調整した。
ソルバーにかけて、唯一解であることがわかった。めでたし。

完成した問題

・・・□□□
×・・□□2
――――――
・・□□0□
・□□2□・
・□0□・・
――――――
□2□2□□

手で解いてみると、そう悩むことなく解ける問題だった。




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

  • いわいまさか
  • at 2019/6/05 19:08:57


先日、パズル懇話会で、「整数計画ソルバーで碁石ひろい」を解いたことを発表した。その後のコメントで「整数計画ソルバーで虫食算や覆面算は解けるか」を聞かれた。それをうけてやってみみた。
その1の内容はこちら 
三ケタ×三ケタを整数計画ソルバーで

その内容を全部つめこんだLPファイルがこちら。
mul3x3.lp

頭のケタの0チェックをやっていないので、このままソルバーにかけると、000 x 000 = 00000 という答えも正解となる。

虫食算や覆面算を解くためには、このベースに独自の条件を足していけばよい。

「虫食算・筆算」で検索して問題を見つける・・・あった。
http://www.manabu-oshieru.com/chugakujuken/sansu/mushikui.html
のページの「虫食い算の発展問題 その1」というのがぴったりなのでそれを題材で使わしてもらう。
・・・□4□
×・・□4□
――――――
・・□□1□
・・□□4
□□□□
――――――
□□0□□□

・・・ABC
×・・DEF
――――――
・・GHIJ
・KLMN
OPQR
――――――
STUVWX
にあてはめて

LPに数字の条件を足す。

 b=4
 e=4
 i=1
 k=0
 n=4
 u=0

それぞれの1番上位のケタは0にはならないので、それも入れとく。
 a0=0
 d0=0
 g0=0
 l0=0
 o0=0
 s0=0

scipにかけると。
246 x 549 = 135054 と出る。

別解チェックをするには、
「abc def が決まれば同じ答え」「1個でも違えば違う答え」なところに着目して、

 a2 + b4 + c6 + d5 + e4 + f9 <=5 

を付け加える。
そしてscipにかける。
と「no solution availavle」と他に答えがないことを示してくれる。




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

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


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

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

・・・ABC
×・・DEF
――――――
・・GHIJ
・KLMN
OPQR
――――――
STUVWX

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

①一つの文字に関して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について全部、立式。

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

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
も同様 
これで出来上がり。

以上


記事一覧へ