○○○○×○=○○○○

ネットに虫食い算があって、

1から9までの数をすべて使って次を完成させよ

〇〇〇〇×〇=〇〇〇〇

ってあって、すごく難しいと書いてあった。実際、一般化されたこの種の虫食い算はNP完全として知られていて、結局、オーダーにおいてはすべての組み合わせを試して代入して成否をみる以上のことはできないが、ネットで調べてみたら、奇妙なことにこのタイプ、ジャストな問題が沢山あって、なぜかみんなこの問題でひっかかっていた。いわく、

これに固有のエレガントな方法があるはずなのに
見つからず、結局は地道にそれを実行する以上の
ことはなんにもなかった

というこれまた共通の感想を残して。もちろん計算機にかけると一瞬で解くが。だって所詮すべて試しても9!だから。結局は変数の数が進数の底（※）以上にはできないから。

（※）今回は10進数なので文字は9つしか使えない。実際は10だが、無数のヒントや解が生まれる0を嫌う人は沢山いて、0を除いた9つから選ぶ問題

私はかなり苦労してありそうな組み合わせを810にまでは落としたが、母さんは810ってほぼほぼ全然すべてじゃんって言われた。

エレガントな解法なら示してもエレガントだが、そうでもないが、一応書くと方法としては

・一つ目の一番上の数字と二つ目の数の組み合わせを
本来ならば数字の選び方としては単純には9×8で72通り
あるはずだが、まず9通りにまで減らすことに成功した

・それから1の位、10の位、100の位と数字を選ぶことで
6×5!!=90通りにまで減らすことに成功した

組み合わせて9×90=810。だけど、もう少し直感的には少ない感じはするけど。実際は多少は使い回しがあるから、なあ。まあだから、結局は明らかに駄目なやつは避けて必要な計算はする感じで、大きいのは1の位で、1,5,9が無理なのがある程度計算すればわかるのとやっぱり一番上の桁で、2つ目の数とかけて10はいかない。それぞれ証明は

・1が駄目なのは単位元で、単位元はかけたら同じ値になるから。5は0と5しか生まず、5はもちろん駄目で、0も駄目。9をかけたら、1234×9でさえ、5桁になるからアウト。

だから、やっぱ2つ目の数が一番最初に決める数で、234678しかなくなる。8も結局は125〇タイプまで数えれば簡単に除けるから、23467。

まあわからないけど、結局、1の位は23467から選んだ数と1、5とそれを除いた2346789の6通りで、5×6=30通り。これでもかなりまだ多いけど、9×8よりは少ないのかなあ。まあだから、だけど、わからないけど、同じ結果は使い回したい願望あるから（混乱中）、わからないけど、気分的には9×90だったら流石に多すぎるから、9+90くらいに抑えたいんだが、90は大げさにせよ。100くらいなら計算してもいいレベルじゃね。問題は結局は4桁が一致ならば下n桁の計算結果が一致から、それやりたいのと1万オーバーで無意味かの両立難しいっていうか、最適化しすぎて全体像を見失ってる感じあるが、経験からしたら、下2桁は全部調べてもいい気するけどな。1589なしの2つ目（5パターン）からの数4つ選ぶ方法が、9×9×9×9通りだけど実は15とそれないから6×6で36通りで、微妙。下2桁は36通り。だから、36×5なら180だが、もっと減るかもしれないが、まあだから上2桁と下2桁で調べてみたら、上2桁は大きさを大体決めるし、下2桁は組み合わせを決めるから、一応は求まるのかもなあ。結局分解するのと重複のデメリットで微妙だが、まとめると

2つ目の数を23467から選ぶ
・10000を越えてしまうラインを計算する
・基本、ボトムアップに計算する

でいいような。やってみると、2の場合、5でアウトだから、134、3の場合、4でアウトだから、12、4の場合、3でアウトだから、12、2については25〇〇がアウトだから、24〇〇、6の場合、2でアウトだから、17でアウトだから、16〇〇、1666でアウトだから165〇、7は143でアウトだから、1429はアウトで、1428まで。

