走れないんじゃないかって思ってたけど突然晴れましたね.よかったよかった.
今日は忘れてませんよ.笑
今日はなんとなくパズルゲームに没頭していました.
iphoneの25bitというやつです.あんま手では遊んでないんですけどね.
というのも,自分は数学問題botというものをフォローしていて
そのbotがちょいちょいルービックキューブを群論で解くっていうのをオススメしてくるんですよね.
自分は群論をやった時に結構な面白さを感じたのでその本読んでみたかったのですがなかなか本屋にないので,
いきなりルービックキューブなんて難しいものはやらずに簡単なパズルを自分でやってみようと思ったのでした.
というわけで見つけたのはこちら,
25bitというゲームです.
このゲームのルールは以下の通り.
5x5の25マスがランダムに光っているので,ある操作をして全部消してください.
それである操作というのが任意のマスをタップすることです.
するとそのマス,左右,上下の合計5マスが反転します.
反転というのは,点灯していたら消灯,消灯していたら点灯ということです.
例えばこんな場面,広告は気にしない方向でいきましょう
マスに名前をつけましょう.左から3番目上から4番目のマスを 3 4 と名付けます.
この盤面は
4 4→4 2→2 4→2 2
とタップすると.
さて,本題にいきますね
自分の思考回路はこんな感じでした.
盤面の状態を要素とした群を考える
0盤面 何も光っていない盤面
0盤面にの任意のマスを1回だけ押したものを基本変換とする.
基本の群の要素は25種類.組み合わせたものはたくさんある.
演算「*」を要素同士の演算と定義する.
内容は盤面の重ね合わせ.
群の定義を確認すると.ルールは4つ必要
要素全体を集合Gとすると,任意の要素S,T,Uに関して
1.S*TはGの要素
2.S*E = S なる単位元の存在
3.S*F = E なる逆元の存在
4.S*(T*U) = (S*T)*U
この四つ.
1は自明,2は0盤面,3は自分自身,
4を考えてみる,
光っている部分を1,そうでない部分を0とすると.
盤面を足す行為は自分のあるマスが光っている時,相手の該当する部分に1を足していくという操作である.
最終的にマスが光っているかどうかは盤面の数値を2で割った余りで評価できる.
この最終的なマスの値は演算を行う順番に左右されないで,分配法則どころか可換であるので,与えられた群はアーベル群であるとわかった.
例えば与えられた盤面がS*T*S*S*T*S*U*S*Tで表すことができる時
S*T*S*S*T*S*U*S*T = S*S*S*S*S*T*T*T*U = S*T*U
が得られる.
以上のことを踏まえると,
問題は
1.圧縮が1通りであるか.
2.与えられた盤面をどうやって特定するのか.(最小手数にでなくていい)
の二つとなる
1番はある演算の塊をS*S = Eとするだけで最小手数に変換できるかを示すのに必要,例えば
基本操作S,T,U,V,Wにたいして.
S*T*U = V*W (操作3回から2回)
のような変換が成立してしまった場合時,最小手数の圧縮には特別な場合としての例外処理が必要になる.
2番はどういうことかというと,最小手数でなくても,何かしらの方法で簡単に表すことができれば,その演算の塊を上の式のような操作で最小手数に変換することができるということ.ようするに最小じゃなくていいから有限な回数の操作で確実に解ける手法が欲しいということです.
1について考えてみる.
合わせることで全く別の変換になってしまうものがあるか,,,,
ないことを示すのは難しいですね,とりあえず背理法を使ってみます.
背理法とは,ありえないことを示すために,あると仮定して話を進めた時に発生する矛盾を提示するという手法です.(ここまで読んでる人に背理法を知らない人はいない気がするのですが一応)
って流れだったんですけど,単刀直入に言うと,線形独立じゃなかったです.
なので同じボタンは2回以上押されることはないことが,群を定義している段階の4で明らかになっているので,
どのボタンを押してどのボタンを押さないかで全探索します.
こういう時は再帰関数です.
25このボタンについて,押すか押さないかを再帰的に遷移していきました.
(本来ならメモリを使いすぎてしまうのでスタックで状況を積むのがいいです)
こんな感じの関数で計算すると,,
という感じで無事解けました.ただ盤面が2次元配列なのでえらい計算時間がかかる
本来なら2^25パターンなので1秒かからないくらいなのですがそれに25が二回くらいかかっちゃってる..
それで18秒...
なので盤面をint変数に叩き込んで引き算やbit積など,一気に計算したら良さそうですね.暇な時に直しておきます.
久しぶりにアルゴリズム(?)の話でした.
おやすみなさい.