ハイパーロボットの解法のアプリ上での実装についてのメモ2
前の投稿 の続きです。 直進パズルオンライン のシングルプレイに答えを表示させる機能を付けました。 【簡単なアルゴリズム説明】 【実装中で苦労したこと】 【他のアプリとの違い】 を残しておきます。 【簡単なアルゴリズム説明】 1.準備 まず、壁の配位、コマの配位を管理する変数(配列を)用意する。壁の配位は一回ステージが決まれば不変ですが、コマの配位は1手動かしたら変わるので、別の変数(配列)に用意しておきます。また、あるコマをある方向に一手動かし、動かした先のコマの配位を保存できるようなプログラムも作っておきます。 2.一筆書きでゴールできるか判定するプログラムを作る ゴール対象コマを動かして、一筆書きでゴールまで到達できるかを判定するプログラムをまず作ります。ゴールの位置が決まればゴール対象コマも決まり、コマたちの初期位置C[手数=0]から考えて、ゴール対象コマが動ける方向を元に、1手動かして実現できる配位C[手数=1]が決まります。C[n]から動ける方向をそれぞれに対して探し、C[n+1]を作っていくと、(あれば)ゴールできる手順が見つかります。これだけでも体感で1/2くらいの確率でゴールできる手順が見つかります。もちろんこれが最短とは限りません。実現される配位C[n]の大きさはそこまで大きくなく、C[n]からC[n+1]は最大でも3倍にしかならないからです。というのも、まず動ける方向が原理的に4方向が最大で、壁の方向には動けない&来た方向には戻らない、という制限があるので、C[n+1]はC[n]の2,3倍程度の大きさしかありません。例えば2手ずつ増えるとして、10手先まで計算しようとすると、2の10乗=1024程度の計算量になりますが、これはそこまで大きくなく、この一筆書きプログラムは何回も呼んでもそこまで時間はかかりません。 3.総当たりでゴールできるプログラムを作る ゴール対象コマでやった方法を、全てのコマに対して行います。初期位置C[手数=0]から、1手動かして実現される配位C[手数=1]を作り、全て保存します。C[n]からC[n+1]を作る時も同じ方法で、おおよそ10倍くらい配位の数が増えていきます。というのも、例えば5コマある場合、1コマあたり2,3方向しか動けず、以前実現した配位はC[n+1]に入れないので、おおよそ10倍程度になります。...