まさしく「おねえさんの問題」ですね。ただの総当たりだと高々4^(n^2)通り調べないといけないので、こちらも簡単なバックトラック法で書かせていただきました あれから、おねえさんの問題のプロジェクトをされていた方の著書で、アルゴリズムの流れはおおよそ理解できましたが、プログラミングに不馴れで未だにそれを再現できておりません…

先日のself-avoiding crossの問題、いろいろ参考にしたり工夫にしたりして4×4の計算にかかった時間が3分2秒から52秒になりました。せっかくなので5×5もしましたが、4時間19分9秒…6×6なんてやったら、何年かかるだろう

まさしくその通りです。遠回りしてもいいけれど同じ角を通らないで左上から右下まで移動する方法...となります。 単純なのですが、マスが1つ大きくなると計算量が何千倍にも何万倍にもなってしまうんのでそれだけ時間がかかるんですよね..

同じ道なだけで、全部通らなくても大丈夫です！ 10×10までは処理できるようにしているのですが、5×5の時の答えは4×4の150倍になるので待つと半日かかりそうなんですよね...

昔の感覚を思い出すために、格子上の道の通り方を数えるプログラムを組んでみました。4×4が限界だし論文とか読んでアルゴリズムを導入しないとダメかな···