2019この手のゲームはいろいろな研究ができて楽しいですよね。研究してみる具体的には以下のものについて考えたいと思います。計算するのにどのくらい時間がかかるか語句の定義これが曖昧だと語句でこんがらがるので、以下のように定義します。する(全ての値が0)まずこのゲームをどうやって数学の世界に落とし込むかということが重要になります。これ自体は簡単で青いパネルを1、白いパネルを0として考えればいいわけです。初期盤面は以下のように表現できるわけです。数学的な表現に落とし込むパネルを押した時に押したパネルの周囲のパネルも反転するのですが、これをどうやって数学的な表現に直せばいいでしょうか?計算空間ここで、以下のような計算空間(これは正しい表現ではない)を考えます。一見すると不思議な計算に見えますが、こういうヘンテコな計算の世界を定義するわけです。このヘンテコな計算方法はXOR(排他的論理和)として知られています。パネルを押して、その周囲のパネルの色が反転するというのをこの計算空間を使って求めます。押したときに反転するパネルを1、そうでなければ0という風に考えます。初期行列から左上隅のマスを押したときに次にどのような状態になるかは以下のように求めることができます。左上隅のマスを押したときの変化これを用いることでマスを押したときに次にどのような状態になるかが計算できるわけですね。対称性パネルの押し方と、押したときの反転パネルの表現ですが例えば一番上の列ですと四通りの押し方があるように思えます。実質二通りところがこれらは対称のものが存在するので、実際には二通りだけ考えれば良いことがわかります。実質二通り二列目も同様に四通りありますが、対称なのでこれも二通りだけ考えれば問題ありません。これ以降は上下に対称なのでやはり考える必要がありません。よって、考えるべき基本的な変換行列は次の四つしかないことがわかります。完全性さて、このゲームが完全であるかどうかについてウラルさんが研究してくださったので、その成果を発表したいと思います。どんな初期行列からでもクリアできるかというのは「与えられた任意の行列をゼロ行列にできるか」というのと等価です。これを全て検証するのは難しい問題ですが、任意の一マスだけを反転させることが可能ならばそれを繰り返せばどんな初期状態の行列でもゼロ行列に持っていけることがわかります。この場合も、16マス全てについて反転可能かどうかを調べる必要はなく、上に挙げた三マスについてだけ調べれば大丈夫です。基本変換行列を達成するパネルの押し方ウラルさんの研究結果から、それぞれの行列を達成するパネルの押し方が発見されました。このことから、任意の初期行列をゼロ行列にすることができるということが証明できました。これらの情報から、最も手数がかかるのは全てのマスが青い初期行列のケースで、100手かかることも求められます。これはワーストケースを考えているので、どんな初期行列でも高々100手あればクリアできるということを示しているにすぎません。実際には全部青いマスの場合は四隅を押せば四手でクリアできます。これ、パネルの押す順番って関係ないの?ないよー、何故ならこの計算空間では可換性が成り立つからね。可換性パネルを押す順番が関係ないかどうかは交換法則があるかどうかで決まります。わかりやすく言えば加算や乗算には交換法則が成り立ちます。減算や除算は加算や乗算に直せば交換法則が成り立ちます。成立さて、これを見ると交換法則が成り立っていることがわかります。いうよりも、交換法則が成り立つような計算空間を定義したと考えたほうが正しい。Cとすれば「可換性があるのでその三つを押す順番は入れ替えても良い」ということになります。上のような感じで順番を代えても問題ないことになります。今回の問題の場合、反転させたいマスが八つあるのでそれぞれについてパネルの押し方を考えます。これは基本変換行列を反転させたり回転させたりすればすぐにどのマスを押せばいいかわかります。それぞれのマスの押す回数さて、ここでそれぞれのマスを押す回数が求められました。合計すると40だから40回押さないとダメ?よく考えたら40回も押さなくていいことがわかるよん。単位行列(変換)さて、ここで同じマスを二回押した場合の挙動について考えましょう。えーっと、一度反転させたものをもう一度反転させるわけだから...元に戻るということやね!二回変換するともとに戻る当たり前だが、A以外でも同じ変換を二回行なうと元の状態に戻ります。ここで、Iとは元の行列に足しても全く変化しない変換と定義します。全ての値が0の行列ということですね。全ての値が0の変換ということはどのマスも押していないのと同じなので、これは無視して良いということになります。あるマスを「偶数回押すというのは一度も押さなくてよい」「奇数回押すというのは一度だけ押す」と考えればいいことになります。単位行列に従って、押すべきマスと押さなくてよいマスを分けると以下のようになります。解法このとき、色がついているマスが十あるので、この初期状態の最短手数は”高々”十手であることがわかりました。同じマスを二回以上押さない解のことを合理的な解、と呼ぶことにします。最小手数を求めるさて、ここで今回の問題について厳密に最小手数が十手であると断言してよいのでしょうか?初期行列まず、初期行列が全部で何通りあるかを考えます。通りの初期状態が考えられます。単位行列の性質から同じマスを二回以上押す意味がないので全てのマスは押すか押さないかの二択になります。これも全てのマスについて考えらえるのでマスの押し方も、となります。マスの押す場合の数と初期状態の数が等しいので「違うマスの押し方によって同じ変換にならない」ことが証明できれば、初期状態に対して合理的な解がただ一つしか存在せず、それが最小手数解であることが保証されます。合理的な解と初期行列は一対一対応か?上の図はあくまでも一例。実際にはそれぞれ65536通りあるので、紙面の都合上全てを書ききることはできません。一つの初期状態に対して解が一対一対応であればいいということですね。独立性さてここで問題となるのは「あるマスを押したときの変換行列が他のマスをいくつか押したときと同じ変換行列にならないかどうか」ということです。これがYESなら、初期行列と解が一対一対応でなくなるので唯一解が最小手数解であることが保証されなくなります。要するに「Aという変換と、BとCを押した変換が同じものにならないと言えるか」ということになります。成り立つか?これだけだと確かめるのが難しそうに思えますが、先程の単位行列の話を持ち込むと少しだけわかりやすくなります。単位行列に変換もしもAという変換がB+Cと同じ変換であるなら、可換性から更にAを押した状態を考えることができます。このとき、左辺は単位変換の法則から同じ変換を二回行えばもとに戻るのでIになります。変換の和になっています。今回はわかりやすく右辺は二項になっていますが、項の数がいくつであっても同じ議論ができます。これは「同じ変換を二回使わずに単位行列をつくることができるか?」という問題と等価だということです。初期行列から同じマスを押さずに、再び初期行列に戻れるか?という考えもできますね。これは結果的に「そのような組み合わせはない」ということがわかっているのですが、証明ができていません。独立性自体の証明はできていないのですが、これが正しいことはわかります。ウラルさんが如何なる初期行列においても解が存在するということを証明したからです。考え方の違いこの論理によって、合理的な解が唯一であり最小手数解であることが保証されるわけです。この考えは別の問題でも推し進めて使うことができそうです。一般的なルールでは合理的解の数と初期行列の組み合わせが同じになるので、真ん中のケースが一番多そうな気がします。ついて全ての変換行列に対して逆変換が存在するとき、合理的解の数と初期行列の数は一致する逆変換とは、押したセルを押せば元の行列に戻る(一回でなくてもよい)ということを指します。完全性について「完全性がある」というのは「任意の一マスを反転させる変換行列の組み合わせがある」というのと同値である独立性について逆変換があれば、独立性があるまとめさて、結論として最小手数解を求めることができたのですが、これは果たして正しい求め方だったのでしょうか?ルールが複雑になって、パネルの数が増えれば手作業で「任意の一マスを反転させる変換行列の組み合わせ」を見つけることは困難になります。コンピュータでパッと解があるかどうか、最小解であるかどうかを求める方法はないのでしょうか?また、今回はその手の解析をしなかったために計算複雑性について全くの手つかずになってしまいました。次回への宿題ということにします。あと、この手の問題は恐らくあみだくじと同じで合理的解と組み合わせが常に等しく、必ず一対一対応になる気がします。自身を天才と信じて疑わないマッドサイエンティスト。十字架の疵は彼女につけられた。PM可換性があるなら最短手を探す方針は簡単ですね。回の操作は等価変換になっています。この操作は結合性、単位元の存在、逆元の存在が示されていますから、群をなしているといえます。あるなら直和分解してみるなど群の構造を調べれば数学的な構造は明らかになると思います。群と言いますが、その構造は一般によく調べられてますから、数学的にはこの問題は解決しているように思えます。回以下の解から等価変換になる組み合わせを全て除去することで最短手が得られそうですね。要請されるでしょうから、取り除く順番は問われないはずです。ものを予め整理しておけば最短手が出力されます。AMもしも独立性がなかったとした場合は、仰られるように等価変換でより小さい解を得ることができそうですが、解が存在するかどうかのチェックは現状2^Nでの総当りでしか判定することができないように思えます。なるとこれはSATへ還元できるので(少なくとも)NP完全問題ということになるのですが、対称性などを考えればより良い解の見つけ方がありそうな気もします。コメントをキャンセルメールアドレスが公開されることはありません。