|
|
|
前回の記事からのつづき
問題：
自然数の２個の和で５を表す。
使う自然数は違うもの。
という問題を解くためのLPはこれ。
sum5.lpa君用に・・・
a1 a2 a3 a4 a5 は和に１を使うか、２を使うか、３を使うかというbinary変数（bool変数）
①要素が２個だということの式
a1 + a2 + a3 + a4 + a5 = 2
②和が5になることの式
1 a1 + 2 a2 + 3 a3 + 4 a4 + 5 a5 = 5
③全部の解に番号をふる。２進数的なことで。
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 複数解
と結果がでる。
考察：
前回の記事で提示した「解なし、唯一解、複数解を１回のLPで判定する」という目的は達成した。
だけど、「解が２個以上あれば、複数解だよん」というゆるい要求に対して「解番号の差を最大にする」というギンギンな計算をさせてるため、無駄がある。
今回の問題は小さかったため、問題にならなかったが、大きい問題を解くときには、その無駄が問題になる。このままでは使えない。
整数計画ソルバーでパズル（的なもの）の唯一解判定に関して、いままで、自分の作戦では。
①LPを書いて答えを出す。
②もとのLPに対して①の答えを禁じた条件を追加したものを書き、答えを出す。
「①が解ありで、②で解なしだと、唯一解だ」という作戦を使っていた。
これだと、LPを2回解くことになり、つまり、2回目で同じ計算をまた解かせるので、もったいなさそうなのだった。
今回、LP１回分で、解なし、唯一解、複数解を判定することにチャレンジ。
簡単な問題で進める。
問題は「数nを2個の自然数の和で表す。ただし、使う自然数はみんな違うもの」
n=2だと 解なし
n=3だと 1+2の唯一解
n=4だと 1+3の唯一解
n=5だと 1+4 2+3 解が２個
n=6だと 1+5 2+4 解が２個
ニコリのペンシルパズルのカックロの要素的問題。
大枠の展望
a君に解かせて
同じ問題をb君にも解かせて
a君とb君の答えが違う方をよりよいとしておき（maximizeとかが使えるかなぁ）
①a君とb君が違う答えを出してくれば、複数解
②それでも、a君とb君が同じ答えを出してくれば、唯一解
③a君もb君も答えられなければ、解なし
ということで。
つづく
その１その２の記事は、
ということで問題を作ってみる。
来年は2020年の令和2年なのでそのあたりに絡めて
・・・□□□
×・・□□２
――――――
・・？□０□
・？□２□・
？□０□・・
――――――
？２□□□□
みたいな形を狙ってみる。
解がいっぱい出るようだったので、もう１個２を表出させ、桁を調整した。
ソルバーにかけて、唯一解であることがわかった。めでたし。
完成した問題
・・・□□□
×・・□□２
――――――
・・□□０□
・□□２□・
・□０□・・
――――――
□２□２□□
手で解いてみると、そう悩むことなく解ける問題だった。
先日、パズル懇話会で、「整数計画ソルバーで碁石ひろい」を解いたことを発表した。その後のコメントで「整数計画ソルバーで虫食算や覆面算は解けるか」を聞かれた。それをうけてやってみみた。
その１の内容はこちら
三ケタ×三ケタを整数計画ソルバーでその内容を全部つめこんだLPファイルがこちら。
頭のケタの０チェックをやっていないので、このままソルバーにかけると、000 x 000 = 00000 という答えも正解となる。
虫食算や覆面算を解くためには、このベースに独自の条件を足していけばよい。
「虫食算・筆算」で検索して問題を見つける・・・あった。
のページの「虫食い算の発展問題 その１」というのがぴったりなのでそれを題材で使わしてもらう。
・・・□４□
×・・□４□
――――――
・・□□１□
・・□□４
□□□□
――――――
□□０□□□
・・・ＡＢＣ
×・・ＤＥＦ
――――――
・・ＧＨＩＪ
・ＫＬＭＮ
ＯＰＱＲ
――――――
ＳＴＵＶＷＸ
にあてはめて
LPに数字の条件を足す。
b=4
e=4
i=1
k=0
n=4
u=0
それぞれの１番上位のケタは0にはならないので、それも入れとく。
a0=0
d0=0
g0=0
l0=0
o0=0
s0=0
scipにかけると。
246 x 549 = 135054 と出る。
別解チェックをするには、
「abc def が決まれば同じ答え」「１個でも違えば違う答え」なところに着目して、
a2 + b4 + c6 + d5 + e4 + f9 <=5
を付け加える。
そしてscipにかける。
と「no solution availavle」と他に答えがないことを示してくれる。
虫食算や覆面算に関連して
三ケタ×三ケタの筆算を数字で埋めてみようということで。
それを整数計画ソルバーで解くためにそれようの不等式・等式に直す。
・・・□□□
×・・□□□
――――――
・・□□□□
・□□□□
□□□□
――――――
□□□□□□
・・・ＡＢＣ
×・・ＤＥＦ
――――――
・・ＧＨＩＪ
・ＫＬＭＮ
ＯＰＱＲ
――――――
ＳＴＵＶＷＸ
２４文字でアルファベットにも入って手ごろなサイズ。
①一つの文字に関して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
も同様
これで出来上がり。
以上
更新状況
いわいまさか on twitter
プロフィール
最新記事一覧
最新コメント
- パ：球表面に乱数で点を打つには / かっちゃん / [2015/11/29]
- パ：ライブキューブで３ｘ３ｘ３ / いわいまさか / [2015/11/06]
- ズズトトサウンド / いわいまさか / [2015/09/06]
- ドミノをやった / いわいまさか / [2014/10/26]
- ドミノをやった / かっちゃん / [2014/10/26]
最新トラックバック
- 顔文字？ ( i ^ i ) / (Copious-Systems)
- パ：キャストパズルっていったら / (ケノーベル エージェント)
- パ：ジガゾーパズル / (ケノーベル エージェント)
- 顔文字？ ( i ^ i ) / (低次元日記)
- プ：乱数の使い方がダメ / (ゲームが作れるようになるまでがんばる日記)
ライターからの一言
ドボチョーーーン