2の場合、1桁目15と2ないかは346789、それに対して結果1桁目682468だから、2はアウトだから、6はアウトで、34789の5通りに対し、68468。2桁目は123456789から2番目の数と1桁目の残りの数2つ除くから6つからか。36なければ145789、13×2=26で2があるからアウトで、1消える、4は8あるから、43×2=86、5は0で消える、7は73×2=46だからOK。8は66になるからアウト、92×2は86だから可。だから、2番目の数が2、1桁目が3なら、2桁目は158が消えて479のみ。これをそれぞれやって、（1桁目、2桁目）=（3,479）、（4,37）、（7,156）、（8,1345）、（9,13567）だから、3+2+3+4+5=19通り（下2桁）。上2桁の選び方は上1桁を134から好きに選ぶ。上2桁目をそれ以外から好きに選ぶから21通り（上2桁）。そうすると可能性は上2桁×下2桁で19×21<400で抑えられるが、実験データによれば、これはいずれもうまくいかないらしい。3桁はしたくないなあ。9個のうち5つは使ってるから、半ばのはずだが、わからないが、一応、たとえば、1桁目が3、2桁目が4なら上1桁は1で、上2桁目は123456789のうち1（上1桁）、2（2番目）、3（1桁目）、4（2桁目）、6（1桁目結果）、8（2桁目結果）はNGだから、579だけが可能性で、2桁目は繰り上がらないから、579だけで2倍したらそれにしなくてはいけなくて、5×2=0アウト、7×2=4アウト、9×2=8アウトで全滅。でこの線は消える。だから34は消えた。37は1589から上2桁を作らないといけないから上1桁はまたしても1確定。だけど、上1桁の結果の方が作れないから消えてアウト。37は消えた。39は1457で上2桁同士を作る+繰り上がりあり（+1）。これもやっぱ4の線が2倍して8超えるから消えて、上1桁は1確定。だけど上1桁の結果の方が4以上には絶対ならんから消える。これで（下1桁）3のラインは消えた。残り16通りについて考える。やっぱ上1桁4のラインを消しといた方がいいと思うんだけど。4×2=8だから上1桁の結果の方は8か9で、41、43なら8、45、46、47、48なら9で間違いないけど、だから、（2番目の数を）2（にしたの）に加えて（上1桁目に）4を選んで（結果の方が）8になった場合、248はNGで、反対に9になれば、249NGで、48NGなら下1桁は79しかなくて、反対に49NGなら78しかないが、下1桁7ならそれは4だから7の線は消えて、だから上1桁が48なら下1桁は9確定。上1桁が49なら下1桁は8確定。つまり4〇〇〇なら4〇〇9×2=8〇〇〇タイプか4〇〇8×2=9〇〇〇タイプ。だけど下1桁89タイプ多いんだよなあ（それぞれ4通り、5通り）。実際、4〇〇9×2の下1桁は8になるからアウトで、あり得るのは4〇〇8×2=9〇〇〇タイプのみ。展開してみれば、上2桁が45、47タイプと下2桁が81、83、85タイプで、4 [5,7] [1,3,5] 8 ×2=9〇〇6、展開すれば、4518,4538,4718,4738,4758の5タイプ。実際には45を2倍すると90になり、しかも下から繰り上がってこないから45タイプはなしで、結局47タイプだけが残る。しかし47タイプは2倍すると94になって4だぶるから繰り上がる5以外は駄目で、結局4〇〇〇タイプは4758だけ。4758×2=9516で5かぶるからアウト。結局（上1桁目の数字）4は消せる。つまり（上1桁目の数字は）1か3。上2桁をこれで2×7＝14通り、下2桁を14通りにまで落とせた。14^2=196だからさっきの半分以下になってる。筋の悪い（下1桁目）4をとがめたいが、（下2桁）43なら3使ってるから上1桁目は1確定で、1〇34×2=〇〇68で、結果の方の上1桁目は繰り上がりを受けてもせいぜい4なのに1234使えず、NG。47なら

あー普通に下2桁、表記仕方の揺れで普通に計算ミスした。でもない？？74×2=48でNGだった。4だぶるから。

気のせいだったけど、いずれにせよ、4の筋は消えて、1桁目は7,8,9のいずれか。12通り。実際はだから、100の位の数を決めるのに上1桁の値は避けて、下2桁の値は避けてそれが2倍だから、どれも3つの未知数にまで下げれるから、上1桁の値の個数（=2）×下2桁の値の個数（=12）について、３つ（上2桁目の2つの数字+上1桁目の数字の結果の方）の虫食い算を解けばいい。実際は多少減って、2（2番目の数）からの1（1桁目の数字）からの75,76,83,84,85,93,95,96,97（下2桁9種類）もしくは3（1桁目の数字）からの71,75,76,81,84,85,91,95,96,97（下2桁10種類）を考えればよい。

（場合わけの様子）

なお、上1桁の値が1の場合、結果の方は2か3で、2は使ってるから3確定である。したがって、上半分の3が出る場合は自動的に消える。

計算して、1〇（48,79）×2=3〇（96,58）、ないし、3〇（57,48,58,59,79）×2=〇〇（14,96,16,18,58）だけでいいとわかる。7通り。

前者は結局調べればないとわかり、後者についてもたとえば3〇57、3〇79については7が消えて、答えの上1桁は6と決まる。そして残りを検討したらうまくいかない。そして残りは3〇48=〇〇96÷2、3〇58=〇〇16÷2、3〇59=〇〇18÷2のみで、それぞれ157ではうまくいかず、279ではうまくいかず、467ではうまくいかず、結局2倍してうまくいく場合はないとわかった。

とりあえず2番目の数が2の場合は消せたなあ。